이분 탐색 알고리즘의 개념을 학습하고 나면 한가지 궁금증이 생긴다. 이분 탐색 알고리즘이 어떤 식으로 문제에 출제될 수 있을까? 순차 탐색보다 더 빠르게 데이터를 탐색할 수 있어서 사용되는 것이 다일까?
이러한 궁금증을 가진 상태로 백준이나 코딩테스트를 통해 문제를 풀다 보면 전형적인 이분탐색 기법을 활용하여 풀 수 있는 문제들을 마주하게 되는데 바로 파라메트릭 서치 유형의 문제이다.
- 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제(decision problem)로 바꾸어 푸는 것이다.
- 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이분 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
위 표현이 지금은 와 닿지 않을 수 있다. 전형적인 예제를 풀어보면 더 이해가 쉬울 것이다.
import sys
input = sys.stdin.readline
k, n = map(int, input().split())
data = [int(input()) for _ in range(k)]
left, right = 1, max(data)
result = 0
while left <= right:
mid = (left + right) // 2
total = 0
for i in data:
total += i // mid
if total >= n:
left = mid + 1
result = mid
else:
right = mid - 1
print(result)
알고리즘적인 관점에서 이 문제가 파라메트릭 서치 유형의 문제인 근거는 파라메트릭 서치를 사용하기 위한 조건들을 모두 만족하기 때문이다.
1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우
2) 가능한 해의 영역이 연속적이어야 한다.
백준 2512번: 예산
백준 2805번: 나무 자르기
백준 2470번: 두 용액
https://sarah950716.tistory.com/16 [주니어 개발자의 대나무숲]
도서 - 이것이 취업을 위한 코딩 테스트다 with 파이썬 (저자: 나동빈)