[실전 알고리즘] 0x0C강 - 이분탐색_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x13강 - 이분탐색에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

방학때 다 완성을 했어야하는데 특강을 기획하다보니 그것을 준비하느라 완성을 하지 못하게 되었고, 개강을 하니 강좌를 만들 시간이 충분하지가 않네요. 계획 상으로는 7개의 강이 남아있는데 아마 완결까지 굉장히 오래 걸릴 것 같습니다. 양해 부탁드립니다ㅎㅎ 이번 시간에는 이분탐색에 대해 배워보겠습니다.

 

 

이분탐색은 코딩테스트에 자주 나오는 알고리즘이 아닙니다. 그리고 코딩테스트 기준으로 이분탐색은 굉장히 변별력 있는 알고리즘 중 하나이기에 설령 이분탐색 문제가 나왔다고 하더라도 이를 풀지 못해서 당락이 바뀔 가능성은 거의 없습니다. 그러나 이분탐색 문제는 일단 제대로 익히고 나면 구현이 그다지 어렵지 않은 편이기 때문에 코딩테스트에서 굉장한 우위에 설 수 있습니다. 참고로 강의 내에서 언급하겠지만 STL을 사용할 경우 구현이 굉장히 쉬워집니다. 그러므로 이전 강의 내용들을 잘 따라왔다면 이분탐색을 깊게 공부하시고, 그렇지 않다면 이번 강에서 개념만 적당히 익힌 채로 넘어가고 먼저 이전 강의 내용들을 완벽하게 숙지할 수 있도록 합시다.

 

이분탐색은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법입니다. 우리는 0x01강에서 이분탐색을 사용한 알고리즘을 본 적 있습니다. 굳이 딱딱하게 알고리즘이라고 부르지 않더라도, 이분탐색은 술자리에서 업다운 게임을 해본 적이 있다면 머릿속으로 어느 정도 알고 있는 개념일 것입니다.

 

BOJ 1920번 : 수 찾기 문제를 풀어봅시다. 이 문제는 굉장히 정직하게 이분탐색을 할 것을 요구하고 있습니다. 미리 배열 $A$를 정렬해둔 후 $M$개의 수들에 대해 이분탐색을 수행하기만 하면 되는데 구현을 어떤 식으로 해야 할지 굉장히 막막할 것입니다. 구현은 각 수에 대해 해당 수가 있을 수 있는 $A$ 내의 index의 범위를 계속 절반으로 줄이는 방식으로 구현됩니다. 같이 해봅시다.

 

$A$는 이미 정렬되어 있는 상태라고 가정합시다. 정확히 말해서, 입력을 받은 후 STL sort를 이용해 정렬을 수행하면 됩니다. 원래 문제에서는 $A$에 19가 있는지만 판단하면 되지만, 더 확장해 19가 있는 인덱스를 반환하는 함수를 만들도록 하겠습니다.

 

st와 en은 target이 있는 인덱스로 가능한 범위를 나타냅니다. 만약 A 내에 target이 있다면 0에서 9사이임은 자명합니다. 물론 해당 범위 내에 target이 없을 수도 있습니다. 이 범위는 계속해서 줄어들 예정입니다.

 

mid = (st+en)/2로 계산합니다. C언어의 특성상 나머지는 버립니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] < target 입니다. 이 결과를 통해 적어도 mid 이하의 인덱스에는 target이 있을 수 없음을 알 수 있고, 이는 곧 st = mid+1 로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] > target 입니다. 이 결과를 통해 적어도 mid 이상의 인덱스에는 target이 있을 수 없음을 알 수 있고, 이는 곧 en = mid-1 로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] = target 입니다. target이 들어있는 인덱스를 찾았으므로 mid의 값을 반환하고 과정을 종료합니다.

 

이 과정을 코드로 옮기기 전, A 내에 target이 없는 경우에는 어떻게 되는지도 확인해봅시다. 이전과 마찬가지로 st와 en은 target이 있는 인덱스로 가능한 범위를 나타냅니다. 만약 A 내에 target이 있다면 0에서 9사이임은 자명합니다. 이 범위는 계속해서 줄어들 예정입니다.

 

mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] > target 입니다. 이 결과를 통해 적어도 mid 이상의 인덱스에는 target이 있을 수 없음을 알 수 있고, 이는 곧 en = mid-1 로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] < target 입니다. 이 결과를 통해 적어도 mid 이하의 인덱스에는 target이 있을 수 없음을 알 수 있고, 이는 곧 st = mid+1 로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] < target 입니다. 이 결과를 통해 적어도 mid 이하의 인덱스에는 target이 있을 수 없음을 알 수 있고, 이는 곧 st = mid+1 로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] > target 입니다. 이 결과를 통해 적어도 mid 이상의 인덱스에는 target이 있을 수 없음을 알 수 있고, 이는 곧 en = mid-1 로 변경이 가능함을 의미합니다.

 

st와 en이 역전되었습니다. 이는 곧 target과 일치하는 인덱스가 존재하지 않음을 의미합니다. -1을 반환하고 과정을 종료합니다.

 

A[mid]와 target 의 대소비교 결과에 따라 구간이 어떻게 줄어드는지 보겠습니다.

A[mid] > target일 때는 초록색 구간으로, en = mid-1이 됩니다.

A[mid] = target일 때는 주황색 구간으로, st = en = mid이 됩니다. 사실 굳이 st, en 를 바꿀 필요 없이 바로 mid를 반환하면 됩니다.

A[mid] < target일 때는 보라색 구간으로, st = mid+1이 됩니다.

 

설명한 것 그대로 BinarySearch 함수를 구현하면 됩니다. 구간의 범위가 매 반복문마다 계속 절반으로 줄어드므로 $O(lgN)$임을 알 수 있습니다. (정답 코드)

 

함수를 보면 알겠지만, 구현이 그다지 어렵지 않습니다.

 

현재는 배열에 target이 여러 번 들어있을 경우, 아무 인덱스나 반환하게 됩니다. 만약 여러 번 들어있을 때 제일 왼쪽의 인덱스 혹은 제일 오른쪽의 인덱스를 반환해야 하면 어떻게 할까요?

 

더 나아가 값을 정확히 찾는 것이 아닌, target이 삽입되어도 오름차순 순서가 유지되는 제일 왼쪽/오른쪽의 인덱스를 찾는 문제를 생각해봅시다. target이 특정 인덱스에 삽입된다는 의미가 헷갈릴 수 있는데 다음 장의 그림을 보고 정확한 의미를 파악해보세요.

 

target을 특정 인덱스에 삽입한다는 의미는 그 인덱스 이상의 모든 원소를 오른쪽으로 한 칸 밀고 target을 그 인덱스에 넣는다는 의미입니다. 1, 2번째 예시는 삽입 이후에도 오름차순 순서가 유지되나 3번째 예시는 오름차순 순서가 유지되지 않습니다.

 

위의 예시에서 11은 2, 3, 4번째 인덱스에 들어가더라도 모순이 생기지 않습니다. 즉 11이 삽입되어도 오름차순 순서가 유지되는 제일 왼쪽의 인덱스는 2이고 제일 오른쪽의 인덱스는 4입니다. 이를 어떻게 구할 수 있을지, 그리고 제일 왼쪽/오른쪽의 인덱스는 어떤 것과 연관이 있을지를 한 번 고민해보세요.

 

이것 또한 이분탐색으로 해결할 수 있습니다. 더 나아가 오름차순 순서가 유지되는 제일 왼쪽/오른쪽의 인덱스의 차이가 해당 배열 내에 target의 등장 횟수입니다. target이 해당 배열 내에 등장할 때와 그렇지 않을 때를 나눠 직접 앞의 슬라이드를 참고해서 고민해보세요.

 

BOJ 10816번: 숫자 카드 2 문제를 봅시다. 제일 왼쪽과 오른쪽의 인덱스를 구하고 그 차이를 계산하면 그 수가 몇 번 적혔는지를 알 수 있습니다. 마찬가지로 st와 en을 이용한 이분탐색으로 이를 구할 수 있습니다. 우선 제일 왼쪽의 인덱스를 같이 구해봅시다.

 

A는 이미 정렬되어 있는 상태라고 가정합시다. A에 22가 들어가도 모순이 생기지 않는 인덱스 중에서 가장 왼쪽의 것을 반환하는 함수를 만들어봅시다.

 

st와 en은 target이 있는 모순이 생기지 않는 인덱스로 가능한 범위를 나타냅니다. en이 9가 아니라 10임에 주의합니다. 이 범위는 계속해서 줄어들 예정입니다.

 

mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] < target 입니다. 이 결과를 통해 target은 mid보다 더 큰 인덱스에 삽입되어야 함을 알 수 있고, 이는 곧 st = mid+1 로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] = target 입니다. 이 결과를 통해 target은 mid에 삽입이 가능함을 알 수 있습니다. 그런데 저희는 모순이 생기지 않는 인덱스 중에서 가장 왼쪽의 것을 찾고 있으므로, 여기서 mid를 반환하고 끝내면 안됩니다. 대신 그 인덱스는 mid 이하에 존재한다는 사실을 기록하고 다음 단계를 진행해야 합니다. 이는 곧 en = mid 로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] = target 입니다. 앞에서 한 것과 마찬가지 논리로 en = mid로 변경이 가능함을 의미합니다.

 

다시 mid = (st+en)/2로 계산합니다. 우리는 A[mid] 와 target의 값을 비교해 st 혹은 en을 적절하게 바꿀 것입니다.

 

비교 결과 A[mid] = target 입니다. 앞에서 한 것과 마찬가지 논리로 en = mid로 변경이 가능함을 의미합니다.

 

st = en이 되어 후보군이 1개로 고정되었습니다. st를 반환하고 과정을 종료합니다.

 

A[mid]와 target 의 대소비교 결과에 따라 구간이 어떻게 줄어드는지 보겠습니다.

A[mid] >= target일 때는 초록색 구간으로, en = mid이 됩니다.

A[mid] < target일 때는 보라색 구간으로, st = mid+1이 됩니다.

 

굉장히 헷갈릴 수 있는데, 직접 배열과 target을 정해놓고 비교 결과에 따라 구간을 어떻게 정해야할지 고민해보시면 도움이 될 것입니다.

 

설명한 것 그대로 제일 왼쪽의 인덱스를 구하는 lower_idx 함수를 구현하면 됩니다. 구간의 범위가 매 반복문마다 계속 절반으로 줄어드므로 $O(lgN)$임을 알 수 있습니다.

 

제일 오른쪽의 인덱스를 구하는 과정도 비슷하게 진행됩니다. 자세한 설명은 생략하고 마찬가지로 A[mid]와 target의 대소비교 결과에 따라 구간이 어떻게 줄어드는지 보겠습니다. 참고로 lower_idx 함수와 A[mid] = target 일 때만 다릅니다.

 

A[mid] > target일 때는 초록색 구간으로, en = mid이 됩니다.

A[mid] <= target일 때는 보라색 구간으로, st = mid+1이 됩니다.

 

설명한 것 그대로 제일 오른쪽의 인덱스를 구하는 upper_idx 함수를 구현하면 됩니다. 마찬가지로 구간의 범위가 매 반복문마다 계속 절반으로 줄어드므로 O(lgN )임을 알 수 있습니다. (정답 코드)

 

이분탐색에서 실수하기 쉬운 점을 짚어봅시다. 증가수열에서 target보다 값이 작은 원소 중에 가장 오른쪽에 있는 원소의 위치를 찾는 문제를 생각해봅시다. 예를 들어 배열이 (-4, 1, 3, 4, 5, 6, 6)이고 target이 4일 경우 3의 인덱스인 2를 반환합니다. 이 위치는 사실 lower_bound 함수의 반환값에서 한 칸 왼쪽으로 가면 되지만, 앞에서 한 것과 같이 st, en으로 구간을 둔 후 구간을 줄여나가는 이분탐색으로 해결해봅시다.

 

A[mid] < target일 때는 보라색 구간으로, st = mid이 됩니다.

A[mid] >= target일 때는 초록색 구간으로, en = mid-1이 됩니다.

 

혹시 여기서 그림을 보고 뭔가 느낌이 쎄한 것을 찾을 수 있나요? 그렇다면 당신은 빡고수입니다.

 

A[mid]와 target의 비교 결과에 따라 st, en을 바꾸는 과정은 논리적으로 아무 문제가 없습니다. 그러나 앞의 그림에서 보면 초록색 구간과 보라색 구간이 4개/4개로 나눠진 것이 아니라 3개/5개로 나눠진 것을 볼 수 있습니다. 이는 적절한 mid 값을 택하지 못하기 때문에 발생하는 문제로, 단지 정확히 절반으로 나누지 않기 때문에 다소 비효율적이라는 것에서 끝나는게 아니라, 일부 값에 대해 아예 무한루프에 빠져버릴 수 있습니다. 실제로 구현을 했을 때 target이 16일 때 무한루프에 빠져버리는 상황을 확인할 수 있습니다.

 

st = 2이고 en = 3일 때 mid = 2이고, a[2](=11) < target(=16)이기에 st는 변함없이 2가 되어 무한루프에 빠지게 됨을 알 수 있습니다.

 

지금 이 함수에서 이렇게 무한루프가 도는 이유는 st와 en이 1 차이날 때 mid = st를 택했기 때문에 a[mid] < target일 경우 st가 변함없이 계속 st가 되기 때문입니다. 이를 막기 위해서는 st와 en이 1 차이날 때 mid가 st대신 en이 되게끔 해야 합니다. 즉, mid = (st+en+1)/2로 두면 됩니다.

 

(st = mid / en = mid-1)일 때에는 mid = (st+en+1)/2, (st = mid+1 / en = mid)일 때에는 mid = (st+en)/2 으로 두어야 무한루프를 방지할 수 있습니다. 꼭 이것을 공식처럼 외우지 않더라도 직접 st와 en이 1 차이나는 경우를 생각해보면 판단할 수 있습니다.

 

그러나 무한루프는 싫지만 그렇다고 해서 매번 구현시마다 이것을 고려하기도 싫으면, 그냥 en-st 가 어느 정도 이하로 줄어들면 그 안에서는 선형으로 탐색하도록 구현을 할 수도 있습니다. 단, 범위 내에서 제일 왼쪽(=최소)을 찾아야 하는지, 제일 오른쪽(=최대)를 찾아야 하는지에 따라 st부터 1씩 증가하며 살펴볼지, en부터 1씩 감소하면서 살펴볼지를 정해야 합니다.

 

st와 en이 3 이하로 차이나면 반복문을 종료하고 st와 en사이의 모든 index에 대해 순차적으로 조건을 만족하는지 확인하도록 구현한 예시입니다.

 

Binary Search의 구현이 엄청 어려운 것은 아니지만, 실수할 여지가 있습니다. 하지만 STL을 활용하면 Binary Search를 직접 구현할 필요가 없어집니다. STL에는 binary_search, lower_bound, upper_bound 함수가 존재하고 이 세 함수는 오름차순으로 정렬되어 있는 배열/vector에서만 정상 작동하는 함수입니다. 각 함수에 대해 알아봅시다.

 

binary_search 함수는 주어진 범위 내에 원소가 들어있는지 여부를 $O(lg N)$에 true 혹은 false로 반환해주는 함수입니다. 만약 그 범위가 오름차순으로 정렬되어 있지 않다면 실제로는 들어있으나 들어있지 않다고 판단할 가능성이 있습니다.

 

이 함수를 이용하면 BOJ 1920번 : 수 찾기 문제를 더 간단하게 해결할 수 있습니다. (STL을 사용한 정답 코드)

 

lower_bound, upper_bound 는 각각 target이 삽입되어도 오름차순 순서가 유지되는 제일 왼쪽/오른쪽의 인덱스를 반환합니다. 앞에서 같이 구현한 lower_idx, upper_idx 함수와 거의 동일합니다. 단, lower_idx/upper_idx와는 다르게 lower_bound/upper_bound는 배열을 넘겨줄 경우 포인터를 반환하고 vector일 경우 iterator를 반환합니다.

 

포인터/iterator에 그다지 익숙하지 않더라도 몇 가지 사용 예시를 살펴보면 쉽게 감을 잡을 수 있을 것입니다. 구글에 lower_bound라고 검색해보거나 레퍼런스 사이트를 참고해보세요.

 

lower_idx/upper_idx 함수를 구현할 때 언급했듯 동일한 target에 대해 두 인덱스의 차이가 곧 target이 배열 안에 들어있는 횟수입니다. BOJ 10816번: 숫자 카드 2 문제를 STL을 이용해 풀어보세요. (정답 코드)

 

이외에도 저는 써본 적이 없지만 equal_range 라고 lower_bound, upper_bound 의 결과를 pair로 반환해주는 함수도 있습니다.

 

lower_bound, upper_bound 가 무엇을 반환하는지, 어떻게 사용하는지 헷갈릴 수도 있지만 익혀두면 굉장히 유용하니 연습문제들을 풀면서 손에 익히는 것을 추천드립니다.

 

이분탐색 강의가 끝났습니다! 이번 강의에서 저희는 이분탐색의 구현법, 주의사항, 그리고 STL의 사용법을 익혔습니다.

 

Parametric Search라는, 매개 변수의 값을 가지고 이분탐색을 수행해 주어진 문제를 decision problem으로 변환해 시간복잡도를 떨구는 기법도 있으나 코딩테스트 대비용으로는 너무 난이도가 높은 것 같아 배제했습니다. 단, 다른 것을 다 공부하고도 시간이 남는다면 공부해보세요.

 

연습문제가 꽤 어렵습니다. 단순 이분탐색만으로 풀리는 문제도 있지만, 문제를 이분탐색로 풀릴 수 있게끔 변환을 하는 것 자체가 어려운 문제도 들어있습니다. 코딩테스트 수준을 넘어서 깊은 사고를 필요로 하는 문제가 섞여있으니 풀리지 않는다고 너무 자책하지 마세요.