이분탐색 (binary search) C++ STL 사용법 알아보고, 구현해보자!

1. 정의 살펴보기

오늘은 이분 탐색 알고리즘에 대해서 알아보겠다.

여느 때와 동일하게 위키피디아를 켰다.

Binary search 에 대한 Wikipedia의 설명

 

장황하게 설명되어 있는데, 핵심 문장을 살펴보면 아래와 같다.

타겟 밸류와 배열의 중간값을 비교하여 일치하지 않았다면 '타겟이 있을 수 없는 절반의 영역을 삭제' 한 후, 나머지 절반의 영역에서 해당 과정을 반복하는 탐색방법이다. 이 탐색은 타겟이 발견될 때까지 계속된다.

라고 되어있다.

 

요컨데, 내가 초등학생 때 했던 놀이 중 하나와 상당히 닮아 있는 것 같다. 혹시 Up Down 게임을 해 봤다면 이해가 굉장히 쉬울 것 같다. 1부터 100까지의 숫자를 하나 생각하고, 상대가 하나를 추측해서 제시한다. 그럼 나는 내가 생각한 숫자가 더 크다면 UP, 내가 생각한 숫자가 더 작다면 DOWN을 외치고, 상대는 또 다음 추측을 진행하는 류의 게임이다.

물론 처음부터 범위를 크게 좁히기 위해 도박수를 걸어 10이나 90과 같이 중간에서 멀리 떨어진 값을 외치는 경우도 있지만, 대부분의 경우 첫 수로 50을 부른다. 만약 DOWN이라고 한다면, 1~49 사이에 답이 존재하는 것이고, 50~100은 아예 배제해버릴 수 있다.

그렇다면 다음 수로는 뭘 불러야 할까? 1과 49 사이에 있는 25를 부르는 것이 이상적일 것이다. 그리고 이와 같은 방법이 Binary search와 완벽하게 일치한다는 것을 확인할 수 있다.

 

Binary search의 가장 큰 특징은 위키피디아에도 언급된 바와 같이, 시간복잡도가 O(log N) 이라는 부분에 있다. 이 사실을 이용하면 이분탐색이 가능한 경우에 한하여 엄청나게 빠른 답안을 도출해낼 수 있다는 장점이 있다. O(N^2)의 문제를 O(NlogN)으로만 바꿔도 기쁜 상황에서 O(log N)은 도저히 참을 수 없는 매력적인 시간복잡도이다.

 

 

 

2. STL 사용해보기

algorithm 이라는 STL를 사용하면, binary search와 관련된 함수들을 사용할 수 있게 된다.

binary_search, upper_bound, lower_bound가 그것이다.

하나하나 cplusplus.com 에서 살펴보자.

 

binary_search() 함수의 cplusplus.com 에서의 정의

두 가지 템플릿이 존재하며, 첫째 템플릿은 first, last, val 을 변수로 받고, 두번째 템플릿에서는 comp 변수를 추가로 받는다.

쓰여있다시피, "정렬된 값에 대해서만" 올바르게 작동한다.

기본적으로는 오름차순 정렬이 되어있어야 사용 가능하지만, comp 변수를 사용하는 경우라면 comp 변수의 규칙과 같이 정렬되어 있어야 한다. (sort 함수 편에서 다뤘던 내용과 동일하다. comp로 인해 내림차순 정렬을 시켰다면, 이 경우에서 역시 동일 함수를 사용하여야 한다.)

변수 설명

변수 설명인데, 어렵지 않다.

first와 last는 서치를 시작할 주소와 끝 주소, val는 찾을 값, comp는 함수이다. (sort() 함수 편에서 다뤘으니 참고)

https://marei-developement-diary.tistory.com/2

C++ sort() 함수에 대해서 알아보자.

comp 함수의 사용법에 대해서 궁금하다면 여기 이미 설명해두었으니 가서 읽어보길 바란다.

 

아무튼 정리해서 말하자면

1. comp 없이 사용할 경우, 오름차순 정렬된 값들 중 val 값이 존재하는지

2. comp를 사용할 경우, comp의 기준으로 정렬된 값들 중 val 값이 존재하는지를 파악하여

존재한다면 true를, 존재하지 않는다면 false를 return하는 함수.

라고 정리해 볼 수 있겠다.

 

다음은 lower_bound 함수에 대해서 알아보자.

lower_bound() 함수의 cplusplus.com 에서의 정의

 

lower_bound 함수에 대한 cplusplus.com의 설명이다.

마찬가지로 first, last, val, comp 변수를 사용하는 두 종류의 템플릿이 존재한다.

하지만 이 함수가 궁극적으로 return하는 값은 val 값의 lower bound의 iterator이다.

말은 어려운데 간단하게 말해서 배열 안에서 val보다 크거나 같은 값들 중 가장 앞에 존재하는 값의 위치를 나타낸다고 생각하면 된다.

예를 들어 arr[6] = {1, 2, 4, 4, 4, 7} 에서 lower_bound(arr, arr+6, 4) = arr+2 가 나올 것이다.

이 경우 lower_bound(arr, arr+6, 4)-arr 를 하게 되면 arr의 몇 번째 원소가 lower bound를 저장하게 되는지 알 수 있게 된다.

 

lower_bound 가 있으면 upper_bound 도 있을 것 같지 않은가?

 

upper_bound() 함수의 cplusplus.com 에서의 정의

 

upper_bound 역시 존재한다.

다 똑같은데 역시 return만 다르다. return값은 val보다 큰 값 중에서 가장 먼저 등장하는 값의 위치를 나타낸다.

똑같은 배열에서 예시를 들어보면, arr[6] = {1, 2, 4, 4, 4, 7} 에서 upper_bound(arr, arr+6, 4) = arr+5 가 나올 것이다.

이 경우 uper_bound(arr, arr+6, 4)-arr 를 하게 되면 arr의 몇 번째 원소가 upper bound를 저장하게 되는지 알 수 있게 된다.

 

참고로, 어떤 배열에서 특정 값이 출현한 횟수의 경우, upper_bound 값에서 lower_bound 값을 뺀 결과값 만큼의 출현횟수를 가지게 되므로 알아두면 굉장히 유용하다.

 arr[6] = {1, 2, 4, 4, 4, 7} 에서 upper_bound 인 arr+5 에서 lower_bound인 arr+2를 뺀 값인 3이, 숫자4가 배열안에서 출현한 횟수라는 것이다.

 

 

 

3. 문제 풀이 (직접 구현하기)

하지만 문제를 풀다보면 특정 값을 찾기 위해서만 이분탐색을 사용하지는 않는다. 때문에 이분탐색 알고리즘의 원리를 사용하면서도 STL의 활용으로는 문제를 풀 수 없는 경우가 더러 생긴다. 코딩 테스트 등에서 이런 문제를 마주했을 때를 대비해서라도 직접 구현하는 방법을 알아야 한다.

 

이분탐색은 설계만 완료되면 구현은 상당히 쉬운 편에 속한다. 다만, 이분 탐색을 어떻게 적용시켜야할 지에 대해서 아이디어가 떠오르지 않는다면 난이도가 굉장히 올라가는 유형이라고 생각한다. 숫자의 범위가 굉장히 넓으면서 시간을 단축해서 구현해야하는 경우 이분탐색을 염두에 두어야 한다.

 

 

그렇다면 백준 2110번 문제를 보자

백준 #2110 공유기 설치

 

일직선 위의 집의 좌표들이 주어지고, C개의 공유기를 설치할 때, 가장 가까운 두 공유기 사이의 거리가 최대가 될 때의 그 거리를 구하라는 문제이다.

입력 조건을 보면, 정답은 0과 1,000,000,000 사이의 한 값이 정답이 되는데, 시간제한은 2초이다. 각 경우 하나하나 다 따져보는 방법으로는 1,000,000,000가지를 모두 따져보게 되며, 시간초과가 될 확률이 매우매우매우매우 높다.

따라서 이분 탐색을 해야할 것이라고 생각해볼 수 있겠다.

 

메인 아이디어

그렇다면 어떻게 접근하면 좋을까?

답으로 가능한 거리의 범위는 최소값이 1, 최대값은 가장 먼 위치의 두 집의 좌표차이 라고 볼 수 있다. (2개 설치 시 아무리 멀어도 한쪽 끝과 다른 한 쪽 끝에 위치한 경우이므로)

low와 high는 준비됐다. 그렇다면 각각 어떻게 이 값들을 control 해나갈까?

mid = (low+high)/2 에 대해서, 다음을 따져보자.

 

1. 첫 번째 집에는 공유기를 설치하고, 이 값을 curr에 저장하자.

2. 첫 번째 공유기와의 거리가 mid 이상인 집이 처음 등장하면 공유기를 설치한다. 이 값을 curr 값에 저장하자.

3. curr에 저장된 값과의 거리가 mid 이상인 집이 처음 등장하면 공유기를 설치하고, 이 값을 curr 값에 저장한다.

4. 3의 과정을 반복한다.

5. 모든 집에 대해서 반복한 후에 설치된 공유기의 갯수가 C개 이상이면 true, C개 미만이라면 false를 반환하는 함수를 만든다.

 

이렇게 해서 만든 함수를 isPossible() 라고 해보자

만약 isPossible(mid)==true 라고 한다면, 혹시 거리가 더 길 때도 가능할 지 확인해보고 싶을 것이므로, low=mid+1으로 바꿔준 다음 코드를 반복해본다. 만약 가능한 경우라면 이전에 가능했던 값과 현재 가능한 값 중 어떤 값이 더 큰 지 역시 저장해주면 좋겠다.

또, isPossible(mid)==false 라고 한다면 mid의 값이 너무 크다는 얘기가 되므로, high=mid-1으로 바꾸고 계속 진행하면 된다.

low<high 인 상황에서 위의 내용을 반복해나간다면? 답을 구할 수 있을 것으로 보인다.

 

최종 코드

맞았습니다!!

 

 

 

4. 고찰

엄청나게 큰 가짓수의 케이스를 다룰 때, 굉장히 유용하다. 공유기 설치 문제의 경우 sort 하는데 O(Nlog N), 그리고 이분탐색을 하는데 각 탐색마다 O(N)의 연산을 포함하기에 O(N)*O(logN)=O(NlogN) 해서, O(NlogN)+O(NlogN)=O(NlogN) 의 시간복잡도를 가지는 것을 예상해볼 수 있다. 만약 브루트포스 알고리즘을 사용하였다면 O(N^2)의 시간복잡도를 가졌을 것이다. 떠올릴 수만 있다면, 시간 단축이 굉장히 잘 된다.

 

하지만 이는 어디까지나 떠올릴 수 있을 때의 얘기이다. 분명 이분탐색의 개념 그 자체와 구현 방법은 어렵지 않지만, 어떻게 적용시킬지를 생각하는 것은 보다 어렵다고 느껴진다.

공유기 설치 문제 정도의 수준까지는 그래도 조금 머리를 굴리면 알아낼 수 있지만, 어떻게 적용시키는 건지 다른 사람들이 푼 것을 보지 않으면 감도 잡히지 않는 문제도 많았다. 이분탐색 문제는 정말 다양한 문제를 접해본 후에 코딩테스트에서 접했을 때 어! 이거 저번에 풀었던 거랑 비슷한데! 라고 떠오르는게 아니라면 정말 어려울 것 같다.

 

약간의 벽을 느끼게 하는 문제유형이었다. 쉬운 문제는 한도 끝도 없이 쉽지만, 어려운 문제는 한도 끝도 없이 어려운, 난이도의 편차가 굉장히 심한 유형이라고 생각된다. 나중에 실무에 들어가서 이진탐색 알고리즘을 복잡하게 사용해야 하는 경우가 생길 수도 있을 것이다. 이 때를 대비해서라도 열심히 공부해야 한다.

현재 내가 할 수 있는 최선은 다양한 문제를 풀어보는 것 정도이다.

 

 

 

Sources

https://en.wikipedia.org/wiki/Binary_search_algorithm

Binary search algorithm - Wikipedia

https://cplusplus.com/reference/algorithm/binary_search/#google_vignette

https://cplusplus.com/reference/algorithm/binary_search/#google_vignette

https://cplusplus.com/reference/algorithm/lower_bound/

https://cplusplus.com/reference/algorithm/lower_bound/

https://cplusplus.com/reference/algorithm/upper_bound/

https://cplusplus.com/reference/algorithm/upper_bound/

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치