기본적이면서도 너무나도 강력한 이분탐색에 대한 정리를 하고자 한다.
이분탐색이란 말 그대로 일정한 구간, 범위 등을 2개로 나누어 탐색 범위를 좁혀나가는 것을 말한다.
시간복잡도를 따질 때 log N이 붙는 경우가 많은데, 이 로그의 밑은 보통 2를 쓴다. log가 붙었다는 것은 이분탐색 등이 사용되었다는 것을 의미하는 경우가 많다.
4라는 숫자에 밑이 2인 로그를 씌우면 2가 된다. 2의 11승인 2048에 로그를 씌우면 11이 되어버린다. 이것이 의미하는 것은 2048개의 원소를 완전탐색하기 위해서 2048번 일일이 확인하지 않아도, 단 11번 만에 전 범위를 볼 수 있다는 뜻이다. 2048개 숫자를 일종의 이진트리로 재구성하였을 때 그 깊이가 11이라는 의미도 된다. 2048 대 11은 드라마틱하게 느껴지지 않을 수 있다.
하지만, 2의 39승을 보자. 2의 39승은 5천5백억 가까운 아주 큰 수이다. 심지어 int범위로 표현할 수 조차 없다. 하지만 이에 로그를 씌우면 39로 아주 귀엽게 작아진다. 이번에도 5천5백억이라는 숫자를 이진트리로 배치하면 39라는 깊이밖에 안된다는 것이다.
범위가 줄어드는 정도가 정말 너무나도 엄청나지 않은가? 알고리즘과 자료구조를 보면 여러가지의 시간 및 공간 복잡도를 줄이는 기법들이 있다. 앞선 포스팅에서 모노톤 스택을 활용하여 풀이한 히스토그램 및 부분배열 고르기 문제도 O(n^2) -> O(n)으로 줄어들게 만드는 기법이고, 거듭제곱 문제 또한 O(5천억)을 O(39)로 줄여버리는 비트연산(2로 나눈다는 점에서 유사함)을 사용한다. 그중에서도 이분탐색은 그 효율성이 너무 엄청나다. 그래서 이분탐색으로 풀이가 가능한 문제들은 보통 문제에서 주어지는 답이 될 수 있는 범위가 엄청나게 넓다. 반대로 범위의 상한, 하한 차이가 너무나도 크다면, 이분탐색 문제가 아닐까라는 의심을 해볼 수도 있겠다.
이분탐색은 위의 그림과 같이 어떠한 범위가 있을 때(가로로 긴 직사각형) 답이 별의 위치에 있다면, 별이 포함되지 않음이 확실한 앞쪽 범위를 전부 버린다. 그리고 그 과정을 하나의 답을 찾을 때까지 반복하는 것이다. 이를 수도 코드(pseudo code)로 나타내면 아래와 같다.
start(left를 쓰기도 한다)를 의미하는 s는 범위의 하한, end(right가능)를 의미하는 e는 범위의 상한이다. s와 e의 한가운데에 있는 mid를 구해서 한번 '테스트'해보는 것이다. 그리하여 테스트의 결과가 타깃보다 많을 때(넘칠 때 등) s나 e를 조정하여 절반의 범위를 버리는 것이다. 탐색 초반에 버리는 범위의 크기가 엄청나기에 대단한 효율성을 갖는 것이다.
while s<=e:
mid=(s+e)/2
result=some process/computation using mid
if result<=target: s=mid+1
else: e=mid
return s이를 위해서는 범위는 정렬되어 있어야하고, 연속된 수들의 집합이어야 한다. 그리고 결과값은 일정한 경향성/방향성을 띠어야 한다. 즉, 테스트를 하는 값이 커지면 커질수록 결과값도 커지거나 작아지는 등의 모노톤 성향을 가져야 한다는 것이다. 중간중간 어떠한 수에 의해 예외적이고 돌발적인 상황이 발생한다면 이 이분탐색을 당연히 사용할 수 없다. 위의 수도코드위에 있는 [이분탐색과 사분탐색(?)]그림을 다시 보자. 16이란 숫자는 2의 네제곱 이기도 하지만, 4의 제곱이기도 하다. 16을 2분탐색하면 4이지만, 4분탐색하면 2가 된다. 즉, 로그의 밑이 커지면 커질수록 범위가 더 빠르게 줄어들게 된다. 어떻게 보면 2는 로그의 밑에 올 수 있는 의미있는 자연수 중에 가장 작은 수이다. 가장 작은 밑을 사용함에도 범위의 줄어듬이 매우 큰 것이다. 이분탐색 기법 자체가 가지는 힘이 얼마나 대단한지 알 수 있다. (그래서 이분탐색을 응용한 삼분 탐색, 사분탐색 등은 훨씬 강력한 위력을 갖는 것이다.)
정리해보면 아래와 같은 조건에서 이분탐색을 사용하기에 좋다.
- 문제에서 구하고자 하는 답의 범위 (상한, 하한)가 명확하게 정해져 있다.
- 그 범위가 너무 커서 도저히 하나씩 대조해볼 수 없다.
- 결과값은 일정한 경향성/방향성을 갖는다.
- 범위에 있는 수가 균일하고 연속적이다.
이번은 다른 활용사례를 살펴보자.
아래의 그림은 이진트리이다. 이 이진트리에도 아래의 특별한 규칙이 얽매여 있다.
"하나의 정점(노드)이 2개의 자식 노드를 가질 수 있다. 왼쪽 자식은 반드시 부모보다 작으며, 그 모든 조상들보다 작아야 한다. 오른쪽 자식은 반드시 부모보다 크며, 그 모든 조상들보다 커야 한다."
아래 그림처럼 주어진 이진트리에 3이라는 숫자를 넣는다고 생각해보자.
루트(5)에서 시작하여 첫 번째 비교를 하고, 5보다 작기에 왼쪽으로 내려간다. 두 번째 비교는 2와 한다. 2보다 크기 때문에 오른쪽으로 가게 되고, 세 번째 비교를 4와 하여, 4의 왼쪽 자식이 된다. 원래 이진트리상에는 8개의 숫자가 있었지만, 단 3번만 비교하여 자기 자리를 찾을 수 있었다. 이진트리 내에 훨씬 더 많은 숫자가 있었다면 그 효율성이 훨씬 더 와 닿았을 것이나 그림을 일일이 다 그리는 게 힘들다...
덧붙여, lower_bound함수가 어떻게 목표값의 위치를 찾는지 알아보자.
// arr = 정렬된 배열 (반드시 정렬이 되어있어야 한다!)
while(s<e){
mid=(s+e)/2;
if(arr[mid]>=target)e=mid;
else s=mid+1;
}위의 코드와 같이, 정렬된 배열 arr가 있을 때, s=0, e를 (int)arr.size()-1로 잡고(가장 마지막 값의 인덱스), 중간값부터 하나씩 target(목표값)과 확인하는 방식이다. 그리고 목표와의 비교를 통해 한쪽 절반의 범위만 선택하는 방식으로 로그시간만에 목표값의 위치를 찾을 수 있다.
LIS (가장 긴 증가하는 부분 수열)를 구하기 위해 사용하는 lower_bound / upper_bound 함수나 (파이썬에서는 bisect),
세그먼트 트리 자료구조, 힙 정렬, 이진 검색 트리, 이진트리 등이 모두 이 이분탐색을 응용하여 만들어졌다.
따라서, 이분탐색을 완전히 이해한다면 이후에 다룰 LIS와 세그먼트 트리 등을 더 쉽게 이해할 수 있을 것이다.
<이분탐색 관련 주요 문제>
아래의 기본 문제들(2110, 1654)을 풀어보면 이분탐색 문제 해결을 위한 코드의 기본 포맷을 익힐 수 있다.
