Parametric Search(Binary Search on Answer)
Binary Search on Answer는 배열에서 특정 값을 찾는 일반적인 이분 탐색과 달리, 정답이 될 수 있는 값의 범위 자체를 이분 탐색하는 기법이다.
1. 핵심 개념
일반 Binary Search:
정렬된 배열에서 특정 원소를 찾음Binary Search on Answer:
정답이 존재하는 범위 [L, R]에서
조건을 만족하는 최소값 / 최대값을 찾음핵심 조건은 2개다.
① 정답의 범위를 정할 수 있어야 함
L <= Answer <= R예를 들어
n² < X를 만족하는 최대 n이라면 대략
0 <= n <= X로 탐색 범위를 잡을 수 있다.
② 조건이 단조성(Monotonic)을 가져야 함
어떤 mid가 조건을 만족하는지 검사했을 때 결과가 이런 식이어야 한다.
T T T T T F F F F
↑
경계또는 반대로
F F F F T T T T T
↑
경계즉, 특정 지점을 기준으로 조건의 결과가 한 번만 바뀌어야 한다.
2. 간단한 예제
문제:
n² < 101을 만족하는 가장 큰 양의 정수n을 찾아라.
정답은
10² = 100 < 101 → 가능
11² = 121 > 101 → 불가능
Answer = 10이다.
완전 탐색하면:
for (int n = 0; n <= X; n++)
{
if (n * n < X)
answer = n;
}시간복잡도:
O(X)하지만 조건을 보면:
n = 0 → true
n = 1 → true
...
n = 10 → true
n = 11 → false
n = 12 → false
...즉,
T T T T ... T | F F F ...
↑
Answer라는 단조성이 존재한다. 따라서 Binary Search를 사용할 수 있다.
3. 시간복잡도
탐색 범위가
[L, R]이고 check()의 시간복잡도가 O(N)이라면 전체 시간복잡도는 보통
O(N log(R - L))이다.
4. 일반 Binary Search와 차이
| 일반 Binary Search | Binary Search on Answer |
|---|---|
| 배열에서 값을 찾음 | 정답의 범위를 탐색 |
arr[mid] 검사 | check(mid) 검사 |
| 정렬된 배열 필요 | 조건의 단조성 필요 |
| 특정 값 찾기 | 최소/최대 가능한 답 찾기 |
