이분 탐색에 대해 너무 대충 생각하고 넘어가는 경우가 잦아, 따로 코테 준비 전 C++ 기준으로 정리해보려고 한다.
배열 역시 유사한 형태로 구현이 가능하나 여기선 벡터 기준으로 살펴보기로 한다.
간단한 예시 문제를 살펴보자.
A>B인 쌍이 몇 개인지 알아내는 문제이다. 이중 for문의 경우 20000 * 20000이기에 1초 기준으로 시간초과가 필연적으로 발생하기에 이분탐색을 떠올려야 했다.
// 정렬
sort(A.begin(), A.end()); // 1 1 3 7 8
sort(B.begin(), B.end()); // 1 3 6
for(int i=0; i<n; i++){
// B에서 A의 특정 원소와 같거나 큰 원소 중 가장 작은(왼쪽) 원소의 인덱스 추출
// 0 0 1 3 3
int idx = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
result += idx;
}
다른 자료구조인 set과 map에도 두 함수가 존재한다.
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(5);
cout << *s.lower_bound(2); // 2
cout << *s.upper_bound(3); // 5
map<int, int> m;
m[0] = 1;
m[2] = 3;
m[4] = 5;
cout << m.lower_bound(2)->second; // key 2가 존재하므로 해당 key의 value인 3
cout << m.upper_bound(3)->second; // key 3보다 큰 요소 중 가장 작은 key 4의 value인 5
간단한 예제를 통해 살펴보자.
이 문제는 모든 어둠을 제거하는 가로등의 최소 높이를 찾는 문제이다. 굴다리의 최대 길이 N이 10만이고, M 역시 최대 10만이 될 수 있기에 단순 이중 for문이 어려운 상황이므로 이 역시 이분탐색을 꺼내들어야 한다.
또한 가로등은 양쪽을 동시에 밝히고 있다는 점에 유의하여 접근해보자.
다음은 정답 코드의 일부이다.
sort(v.begin(), v.end()); // 정렬
int l = 0; // left
int r = 100001; // right
int result = r;
while(l <= r){
int mid = (l+r) / 2;
bool flag = true;
int tmp = v[0];
for(int i=1; i<v.size(); i++){ // 두 가로등 사이 검증
if(v[i]-tmp <= 2 * mid){
tmp = v[i];
} else { // 두 가로등 사이를 모두 밝힐 수 없기에 실패
flag = false;
break;
}
}
if(v[0] > mid || n-v.back() > mid){ // 맨앞 or 맨뒤에 밝지 않은 부분 존재하므로 실패
flag = false;
}
if(flag){ // 모두 밝히는 데 성공 -> 높이(mid)가 작아져야 함
result = min(result, mid);
r = mid - 1;
} else { // 모두 밝히는 데 실패 -> 높이(mid)가 커져야 함
l = mid + 1;
}
}
위와 같이 특정 조건을 만족시켰거나, 특정 형태로 구간을 분할하는 등 다양한 형태로 이분탐색 테마 문제가 제시된다.
10^9와 같은 큰 숫자 범위를 갖거나, O(N^2) 연산이 어렵다는 판단이 내려질 경우 항상 이분탐색을 떠올릴 줄 알야아 하고,
이분탐색 시에는 while문을 사용해야 할지 혹은 lower_bound 등의 함수를 사용해야 할지 판단할 줄 알아야 한다.
우왕 멋져용><