Tutorial: 이진탐색 응용 (Binary Search on Answer) timer 1s memory 512MB

1) 매개변수탐색(또는 "Binary Search on Answer")

사실 매개변수탐색(Parametric Search)라는 용어는 한국 PS(Problem Solving) 커뮤니티에서 보통 "정답을 직접 구하는 대신, 정답을 가정하여 그것이 가능한지 판별하고, 그 경계값을 이분 탐색으로 찾는 테크닉"을 의미하는 용어로 널리 사용하고는 있지만, 국제적으로는 더 넓거나 다른 의미로 사용되고 있다. 좀더 정확한 용어로는 "Binary Search on Answer", "Binary Search on the Answer" 이다. 한국과 일본을 제외한 곳에서는 대부분 해당 용어를 사용한다. 편의상 여기서는 매개변수탐색이라고 사용한다.

매개변수탐색의 아이디어는 다음과 같다.

• 우리가 구하고 싶은 값(예: 최소 비용, 최대 거리 등)을 직접 계산하기는 어렵다.

• 대신 그 값이 될 수 있는 숫자 구간 [low, high]를 먼저 잡는다.

• 그 구간 안에서 이분 탐색을 하면서 “이 값 이상/이하로 문제를 만족시킬 수 있는가?”를 판정하는 함수를 이용해 최적의 값을 찾는다.

이 방법이 성립하려면 핵심 조건이 두 가지 있다.

1. 단조성이 있어야 한다.
   정답 후보 값 X에 대해 “X로 문제를 만족시킬 수 있는가?”를 판정할 수 있고, X가 커지거나 작아질수록 그 판정 결과가 한 방향으로만 변해야 한다.

   예를 들어 chk(X)가 “X 이하의 비용으로 이 일을 할 수 있는가?”라고 하자.

   • 만약 어떤 X에서 chk(X) = True라면, 그보다 더 큰 예산 Y(≥ X)에서는 당연히 True여야 한다.

   • 반대로 어떤 X에서 chk(X) = False라면, 그보다 더 작은 예산 Z(≤ X)에서도 False여야 한다.

   이렇게 True 영역과 False 영역이 한 번만 바뀌고 경계가 한 덩어리로 붙어 있는 성질을 단조성이라고 한다.
   단조성이 깨지면(즉 True-False-True처럼 들쭉날쭉하면) 이분 탐색으로 경계를 찾을 수 없다.

2. 판정 함수를 빠르게 계산할 수 있어야 한다.
   chk(X)와 같이 “X가 주어졌을 때 조건을 만족하는가?”를 True/False로 빠르게 판정하는 함수를 만든다.

   일반적으로 O(N) 또는 O(N log N)정도면 충분히 빠르다고 본다.

이 두 조건을 만족시키는 구조가 갖춰지면, 정답 후보 구간 [low, high]에서 이분탐색을 하면서 chk(mid)의 결과에 따라 구간을 절반씩 줄여 나가 최적의 값을 찾을 수 있다.

• 최대화 문제에서는 chk(mid) == True이면 더 큰 값을 시도하고, False이면 값을 줄인다.

• 최소화 문제에서는 그 반대로 움직인다.

2) 예시를 기반으로 설명

8개의 정수로 구성된 정렬된 수열 A=\{2,3,5,7,11,13,17,23\}이 주어졌을 때, 해당 수열에서 어떤 정수 X 보다 크거나 같은 값 중 최솟값을 찾는다고 하면 아래와 같이 진행 할 수 있다.

• 첫 번째 예제로 X=12인 경우, 각 수열에 대하여 조건을 만족하는 원소는 O, 아닌 원소는 X로 표현하면 다음과 같다: \{X,X,X,X,X,O,O,O\}

  탐색해야하는 인덱스의 범위는 0 부터 7 까지 이기에, low = 0, high = 7 로 탐색 범위를 설정하고 mid=3를 확인해본다. A[3]은 조건을 만족하지 못하므로 보다 작은 A[0], A[1], A[2] 또한 조건을 만족하지 못한다는 것을 바로 알 수 있다. 이제 탐색을 해야하는 범위는 4 부터 7 까지다.

  low = 4, high = 7 로 탐색 범위를 재설정하고 mid=5를 확인해본다. A[5]는 조건을 만족하기 때문에 보다 큰 A[6], A[7] 또한 조건을 만족한다는 것을 바로 알 수 있다. 이제 탐색을 해야하는 범위는 4 부터 4 까지다.

  low = 4, high = 4 로 탐색 범위를 재설정하고 mid=4를 확인해본다. A[4]는 조건을 만족하지 못하기 때문에 low를 늘려 탐색을 해야하는 범위를 low = 5, high = 4 로 수정한다.

  이제 low가 high 보다 커졌기에 탐색을 종료한다 \rightarrow 정답은 low = 5에 위치한다.

• 두 번째 예제로 X=10인 경우, 각 수열에 대하여 조건을 만족하는 원소는 O, 아닌 원소는 X로 표현하면 다음과 같다: \{X,X,X,X,O,O,O,O\}

  탐색해야하는 인덱스의 범위는 0 부터 7 까지 이기에, low = 0, high = 7 로 탐색 범위를 설정하고 mid=3를 확인해본다. A[3]은 조건을 만족하지 못하므로 보다 작은 A[0], A[1], A[2] 또한 조건을 만족하지 못한다는 것을 바로 알 수 있다. 이제 탐색을 해야하는 범위는 4 부터 7 까지다.

  low = 4, high = 7 로 탐색 범위를 재설정하고 mid=5를 확인해본다. A[5]는 조건을 만족하기 때문에 보다 큰 A[6], A[7] 또한 조건을 만족한다는 것을 바로 알 수 있다. 이제 탐색을 해야하는 범위는 4 부터 4 까지다.

  low = 4, high = 4 로 탐색 범위를 재설정하고 mid=4를 확인해본다. A[4]는 조건을 만족하기 때문에 high를 줄여 탐색을 해야하는 범위를 low = 4, high = 3 으로 수정한다.

  이제 low가 high 보다 커졌기에 탐색을 종료한다 \rightarrow 정답은 low = 4에 위치한다.

• 위 예제와 같이 작은 값이 조건을 만족하지 못하고, 큰 값이 조건을 만족하는 경우, low는 조건을 만족하는 곳으로 이동하고, high는 조건을 만족하지 않는 곳으로 이동하는 경향을 보인다.
  그렇게 진행하다 보면 결국 탐색이 끝나고 답이 low에 위치함을 관찰할 수 있다.

• 반대로 작은 값이 조건을 만족하고, 큰 값이 조건을 만족하지 못하는 경우는 답이 high에 위치한다.

3) 예시 코드

int A[8] = {2, 3, 5, 7, 11, 13, 17, 23};
int X = 12;

bool chk(int mid) {
    if (A[mid] >= X) return true;
    return false;
}

int parametricSearch() {
    int low = 0, high = 7;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (chk(mid)) high = mid - 1;
        else          low  = mid + 1;
    }
    return low;
}

A = [2, 3, 5, 7, 11, 13, 17, 23]
X = 12

def chk(mid):
    if A[mid] >= X: return True
    return False

def parametric_search():
    low, high = 0, 7
    while low <= high:
        mid = (low + high) // 2
        if chk(mid): high = mid - 1
        else:        low  = mid + 1
    return low

해당 예시와 같이 chk(mid) 함수가 짧은 경우 함수를 따로 만들지 않는 것이 더 일반적일 수 있으나, 대부분의 매개변수탐색 문제에서 chk(mid) 함수가 이처럼 짧은 경우는 드물다.

아래 문제를 풀어보며 감을 잡아보자.

<연습문제>

정올이는 친구들에게 사탕을 나누어 주려고 한다.

정올이에게는 N개의 상자가 있고, i번째 상자에는 A_i개의 사탕이 들어 있다.

정올이는 사탕을 다음과 같은 방식으로 나누어 준다.

• 하루에 모든 상자에서 동일하게 X개 이하의 사탕을 꺼낼 수 있다.

• 단, 어떤 상자에 남은 사탕이 X개보다 적다면, 그 상자에서는 남은 사탕만 모두 꺼낸다.

이렇게 하루 동안 꺼낼 수 있는 사탕의 총합을 이용해, 정올이는 총 T개 이상의 사탕을 꺼내고 싶다.

하루에 꺼낼 수 있는 최대 사탕 수 X의 최솟값을 구하여라.