정의
매개변수 탐색이란 이분탐색을 사용하여 조건을 만족하는 최솟값/최댓값을 찾는 자료구조이다.
매개변수 탐색
- 매개변수 탐색에서 최종적으로 구한 최솟값/최댓값이 찾아야 하는 매개변수이다.
- 결정함수 Fn(param)이 어떠한 조건을 만족하면 T, 만족하지 않으면 F를 반환한다고 정의해 보자.
이분 탐색에서 배열이 오름차순이기 때문에 매개변수 param의 결과인 결정함수 Fn(param)는 연속적이다. - 연속적인 결정함수에서 중간에 T → F 또는 F → T로 바뀌는 부분이 찾아야 할 값이다.
매개변수 탐색을 위한 이분탐색을 할 때, (lo+1 < hi)으로 수행하면 최종적으로 아래와 같이 lo와 hi를 얻을 수 있다.
매개변수 탐색으로 최솟값 구하기
param의 최솟값은 T를 만족하는 값 중에서 가장 작은 값이다.
- 만약 Fn(param)의 값이 참이면 param의 오른쪽 구간이 모두 T이므로 왼쪽 구간을 탐색한다.
- 반대로 거짓이면 param의 왼쪽 구간이 모두 F이므로 오른쪽 구간을 탐색한다.
- 이렇게 구간을 좁히다 보면 아래와 같은 결과를 얻을 수 있다.
예시코드
int min_parametric_search(int lo, int hi) {
lo -= 1; // 반례
while(lo+1 < hi) {
int mid = (lo+hi)/2;
if(fn(mid))
hi = mid; // 참이면 왼쪽 구간 탐색
else
lo = mid; // 거짓이면 오른쪽 구간 탐색
}
return hi; // 최솟값 반환
}※ 주의사항
- while(lo + 1 < hi)의 특성상 lo가 정답인 경우에 hi는 lo가 될 수 없음
- 해결 방안은 초기 범위를 lo = min - 1, hi = max 으로 설정
매개변수 탐색으로 최댓값 구하기
param의 최댓값은 T를 만족하는 값 중에서 가장 큰 값이다.
- 만약 Fn(param)의 값이 참이면 param의 왼쪽 구간이 모두 T이므로 오른쪽 구간을 탐색한다.
- 반대로 거짓이면 param의 오른쪽 구간이 모두 F이므로 왼쪽 구간을 탐색한다.
예시코드
int max_parametric_search(int lo, int hi) {
hi += 1; // 반례
while(lo+1 < hi) {
int mid = (lo+hi)/2;
if(fn(mid))
lo = mid; // 참이면 오른쪽 구간 탐색
else
hi = mid; // 거짓이면 왼쪽 구간 탐색
}
return lo; // 최댓값 반환
}※ 주의사항
- while(lo + 1 < hi)의 특성상 hi가 정답인 경우에 lo는 hi가 될 수 없음
- 해결 방안은 초기 범위를 lo = min, hi = max + 1 으로 설정