본문 바로가기

이분 탐색32

[백준] 28449번 : 누가 이길까 (C++) 28449번 : 누가 이길까 문제) HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다. HI팀엔 N명 ARC팀엔 M명이 속해있다. 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 N × M개의 대결로 이루어진다. 모든 참가자는 코딩실력을 가지고 있다. 대결을 하면 더 높은 코딩실력을 가진 참가자가 승리하고, 두 참가자의 코딩실력이 같다면 무승부가 된다. 하얔이는 이 대회의 결과를 빨리 알고싶어졌다. 하얔이를 위해 대회의 결과를 예측해보자! 입력 : 첫째 줄에 HI팀의 인원 수 N, ARC팀의 인원 수 M이 공백으로 구분되어 정수로 주어진다. (1≤ N , M ≤100000) 둘째 줄에 HI팀의 참가자의 코딩실력을 나타내는 길이 N 수열 a_i가 공백으로.. 2024. 2. 4.
[백준] 16498번 : 작은 벌점 (C++) 16498번 : 작은 벌점 문제) 세 명이 한 팀이 되어 정수를 조합하는 게임이 있다. 이 게임에서 각 팀의 각 플레이어는 정수가 하나씩 적혀있는 숫자 카드를 한 장 이상 받는다. 각 플레이어는 가지고 있는 숫자 카드 중 한 장을 선택해 책상에 내려 놓는다. 이렇게 되면 책상에 총 3장의 카드가 놓이게 되며, 이 때 보이는 수의 최댓값과 최솟값의 차이가 벌점이 된다. 이를 식으로 표현하면 다음과 같다. | max(a,b,c) – min(a,b,c) | 여기서 a, b, c는 각각 플레이어가 선택하여 내려놓은 카드의 숫자 값이다. 세 명의 플레이어에게 주어진 숫자 카드가 주어졌을 때, 만들 수 있는 가장 작은 벌점을 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 첫 번째 플레이어가 받은 숫자 카드의 개.. 2024. 2. 3.
[백준] 13423번 : Three Dots (C++) 13423번 : Three Dots 문제) 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 Xa, Xb, Xc이다. 이때 점 a, b 사이의 거리와 점 b, c사이의 거리가 같으면 세 점의 간격이 같다고 한다. 즉, Xb - Xa = Xc – Xb일 때 세 점의 간격이 같다. 다음은 N = 5인 경우의 예시이다. 위 예시에서 점의 위치는 각각 -4, -1, 0, 2, 4이다. 이중 -4, -1, 0위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 1로 간격이 같지 않다. 그러나 -4, -1, 2 위치의 세 점.. 2024. 2. 2.
[알고리즘] 이진 탐색 (Binary Search) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 목차 0. Intro 1. 이진탐색의 아이디어와 기본 구현 2. 이진탐색 응용 3. 매개변수 탐색 0. Intro https://namu.wiki/w/%EC%97%85%20%EC%95%A4%20%EB%8B%A4%EC%9A%B4#toc 업 앤 다운 - 나무위키 가장 많은 경우에 룰로 사용하는 5번 안에 맞히기의 경우를 생각하여 보자. 중간값만을 부르는 전략(최적의 전략)을 선택한다면 log⁡250≈5.64⋯\log_2 50 \approx 5.64 \cdotslog2​50≈5.64⋯이므로 이론상 namu.wiki 위 링크를 읽어보면 이진 탐색의 수학적 핵심을 알 수 있다. 요약하자면 중간값만을 부르는 최적의 전략을 .. 2024. 2. 2.

티스토리툴바