binary search and parametric search

나에게 코딩테스트를 준비하면서 가장 어려운 부분이 어디냐고 묻는다면 나는 단언컨대 binary search와 parametric search를

말할 것 같다

말했을 것이다. 꼭 정리하겠다고 마음먹은 부분인 만큼, 간단하게나마 정리해보고자 한다(원리를 자세히 설명해준 롸와 PS에서 이용할 수 있는 팁을 준 채완이, 백발이에게 고마움을 표한다).

이 글에는 약간의 오류, 특히 용어상의 오류가 발견될 수 있다. 지속해서 수정해나가는 중이므로 참고용으로만 보면 된다.

1. binary search vs parametric search

결정 문제(decision problem, 판정 문제)는 수학적으로 계산 가능한 문제 중 결과를 YES 또는 NO의 두 가지로 답할 수 있는 문제를 의미한다. 하지만 우리가 만나는 많은 문제는 최적화 문제(mathematical optimization problem)로서, 문제에서 제시되는 제약 내에서 어떤 변수가 가질 수 있는 최댓값 또는 최솟값을 요구하는 문제이다. 우리는 이러한 최적화 문제를 결정 문제로 바꾸어, 비교적 쉽고 빠른 방법으로 문제를 해결할 수 있다. 이를 parametric search라고 할 수 있다.

처음부터 특정 조건을 만족하는 값 또는 범위가 아닌 특정 값을 찾으라고 한다면, 즉 주어진 문제 자체가 결정 문제라면, 이에 대해서는 곧바로 binary search를 이용하면 된다. 즉, '이분 탐색 문제'라고 하면, 최적화 문제를 결정 문제로 바꾸는 과정이 존재하지 않는다고 보아도 된다.

한편, 우리는 어느 경우이든지 간에 결정 문제를 풀게 된다고 볼 수 있다. 이 때 주어진 구간은 두 구간으로 나뉘는데, 우리는 곧 해당 구간의 경계를 찾음으로써 문제를 해결할 수 있다. 그리고 그 경계를 찾는 과정이 소위 binary search algorithm이다.

2. binary search algorithm

문제를 보다 익숙하게 바꾸어서, 어떤 배열 A에서 특정 값 k를 찾는다고 하자.

닫힌 구간을 사용한다고 할 때, 무지성으로 잡곤 하는, left, right는 어떤 의미를 갖는가? [left, right] 구간 내에 우리가 찾고자 하는 k가 있다고 상정하는 것이다. 사실 이는 binary search를 배웠다면 그 누구라도 당연하게 배웠을 사실이며, 알고 있을 사실이다. 그럼에도 불구하고 나는 이러한 '당연한' 사실을 소홀히 여겼고, 그래서 문제 해결 과정에서 어려움을 겪었던 게 아닐까 한다. 무슨 일이 있어도 [left, right] 사이에 k가 존재한다는 것을 잊어서는 안 된다(정확히 말하자면, [left, right]에 k가 존재할 수도 있고 존재하지 않을 수도 있다. 다만, 절대로 (-∞, left), (right, ∞)에는 k가 존재하지 않는다).

여기서 while (left <= right)가 나온다. left <= right라 함은, 구간의 길이가 1 이상인 것을 의미하는데, 만약 left > right가 되는 순간 해당 구간 내에는 k가 존재하지 않는다는 것을 의미하고, 따라서 알고리즘은 종료되어야 한다.

그리고 A[mid] > k라면, mid는 정답 범위에 결코 포함되지 않으므로 이를 제외해야 한다. 따라서 right = mid - 1을 통해서 mid 이후뿐만 아니라 mid까지도 정답 범위에서 제외시켜야 한다. A[mid] < k라면, 마찬가지로, mid 이전과 mid는 정답 범위에 포함되지 않으므로 left = mid + 1을 통해 정답 범위를 축소시켜준다.

내가 했던 고민은 여기에 있다. 구간의 길이가 2일 때에는, left = mid일 수도 있는데, A[left] == k이면 어떡하지?

이는 사실 left, right의 의미를 제대로 이해했다면 결코로 나와서는 안될 질문이었다. 구간의 길이가 1인 경우까지도 생각한다면 mid의 범위는 left <= mid <= right일 것이고, mid가 정답 범위에서 포함되지 않는다면 left 또는 right는 당연히 제외되는 것이 타당하기 때문이다. A[mid] == k이면? 여기선 아무도 고민하지 않는다. mid가 우리가 찾던 정답이니까 말이다.

3. lower bound, upper bound

lower bound를 먼저 생각해보자. lower bound는 A[lb - 1] < k <= A[lb]인 lb, 또는 A[lb] >= k인 최소의 lb를 뜻한다. 여기서도 left, right의 의미는 그대로 유지된다. 닫힌 구간을 그대로 사용한다고 할 때, [left, right] 사이에 lower bound가 존재한다고 상정하는 것이다.

그렇다면 A[mid] > k인 경우에는 어떤가? [2, 3, 3, 4]에서 k = 2, mid = 1인 상태라면? A[1] = 3 >= 2이므로 1은 후보군에 포함된다. 다만 A[1] 이후의 값들, 즉 A[2] = 3, A[3] = 4는 모두 3과 같거나 3보다 크다. 이들은 정답 범위를 찾는다는 관점에서, 일말의 정답이 될 가능성을 갖지 못한다. 하다못해 [0, 3, 3, 4]일지라도 lower bound는 1이지, 2나 3이 될 수는 없기 때문이다. 따라서 right = mid + 1이 아니라, right = mid로 한다.

그리고 위 설명은 A[mid] = k일 때에도 그대로 적용된다. 이 때 mid는 강력한 정답 후보이지만, A[mid - 1] = A[mid]라면, lower bound는 mid가 아니라 mid - 1이 된다. 따라서 right = mid로 바꾸어주고 끝낸다.

A[mid] < k인 경우는 어떨까? A[lb] >= k이어야 한다는, lower bound의 정의에서 완전히 벗어나므로 이 때 A[mid]와 그 이전의 값들은 정답 범위에서 제외시켜야 한다. 따라서 left = mid + 1로 바꾸어준다.

이렇게 진행하다가, left = right인 순간에는 어떻게 해야할까? 이 때에는 mid = left = right로서, 다음의 예를 생각해보자.

[3, 3, 3, 3]이고 k = 3인 경우에, left = 0, right = 3부터 시작해서, 오른쪽을 점점 제외해나가다보면 left = right = 0이 되어버린다. 여기서 더이상 진척이 없으므로 left = right인 경우에는, 해당 구간 내에 답이 있는 경우이므로, mid가 곧 lower bound가 되므로 break해준다.

여기까지 잘 이해했다면 upper bound는 헷갈릴 것이 없다. 등호를 넣고 말고를 외울 게 아니라, 뭘 제외하고 뭘 포함시킬지만 고민해보면 되는 것이다.

A[mid] > k인 경우, mid는 upper bound의 후보이다. 단 이보다 오른쪽은 볼 필요가 없다. right = mid;

A[mid] == k인 경우, mid는 upper bound의 후보가 아니다. A[ub] > k이어야 하는데 같다니! mid를 포함해서 그 왼쪽을 모두 범위에서 제외시킨다. left = mid + 1;

A[mid] < k인 경우, mid는 upper bound의 후보가 아니다. left = mid + 1;

마찬가지로 left = right일 경우에는 별도의 처리를 진행해준다.

4. parametric search

lower bound와 upper bound를 찾는 과정이 binary search algorithm의 비교적 단순한 응용이었다면, 실제 문제를 푸는 데에 parametric search를 어떻게 이용하는지 생각해보자.

대표적인 문제는 BOJ 2805가 아닐까? noj.am/2805

이 문제를 처음 풀면서 가장 힘들었던 점은, 절단기에 지정할 높이 H가 클 수록 집에 들고갈 나무의 길이의 합이 작아진다는 것이다. 그래서 parametric search에 대한 사고 체계가 없던 나에겐 무척이나 힘든 문제였다.

하지만 이를 위에서 말한 개념들을 적용하면, 복잡해 보이던 많은 확인 과정들은 '결정함수'라는 하나의 함수에 압축시킬 수 있다.

나무 자르기 문제를 간단하게나마 시각화해보면 다음과 같다.

절단기에 지정할 높이의 최댓값을 구하는, 이 최적화 문제를, 다음과 같이, 결정 문제로 바꿀 수 있다.

"절단기에 지정할 높이가 h일 때, 집에 들고갈 나무의 길이의 합이 M 이상인가?"

위에서 결정 함수가, YES일 때 0, NO일 때 1을 반환한다고 생각하면 00...0011...11과 같은 형태가 된다. 그러면 우리가 해야 할 것은? 맞다. upper_bound(0) - 1을 구하면 된다.