Intro
이분 탐색 알고리즘은 컴퓨터 공학을 전공하지 않더라도 누구나 교양 시간에 배워봤을 만한 알고리즘입니다. 이분 탐색의 개념 자체는 직관적이지만 응용이 상당히 어렵습니다. 오늘은 이분 탐색과 그 활용에 대해 다뤄보겠습니다.
이분 탐색이란?
이분 탐색이 정확히 무엇일까요? 이분 탐색의 예시로 보통 업-다운 게임을 많이 사용하는데요, 진행자는 $1$부터 $100$까지의 정수 중 하나를 고르고, 질문자는 이 정수를 맞혀야 합니다. 질문자는 매 질문마다 정수를 하나 골라 질문하고, 진행자는 질문자가 고른 정수와 진행자가 고른 정수의 대소관계만을 대답해줍니다. 최소 횟수의 질문을 가지고 정답을 맞히고 싶다면, 어떤 전략을 취해야 할까요?
당신이 질문자라면, 맨 처음 $50$을 선택하고, 결과에 따라 계속 절반씩 줄여나가는 전략을 취하는 것이 합리적일 것입니다.
그러나 이 예시는 이분 탐색의 개념을 설명할 때 유용하겠지만, 업-다운 게임은 이분 탐색의 한 예시일 뿐, 실제로는 더 일반화된 방식으로 구현합니다.
탐색 범위가 추상적입니다.
$1$부터 $N$까지의 정수를, 정렬된 정수 배열 $A = [1, 2, \cdots, N]$로 먼저 환원시킨 후 생각해야 합니다.
종료 조건이 일반적이지 않습니다.
업-다운 게임에서는 찾으려는 값과 중앙값이 일치할 때 종료하지만, 일반적인 이분 탐색 구현에서는 그렇게 하지 않습니다. (만약 찾으려는 수가 배열에 없으면 어떻게 될까요? 무한 루프에 빠질 것입니다.)
그렇다면, 이분 탐색을 어떻게 정의해야 할까요?
- 정렬된 배열에서
- ‘예/아니오‘로 답할 수 있는 질문 $Q(m)$ (단, $m$은 중앙값)에 대하여
- $Q(m)$의 답이 참인 구간과 거짓인 구간의 경계를 찾는 것
으로 정의합시다. 이분 탐색을 매개 변수 탐색의 정의로 환원시킨 것입니다. 이제 이분 탐색은 단순히 탐색 범위를 반씩 줄여주는 역할만 하는 것이 아니라, 최소/최대를 구하는 최적화 문제를 빠르게 해결할 수 있는 도구가 될 수 있습니다.
이분 탐색의 구현
최적화 문제를 다루기에 앞서, 우선 이분 탐색이 어떻게 작동하는지 알아봅시다. 이분 탐색은 다음과 같은 Python 코드로 표현할 수 있습니다.
def Q(x: int) -> bool: # 질문 Q(x)에 대한 답을 계산해서 리턴
return (condition);
left = 0
right = N + 1
while left + 1 < right:
mid = (left + right) // 2; # 중앙은 floor로 구함
if Q(mid):
left = mid
else:
right = mid
편의상 0이상 left이하에 위치하는 구간이 condition을 만족하고, right이상 N + 1이하에 위치하는 구간이 condition을 만족하지 않는다고 합시다. while (left + 1 < right) 때문에 left와 right가 인덱스 1 차이로 맞닿을 때까지 반복하며 탐색할 구간을 반씩 줄입니다.
아까 예시로 들었던 업-다운 게임을 살짝 변형해 봅시다. $1$부터 $N=10$까지 정수를 가지고, 진행자가 $7$을 생각했다고 해봅시다. 진행자가 생각한 최소한의 정수가 얼마인지 찾는 최적화 문제를, 결정 문제들의 조합들로 재구성 해봅시다.
질문 $Q(x)$를 “$x$ 미만인가?“로 정의합시다. $Q(x)$가 작은 정수에 대해선 True였다가, 점점 큰 수를 넣다 보면 어느 순간 False를 반환할 것입니다. 이분 탐색의 목적은 바로 이 경계를 찾아내는 것입니다.
먼저, left = 0, right = 11로 놓습니다. 만약, 진행자가 $1$ 또는 $10$을 생각했더라도 left 구간과 right 구간의 경계를 명확하게 정의하기 위해 임의로 확장했습니다.
중앙값 mid는 $\textrm{mid} = \lfloor \frac{\textrm{left} + \textrm{right}}{2} \rfloor$, 정수 나눗셈은 버림으로 구현합니다. a[mid] = 5 입니다. $5 < 7$ 이므로 진행자는 ‘down’을 대답했을 것입니다. 따라서 질문 $Q(5)$의 답은 True가 되고, 배열이 정렬되어 있기 때문에, mid보다 앞 인덱스에 있는 정수들은 볼 필요도 없이 True인 구간에 포함됩니다. 따라서, mid는 left구간에 포함되어야 합니다.
이제 다시 mid를 새로 잡아봅시다.
a[mid] = 8입니다. $Q(8)$의 답은 $7 \le 8$이므로 False가 됩니다. 이번에는 mid가 right구간에 포함되어야겠죠?
종료될 때까지 반복합시다. 중앙값을 잡고 $Q(\textrm{mid})$가 True인지 False인지 비교합시다.
a[mid] = 6이고, $Q(6)$의 답은 $6 < 7$이므로 True입니다. left구간에 mid를 포함시켜줍시다.
마지막 비교입니다. a[mid] = 7이고, $7 \le 7$이므로 $Q(7)$은 False를 반환합니다. mid를 right구간에 포함시켜 주면,
두 구간의 경계가 맞닿게 되고, 탐색이 종료됩니다. $Q(x)$가 True인 최대 정수가 a[left]이고, False가 되는, 즉 $x$ 이상이 되는 최솟값이 a[right]가 됩니다. 따라서 이 문제의 정답은 a[right]가 됩니다!
탐색할 구간이 절반씩 줄어들기 때문에, $\frac{N}{2^k} \leq 1$을 만족하는 최소한의 정수 $k$가 탐색한 횟수가 됩니다. 부등식을 정리하면, $\lg N \leq k$, 시간복잡도는 $\mathcal{O}(\lg N)$이 됩니다. 로그 시간복잡도는 일반적으로 상수 시간복잡도 다음으로 뛰어난 퍼포먼스를 보여줍니다. $N=10^9$ 스케일만 되어도, $\lg10^9 = 29.8973\cdots$이므로, 선형 알고리즘보다 $10^7$배 이상 빠릅니다. 정말 좋은 알고리즘입니다.
이해를 점검하기 위해 연습문제를 하나 풀어봅시다.
BOJ 1920 - 수 찾기
$Q(x)$를 어떻게 해야 잘 구성할 수 있을지 고민해봅시다. 찾으려는 값 $X$가 어디 사이에 있는지는 이분탐색을 통해 알 수 있지만, 어떻게 하면 배열 안에 존재하는지를 판단할 수 있을까요?
Lower bound & Upper bound
배열에 같은 값이 여러 개 있으면 이분 탐색 결과가 어떻게 나올까요?
위 예시는 질문 $Q(x)$를 “$x$ 미만인가?“로 정의했습니다. 따라서 a[right]가 $x$를 초과하는 최초의 정수가 되는데요, 만약 $R(x)$를 “$x$ 이하인가?“로 정의하면 a[left]와 a[right] 둘 중 무엇이 정답이 될까요? 이 때는 a[left]가 $x$ 이하인 최대의 정수이므로 a[left]가 정답이 됩니다. 전자를 Lower bound, 후자를 Upper bound라고 합니다.
왼쪽의 하늘색이 바로 위의 문단에서 설명한 $Q(x)$를 이용한 Lower bound, 오른쪽의 주황색이 $R(x)$를 이용한 Upper bound입니다.
연습문제나 하나 풀어봅시다.BOJ 10816 - 숫자 카드 2
숫자 카드들을 정렬한 후 (Upper bound) $-$ (Lower bound) $+ 1$을 하면 어떤 카드가 몇 장 있는지 알 수 있습니다! 하지만 애초에 존재하지 않을 수도 있으니 위 문제를 먼저 풀어본 후 잘 구현해봅시다.
매개 변수 탐색 (Parametric Search)
초반에 언급했듯이, 제가 위에서 정의한 이분 탐색은 애초에 매개 변수 탐색으로 확장한 정의입니다. 원래의 이분 탐색은 특정한 값을 찾는 데 사용되지만, 매개 변수 탐색은 경계를 찾는 데 사용됩니다. 일반적으로, $1$부터 $N$까지의 범위 내에서 매개 변수 탐색을 수행할 때, $Q(x)$를 판단하는 데의 시간복잡도가 $\mathcal{O}(M)$이라고 하면, 총 시간복잡도는 $\mathcal{O}(\lg N)\cdot \mathcal{O}(M) = \mathcal{O}(M \lg N)$이 됩니다.
참고로 모든 최적화 문제를 결정 문제로 환원할 수는 없습니다. $Q(x)$가 단조적이지 않다면 (즉, True에서 False로 혹은 그 반대로 바뀌는 지점이 유일하지 않다면), 매개 변수 탐색을 활용할 수 없습니다. 보통 최댓값 또는 최솟값을 찾는 문제에 $Q(x)$를 단조성을 띄도록 잘 정의할 수 있고, 시간복잡도도 적당해 보인다면, 매개 변수 탐색을 적용해볼 수 있습니다!
BOJ 2805 - 나무 자르기
최대 높이가 $H \le 10^9$이고, 나무가 $N \le 10^6$그루 있습니다. $h$미터에 절단기를 설치했을 때 얻을 수 있는 목재의 양은 $\mathcal{O}(N)$에 구할 수 있습니다. 총 시간복잡도는 $\mathcal{O}(N \lg H)$로 충분히 시간 안에 돌아갑니다! 자료형 선택에 유의하세요.
BOJ 3079 - 입국심사
$T$분 안에 심사를 마칠 수 있을까요? 이는 $\mathcal{O}(N)$에 판단할 수 있습니다. Python 사용자가 아니라면, 아무도 모르게 어디선가 64비트 정수 범위도 초과할 수 있음에 주의합시다. (Hint: $T$분 안에 통과 가능한 사람이 몇 명인지 카운트할 때 혹시…)
마지막으로 매개 변수 탐색을 활용한 웰노운 테크닉 하나를 소개하고자 합니다.
BOJ 21556 - 우물 파기
“중앙값으로 $x$가 가능한가?“를 이분 탐색으로 환원시키는 테크닉입니다. Codeforces 등지에서 은근 자주 만날 수 있는 유형입니다. $Q(x)$를 “$x$ 이하인 $A_i + A_j$ 쌍의 개수가 $\lceil \frac{S}{2} \rceil$개 미만인가?“로 놓고 Lower bound를 구하면 될 것 같습니다. 하지만 $\lceil \frac{S}{2} \rceil$가 최대 $10^8$ 스케일보다 더 커질 수 있어서, $Q(x)$의 답을 $\mathcal{O}(\lceil \frac{S}{2} \rceil)$에 구해서는 풀 수 없습니다. 더 생각해봅시다!
도전 문제
BOJ 32136 - 소신발언
매개 변수 탐색 문제인데, 어떤 조건으로 최적화 문제를 결정 문제로 환원할 수 있을까요? 구현이 조금 까다로울 수 있습니다.
BOJ 10227 - 삶의 질
위에서 언급한 중앙값 테크닉의 응용입니다.
BOJ 27947 - 가지 밭 게임
매 턴마다 볼록 다각형의 넓이가 단조증가한다는 것을 관찰한다면 이분 탐색을 적용할 수 있습니다!
BOJ 1557 - 제곱 ㄴㄴ
포함-배제 원리를 사용해서 제곱ㄴㄴ수들의 개수를 빠르게 카운트해야 합니다. Lower bound와 Upper bound를 잘 생각하지 않으면 경계에 제곱ㄴㄴ수가 아닌 수가 걸려서 처리하기 곤란해질 수 있습니다.
마무리
이분 탐색은 PS에서 사용할 수 있는 가장 강력한 도구 중 하나입니다. 최솟값/최댓값을 구하는 최적화 문제를 이분 탐색으로 환원시킬 수 있다면, 반씩 구간을 줄여나간다는 성질로 인한 로그 시간복잡도 덕분에 상당히 유용하게 사용할 수 있습니다. 이분 탐색 많이 사랑해주세요.
