이분 탐색(Binary Search) 문제들 중 최적화를 위해 결정 문제로 바꿔서 푸는 매개변수 탐색 문제가 있다. 가끔 나오는 문제다보니 풀 때마다 구간의 정의(lo와 hi) 및 결정 함수를 구현하는데 삽질을 많이해서 정리할 필요성을 느낌.
이 글을 읽기 전 알아야 할 정보
- 이분 탐색 구현 방법
- 매개 변수 탐색의 개념
구글링하면 자료가 많이 나오니 개념에 대한 설명은 여기로 대체하겠다. (굉장히 설명을 잘 해주셨다.)
매개 변수 탐색에서 마주한 문제는 매개변수의 구간을 정의하는 부분과 결정 함수를 구현하는 부분이다.
먼저, 매개변수의 구간을 정의한다는 것은 이분 탐색에서 lo 와 hi 의 의미를 아는 것에서 출발할 필요가 있다.
int binary_search(int lo, int hi, int value) {
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (A[mid] <= value) lo = mid;
else hi = mid;
}
return A[lo];
}탐색할 배열 A가 정렬되어 있으며 value 는 항상 A 에 있다고 가정한다.
따라서 lo < hi 에서 이진 탐색을 수행하므로 while 문에 들어가기 전에 A[lo] < A[hi] 가 성립한다.
while 문에 들어갈 때 lo + 1 < hi 라는 조건때문에 반복문 불변식으로 A[lo] < A[hi] 가 항상 성립한다.
- A[mid] <= value 여서 lo = mid 가 되는 경우, mid < hi 이므로 A[lo] < A[hi] 가 성립한다.
- A[mid] > value 여서 hi = mid 가 되는 경우, lo < mid 이므로 A[lo] < A[hi] 가 성립한다.
- lo 와 hi 가 1 씩 차이나면 mid <= hi 또는 lo <= mid 가 되어 불변식이 깨질 수 있는데, 조건은 항상 hi - lo > 1 이기 때문에 그럴 일은 없다.
while 문에서 빠져나왔을 때는 lo + 1 == hi 일 텐데 어쨌든 lo < hi 이므로 A[lo] < A[hi] 가 성립한다.
(이 조건이 깨지는 경우는 lo < hi 와 같이 잘못된 조건식으로 lo > hi 가 된 상태로 반복문을 빠져나올 때이다. lo + 1 < hi 를 기억하자.)
여기서 A[mid] <= value 일 때 lo = mid 이므로 반환하는 A[lo] 는 항상 value 이다. 만약 조건을 A[mid] < value 로 했다면 A[hi] 를 반환해야 할 것이다. 즉, 값을 찾는 조건에 따라 lo 와 hi 중 하나가 정답이 된다.
| 1 | 2 | 3 | 4 | 5 | 6 |
↑ ↑
lo hi이분 탐색에서 while (lo + 1 < hi) 조건으로 탐색할 경우 최종 lo 와 hi 는 위와 같은 모습이다.
다시 매개 변수 탐색으로 돌아와서, 일반적으로 문제에서 최종적으로 구해야 하는 최솟값/최댓값이 찾아야 하는 매개변수이다. 이를 param 이라고 하겠다. 그리고 결정 함수를 다음과 같이 정의하겠다.
fn(param) := param 이 어떤 조건을 만족하면 true를 반환하고 아니면 false를 반환
여기서 param 의 범위는 이분 탐색에서 배열 A가 오름차순이라고 했던 것과 유사하게 연속이어야 하는데, param 값이 연속인 것 말고도 fn(param) 의 결과도 연속이어야 한다.
즉, param 가 구간 [lo, hi] 사이의 값일 때, fn(param) 는 [false, false, ..., false, true, ..., true, true] 또는 [true, true, ..., true, false, ..., false, false] 여야 한다. 중간에 false -> true 또는 true -> false 로 바뀌는 부분이 있는데 이 부분은 1번만 존재해야 하며, 만약 여러 개 있다면 이분 탐색이 아니라 삼분 탐색 등 다른 방법으로 문제를 해결해야 할 것이다. 이분 탐색은 실제로 1차 함수 f 를 가정하고 f(x) < 0 에서 f(x) > 0 으로 바뀌는 f(x) = 0 을 만족하는 x 값을 찾는 방법이다. 0은 그냥 예시이다. 정해진 값 y 가 있다면 0이 아니라 y가 될 것이다.
fn(param) 의 결과 중간에 false -> true 또는 true -> false 로 바뀌는 부분이 있는데, 여기서 true 를 반환하는 param 이 찾고자 하는 최솟값/최댓값이다.
어떤 조건을 만족하는 param 의 최솟값(=answer)을 찾는 문제를 생각해보자.
fn(param) 은 연속이라고 했기 때문에 param >= answer 에 대해 fn(param) 은 항상 true 일 것이다. param 은 오름차순이니 fn(param) 의 결과는 param 에 따라 [false, false, ..., false, true, ..., true, true] 이고, 다음이 성립한다.
- fn(answer - 1) = false
- fn(answer) = true
- fn(answer + 1) = true
여기서 param 의 구간을 [lo, hi] 라고 정의할 때 while(lo + 1 < hi) 조건으로 반복문을 돌리면 최종적으로 아래와 같이 lo 와 hi 를 얻게 된다.
| f | ... | f | t | ... | t |
↑ ↑
lo hiparam 의 구간이 [1, 6] 이라면 위와 아래는 의미가 동일하다. 단지 위의 배열은 fn(param) 의 결과이고 아래의 배열은 param 의 배열이라는 점이 차이이다.
| 1 | 2 | 3 | 4 | 5 | 6 |
↑ ↑
lo hi어떤 조건을 만족하는 param 의 최솟값은 lo 가 아니라 hi 임을 알 수 있다. 따라서 이 경우에는 lo 가 아닌 hi 를 반환해야 한다.
bool fn(int param);
int binary_search(int lo, int hi) {
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (fn(mid)) hi = mid; // 참이면 왼쪽 구간을 탐색
else lo = mid; // 거짓이면 오른쪽 구간을 탐색
}
return hi;
}구간을 좁히는 조건문을 보면, 조건을 만족할 때마다 왼쪽 구간을 탐색하는데 그 이유는 현재 param 에 대해 fn 이 true 이면 오른쪽 구간은 전부 true 이니 볼 필요가 없기 때문이다. false -> true 는 현재 param 보다 왼쪽에 위치하게 된다.
반대로 조건을 만족하지 않으면 현재 param 에 대해 fn 이 false 이므로 왼쪽 구간은 전부 false 임을 알 수 있다. 따라서 false -> true 는 현재 param 보다 오른쪽에 위치하게 된다.
주의사항: 처음에 lo 와 hi 구간을 정의할 때, lo = 구간의 최솟값 - 1 로, hi = 구간의 최댓값 으로 정의해야 한다. hi 를 반환하기 때문에 lo = 구간의 최솟값이면 hi 는 구간의 최솟값이 될 수 없어서 (lo + 1 < hi 라는 조건에 의해) 구간의 최솟값이 정답일 경우 답을 반환할 수 없게 된다.
어떤 조건을 만족하는 param 의 최댓값(=answer)을 찾는 문제를 생각해보자.
fn(param) 은 연속이라고 했기 때문에 param <= answer 에 대해 fn(param) 은 항상 true 일 것이다. param 은 오름차순이니 fn(param) 의 결과는 param 에 따라 [true, true, ..., true, false, ..., false, false] 이고, 다음이 성립한다.
- fn(answer - 1) = true
- fn(answer) = true
- fn(answer + 1) = false
여기서 param 의 구간을 [lo, hi] 라고 정의할 때 while(lo + 1 < hi) 조건으로 반복문을 돌리면 최종적으로 아래와 같이 lo 와 hi 를 얻게 된다.
| t | ... | t | f | ... | f |
↑ ↑
lo hi최솟값 구할 때랑 배열이 반대로 결과가 나온다. 어떤 조건을 만족하는 param 의 최댓값은 lo 임을 알 수 있다. 따라서 이 경우에는 lo를 반환해야 한다.
bool fn(int param);
int binary_search(int lo, int hi) {
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (fn(mid)) lo = mid; // 참이면 오른쪽 구간을 탐색
else hi = mid; // 거짓이면 왼쪽 구간을 탐색
}
return lo;
}배열이 반대이기 때문에 탐색하는 방법도 반대라는 것에 주의하자.
구간을 좁히는 조건문을 보면, 조건을 만족할 때마다 오른쪽 구간을 탐색하는데 그 이유는 현재 param 에 대해 fn 이 true 이면 왼쪽 구간은 전부 true 이니 볼 필요가 없기 때문이다. true -> false 는 현재 param 보다 오른쪽에 위치하게 된다.
반대로 조건을 만족하지 않으면 현재 param 에 대해 fn 이 false 이므로 오른쪽 구간은 전부 false 임을 알 수 있다. 따라서 true -> false 는 현재 param 보다 왼쪽에 위치하게 된다.
주의사항: 처음에 lo 와 hi 구간을 정의할 때, lo = 구간의 최솟값 으로, hi = 구간의 최댓값 + 1 로 정의해야 한다. lo 를 반환하기 때문에 hi 가 구간의 최댓값이면 lo 는 구간의 최댓값이 정답이어도 lo + 1 < hi 라는 조건 때문에 반환할 수 없게 된다.
정리하자면,
- 문제에서 최종적으로 찾고자하는 최솟값/최댓값을 매개변수로 본다.
- 결정 함수를 정의하고 구현했을 때 결과 배열이 연속인지 확인한다.
- 최솟값이면 결정 함수의 결과가 [f,f,...,t,t] 에서 f->t 로 바뀌는 부분을 찾는다.
- 결정 함수가 true 이면, 오른쪽 구간은 전부 true 이니, f->t 가 있는 왼쪽 구간을 탐색한다. hi = mid
- 결정 함수가 false 이면, 왼쪽 구간은 전부 false 이니, f->t 가 있는 오른쪽 구간을 탐색한다. lo = mid
- 반복문을 빠져나오면, lo < hi 이므로 fn(lo) = false, fn(hi) = true 이다. 따라서 hi를 반환한다.
- 최댓값이면 결정 함수의 결과가 [t,t,...,f,f] 에서 t->f 로 바뀌는 부분을 찾는다.
- 결정 함수가 true 이면, 왼쪽 구간은 전부 true 이니, t->f 가 있는 오른쪽 구간을 탐색한다. lo = mid
- 결정 함수가 false 이면, 오른쪽 구간은 전부 false 이니, t->f 가 있는 왼쪽 구간을 탐색한다. hi = mid
- 반복문을 빠져나오면, lo < hi 이므로 fn(lo) = true, fn(hi) = false 이다. 따라서 lo 를 반환한다.
결정 함수의 구현
fn(param) := param 이 어떤 조건을 만족하면 true를 반환하고 아니면 false를 반환
"어떤 조건을 만족" 하는 것은 param 이상/이하일 때 M개의 그룹으로 나눌 수 있는가 또는 M개로 분할할 수 있는가 등을 묻는 것이라고 볼 수 있다. (대개 문제들이 그렇다.) 여기서 fn(param)의 결과 배열에 따라 즉, 최솟값/최댓값인지에 따라 M 에 대한 조건이 달라진다.
두 가지 흔한 예제를 살펴보자.
예제1) BOJ 2110번: 공유기 설치
문제 요약: C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대화
"가장 인접한 두 공유기의 거리를 최대(=answer)화" 하라는 의미는 모든 인접한 두 공유기의 간격이 answer 보다는 크거나 같아야 함을 의미한다. param 을 두 공유기의 간격이라고 하면 결정 함수는 다음과 같이 정의할 수 있다.
param := 두 공유기의 간격
fn(param) := 인접한 두 공유기 사이의 거리 >= param 이 되도록 C 개의 공유기를 설치할 수 있는가
위와 같이 결정 함수를 정의하면 최대 param (=answer) 이하로는 모든 fn(param) = true 가 되므로 이분 탐색으로 문제를 해결할 수 있게 된다. 즉, 거리가 3이상이 되도록 C개를 설치할 수 있으면 당연히 거리가 2이상이 되도록 C개를 설치할 수 있다.
이제 fn(param) 의 결과 배열이 [true, true, ..., true, false, ..., false, false] 인 것을 알았다.
true -> false 를 찾자.
int search() {
// X는 오름차순 정렬이라 가정
int lo = 1, hi = X[N-1] + 1;
while (lo + 1 < hi) {
int mid = (lo + hi) << 1;
if (fn(mid)) lo = mid; // 현재 cond 보다 오른쪽 구간에 t->f 가 존재
else hi = mid; // 현재 cond 보다 왼쪽 구간에 t->f 가 존재
}
return lo; // 반복문 불변식: fn(lo) = t, fn(hi) = f.
}결정 함수를 구현할 때는 설치된 공유기 개수가 C 개 인지 확인하는 조건에 주의해야 한다.
두 집 사이의 거리 >= param 을 만족할 때마다 공유기를 설치한다고 하자.
공유기가 C개 보다 많이 설치된 경우, param 이 작아서 조건을 만족하는 경우가 많다는 의미로, param을 늘려주어야 한다. 따라서 true 를 반환해야 현재 param 보다 오른쪽 구간에서 param 을 탐색할 수 있다.
공유기가 C개 보다 적게 설치된 경우, param 이 커서 조건을 만족하는 경우가 적다는 의미로, param을 줄여야 한다. 따라서 false 를 반환해야 현재 param 보다 왼쪽 구간에서 param 을 탐색할 수 있다.
공유기 개수가 C개이면 조건을 만족하니 true 를 반환한다.
bool fn(int param) {
int cnt = 1, prev = 0; // 첫번째 집에 공유기를 설치했다고 가정
for (int i = 1; i < N; i++) {
if (X[i] - X[prev] >= param) {
cnt++;
prev = i;
}
}
return cnt >= C;
}
예제2) BOJ 2613: 숫자구슬
문제 요약: M개의 그룹으로 N개의 숫자구슬을 나눌 때, 그룹의 합의 최댓값을 최소화
param := 그룹의 합
fn(param) := 그룹의 합 <= param 이 되도록 M 개의 그룹으로 나눌 수 있는가
위와 같이 결정 함수를 정의하면 최소 param (=answer) 이상으로는 모든 fn(param) = true 가 되므로 이분 탐색으로 문제를 해결할 수 있다. 예를 들어, 그룹의 합이 4 이하가 되도록 M 개의 그룹으로 나눌 수 있으면, 합이 5 이하가 되도록 M 개의 그룹으로 나눌 수 있다.
이제 fn(param) 의 결과 배열이 [false, false, ..., false, true, ..., true, true] 인 것을 알았다.
false -> true 를 찾자.
int search() {
int lo = 0, hi = accumulate(A, A + N, 0);
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (!fn(mid)) lo = mid; // 현재 param 보다 오른쪽 구간에 f -> t 가 존재
else hi = mid; // 현재 param 보다 왼쪽 구간에 f -> t 가 존재
}
return hi;
}결정 함수를 구현할 때는 그룹의 개수가 M 개인지 확인하는 조건에 주의해야 한다.
숫자 구슬의 합 > param 을 만족할 때마다 그룹을 나눈다고 하자.
그룹이 M 개 보다 많이 나뉘어진 경우, param 이 작아서 조건을 만족하는 경우가 많다는 의미로, param 을 늘려야 한다. 따라서 false 를 반환해야 현재 param보다 오른쪽 구간에서 param 을 탐색한다.
그룹이 M 개 보다 적게 나뉘어진 경우, param 이 커서 조건을 만족하는 경우가 적다는 의미로, param 을 줄여야 한다. 따라서 true 를 반환해야 현재 param보다 왼쪽 구간에서 param 을 탐색한다.
딱 M개인 경우 조건을 만족하므로 true 를 반환한다.
bool fn(int param) {
int cnt = 1; // 그룹의 개수는 1개부터 시작
for (int i = 0, psum = 0; i < N; i++) {
if (A[i] > param) return false; // 숫자구슬 1개가 이미 param 을 넘어서면 false
if (psum + A[i] > param) {
psum = A[i];
cnt++;
} else psum += A[i];
}
return cnt <= M;
}참고로 A[i] > param 일 때는 무조건 false 를 반환해야 한다. 아니면 계속 반복문이 수행될 수 있어서 결과가 잘못나올 수 있다.
이 문제는 그룹마다 구슬이 몇 개 들어있는지도 출력해야 하는데, 최솟값을 찾고나면 최솟값을 넘지 않도록 그룹 지은 다음 그룹의 개수가 M 보다 작으면 그룹의 합이 최대인 그룹을 제외하고 그룹 내 구슬을 1개씩 다른 그룹으로 나눠주면 된다.
기타 예제)
'Algorithm > Theory' 카테고리의 다른 글
| 접미사 배열(Suffix Array)과 최장 공통 접두사 배열(LCP Array) (0) | 2021.01.28 |
|---|---|
| 계산기하 - vector 연산 (0) | 2020.02.23 |
| 소인수분해, 소수 판별법, 에라토스테네스의 체 (0) | 2019.05.16 |