코딩테스트에서의 이분탐색 문제 공략법

개요

이분탐색의 개념자체는 쉽다.

심지어 stl에 이미 함수가 있어서 직접 구현할 필요조차 없다.

하지만 조금만 꼬아서 내도 문제 난이도가 저세상으로 간다.

그러니 코딩 테스트에서 킬러 문항으로 자주 출제되는 이분탐색 응용 문제 공략에 대해 알아보자!

 

 

이분탐색이란?

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

시간 복잡도는 O(logN)이다.

 

 

C++ STL의 이분탐색

시간 복잡도

STL에 있는 이분탐색 함수도 O(logN)이다.

 

헤더 파일

<algorithm>에 std::binary_search가 있다.

이분탐색을 하기 위해선 정렬이 필수인데 std::sort 또한 <algorithm>에 있다.

 

binary_search

template <class ForwardIterator, class T>  bool binary_search (ForwardIterator first, ForwardIterator last,                      const T& val);

정렬된 범위에서 값이 존재하는지 테스트하는 함수이다.

[first, last) 범위 내의 어떤 요소가 val과 동등한 경우 true를 반환하고, 그렇지 않으면 false를 반환한다.

 

v라는 벡터에서 3을 찾기 위해서는 이렇게 하면 된다.

std::binary_search (v.begin(), v.end(), 3)

 

위의 버전은 operator<를 사용하여 값을 비교하는 버전이다.

 

만약에 문제에서 독특한 비교 기준을 요구한다면 어떻게 할 것인가?

stl에 이미 있다.

template <class ForwardIterator, class T, class Compare>  bool binary_search (ForwardIterator first, ForwardIterator last,                      const T& val, Compare comp);

오름차순이 아닌 다른 기준으로 sort 하기 위해 비교 함수를 만든 경험이 있을 것이다.

그와 유사하게 비교함수를 만들어서 인자로 넘겨주면 된다.

 

bool myfunction (int i,int j) { return (i>j); }
std::sort (v.begin(), v.end(), myfunction);

이런 식으로 operator< 말고도 다양한 기준으로 이분탐색을 할 수 있다.

 

 

만약에, 찾고자하는 것이 여러 개가 있다면?

ex) 1 3 6 7 7 7 9 라는 배열에서 7 을 찾고자 할때

7이 3번이나 나오는데 그 중에서 처음으로 등장한 7(인덱스 3)을 원할 때도 있고 가장 나중에 등장하는 7(인덱스 5)를 원할 때도 있을 것이다.

단순히 이분탐색으로 7을 찾아서 앞뒤로 인덱스를 옮겨가며 7과 동일한지 비교할 것인가?

만약 처음부터 끝까지 다 7뿐인 배열이었다면? 그러면 최악의 경우 시간 복잡도가 O(N)이 된다.

이 기능 역시 STL에 있다. 

직접 구현하여도 좋다.

백준 10816번의 문제와 풀이를 참고하면 좋다. https://ymthebest.tistory.com/46

 

lower_bound와 upper_bound

binary_search와 동일하게 algorithm 헤더에 있다.

하한선이라는 이름처럼 lower_bound는 구하고자 하는 값보다 작지않은 첫 번째 원소를 가리키는 반복자를 반환한다.

구하고자 하는 값이 여러 개 있을 때는 그 중에서 첫 번째(가장 왼쪽) 값을 가리킨다.

하지만 만약에 구하고자 하는 값이 없을 수도 있다.!

그럼 어떻게 될지는 정의를 다시 생각해보면 알 수 있다.

'구하고자 하는 값보다 작지않은 첫 번째 원소'라고 했으니 구하고자 하는 값보다 큰 원소를 가리키는 반복자를 반환할 것이다.

 

template <class ForwardIterator, class T>  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,                               const T& val);

binary_search와 동일하게 비교함수를 직접 넘겨줄 수도 있다.

 

upper_bound는 원하는 값보다 크다고 비교되는 범위 내의 첫 번째 원소를 가리키는 반복자를 반환한다.

이 함수에 의해 반환된 반복자가 가리키는 값은 원하는 값과 동등할 수 있고 무조건 크다.

template <class ForwardIterator, class T>  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,                               const T& val);

 

사용 예시는 다음과 같다.

 std::vector<int>::iterator low,up;
 low=std::lower_bound (v.begin(), v.end(), 20);
 up= std::upper_bound (v.begin(), v.end(), 20); 

 std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
 std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

 

 

주의사항

1. 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 한다.
2. 무한 루프에 빠지지 않게 mid 값을 정해야 한다. (st와 en이 1 차이 날 때를 주의깊게 확인하기)

 

 

 

참고 자료

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

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

https://youtu.be/3TkaOKHxHnI?si=bVVGQB4e78Vwmh33