0x13 이분탐색
배열에서 원하는 값을 찾을 때, 앞에서부터 하나씩 확인하면 최악의 경우 O(N)이 걸린다. 데이터가 100만 개라면 100만 번 비교해야 한다는 뜻이다. 배열이 정렬되어 있다면 훨씬 효율적인 방법이 있다. 이분탐색(Binary Search)을 사용하면 탐색 범위를 매번 절반으로 줄여서 O(log N) 만에 답을 찾을 수 있다.
0x00 정의와 성질
이분탐색 = 정렬되어 있는 배열에서 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법
사전에서 단어를 찾는 상황을 떠올리면 된다. "Python"이라는 단어를 찾을 때 1페이지부터 순서대로 넘기는 사람은 없다. 대충 중간쯤 펼쳐보고, 찾는 단어가 더 앞에 있으면 앞쪽 절반을, 더 뒤에 있으면 뒤쪽 절반을 다시 탐색한다. 이분탐색이 정확히 이 원리다.
핵심은 배열이 반드시 정렬되어 있어야 한다는 전제 조건이다. 정렬되지 않은 배열에서는 중간값을 기준으로 범위를 줄이는 논리가 성립하지 않는다.
0x01 구현 및 STL
기본 구현
가장 기본적인 이분탐색 함수다. st(시작)와 en(끝) 두 포인터를 관리하면서, 중간값 mid를 계산해 target과 비교한다. target보다 작으면 오른쪽 절반으로, 크면 왼쪽 절반으로 범위를 좁혀 나간다. target을 찾으면 1을 반환하고, st가 en을 넘어서면 값이 없다는 의미이므로 0을 반환한다.
int binarysearch(int target){
int st = 0;
int en = n-1;
while(st <= en){
int mid = (st+en)/2;
if(a[mid] < target)
st = mid+1;
else if(a[mid] > target)
en = mid-1;
else
return 1;
}
return 0; // st > en일 경우 while문을 탈출
}STL binary_search(start, end, target)
직접 구현하지 않아도 C++ STL에서 binary_search 함수를 제공한다. 정렬된 배열과 찾을 값을 넘기면 존재 여부를 bool로 반환한다. 아래 코드는 배열을 입력받아 정렬한 뒤, m개의 쿼리에 대해 값의 존재 여부를 출력하는 예시다.
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int n;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a,a+n);
int m;
cin >> m;
while(m--){
int t;
cin >> t;
cout << binary_search(a, a+n, t) << '\n';
}
}BOJ 10816 : 숫자 카드 2
단순히 값이 "있는지 없는지"가 아니라, 몇 개 있는지 세야 하는 문제다. 이때 등장하는 것이 lower_bound와 upper_bound 개념이다.
- lower_bound: target 이상인 첫 번째 위치
- upper_bound: target 초과인 첫 번째 위치
두 위치의 차이가 곧 target의 개수가 된다. 예를 들어 배열이 [1, 2, 2, 2, 3]이고 target이 2라면, lower_bound는 인덱스 1, upper_bound는 인덱스 4를 가리키므로 개수는 4 - 1 = 3이다.
아래 코드에서 lower_idx 함수는 a[mid] >= target이면 왼쪽으로 범위를 줄이고, upper_idx는 a[mid] > target이면 왼쪽으로 줄인다. 이 미묘한 부등호 차이가 lower_bound와 upper_bound를 구분짓는 핵심이다.
#include <bits/stdc++.h>
using namespace std;
int a[500005];
int n;
int lower_idx(int target, int len){
int st = 0;
int en = len;
while(st < en){
int mid= (st+en)/2;
if(a[mid] >= target) en = mid;
else st = mid+1;
}
return st;
}
int upper_idx(int target, int len){
int st = 0;
int en = len;
while(st < en){
int mid= (st+en)/2;
if(a[mid] > target) en = mid;
else st = mid+1;
}
return st;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a,a+n);
int m;
cin >> m;
while(m--){
int t;
cin >> t;
cout << upper_idx(t,n)-lower_idx(t,n) << '\n';
}
}STL lower_bound, upper_bound 사용 가능
위의 직접 구현과 동일한 동작을 STL의 lower_bound와 upper_bound 함수로 간결하게 처리할 수 있다. 실전에서는 STL을 사용하는 편이 실수를 줄이는 데 유리하다.
#include <bits/stdc++.h>
using namespace std;
int a[500005];
int n;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a,a+n);
int m;
cin >> m;
while(m--){
int t;
cin >> t;
cout << upper_bound(a,a+n,t)-lower_bound(a,a+n,t) << '\n';
}
}이분탐색을 구현할 때 반드시 기억해야 할 두 가지가 있다.
주의사항
- 이분 탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 한다.
- 무한 루프에 빠지지 않게 mid 값을 정해야 한다.
특히 두 번째 주의사항은 자주 실수하는 부분이다. st와 en의 갱신 방식에 따라 mid = (st+en)/2로 할지, mid = (st+en+1)/2로 할지가 달라진다. 잘못 설정하면 st와 en이 바로 옆에 붙었을 때 mid 값이 변하지 않아 무한 루프에 빠질 수 있다.
0x02 연습 문제 1 - 좌표 압축
좌표 압축은 값의 상대적인 순서만 보존하면서, 큰 범위의 좌표를 0부터 시작하는 작은 정수로 바꾸는 테크닉이다. 접근법은 단순하다: 정렬 -> 중복 제거 -> lower_bound로 인덱스 출력.
아래 코드는 입력값을 복사해 정렬한 뒤, 인접한 값이 다를 때만 uni 벡터에 넣어 중복을 제거한다. 그런 다음 원본 배열의 각 값이 uni에서 몇 번째에 위치하는지를 lower_bound로 찾아 출력한다.
#include <bits/stdc++.h>
using namespace std;
int n;
int x[1000005];
vector<int> tmp, uni; // unique
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> x[i];
tmp.push_back(x[i]);
}
sort(tmp.begin(), tmp.end());
for(int i = 0; i < n; i++){
if(i= 0 || tmp[i-1] = tmp[i])
uni.push_back(tmp[i]);
}
for(int i= 0; i < n; i++)
cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';
}STL unique 활용 가능
중복 제거 과정을 직접 구현하는 대신, STL의 unique 함수를 사용하면 더 깔끔하다. unique는 연속된 중복 원소를 뒤로 밀어내고 중복이 제거된 마지막 위치의 반복자를 반환한다. 이것을 erase와 조합하면 한 줄로 중복 제거가 완료된다.
#include <bits/stdc++.h>
using namespace std;
int n;
int x[1000005];
vector<int> uni; // unique
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> x[i];
uni.push_back(x[i]);
}
sort(uni.begin(), uni.end());
uni.erase(unique(uni.begin(), uni.end()), uni.end());
for(int i = 0; i < n; i++)
cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';
}0x03 연습 문제 2 - 세 수의 합
세 수의 합 문제는 배열에서 세 원소를 골라 합이 특정 조건을 만족하는 경우를 찾는 문제다. 세 수를 모두 브루트포스로 고르면 O(N^3)이지만, 이분탐색을 활용하면 시간 복잡도를 크게 줄일 수 있다.
핵심 아이디어는 두 수의 합을 미리 계산해두는 것이다. 가능한 모든 두 수의 합을 two 벡터에 저장하고 정렬한다. 그런 다음 a[i] - a[j]가 two 벡터에 존재하는지를 binary_search로 확인한다. 가장 큰 수부터 역순으로 탐색하므로, 처음 찾은 a[i]가 곧 답이 된다.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
vector<int> two;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a+n);
for(int i = 0; i < n; i++){
for(int j= i; j < n; j++)
two.push_back(a[i]+a[j]);
}
sort(two.begin(), two.end());
for(int i= n-1; i > 0; i--){
for(int j = 0; j < i; j++){
if(binary_search(two.begin(), two.end(), a[i]-a[j])){
cout << a[i];
return 0;
}
}
}
}0x04 Parametric Search
이분탐색의 응용 중 가장 중요한 것이 **Parametric Search(파라메트릭 서치)**다. 일반적인 이분탐색이 "이 값이 배열에 있는가?"를 묻는다면, Parametric Search는 "조건을 만족하는 최소/최대값은 얼마인가?"를 묻는다.
Parametric Search = 조건을 만족하는 최소/최대값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법
문제의 형태를 바꾸는 것이 핵심이다. "최대 얼마까지 가능한가?"라는 최적화 문제를, "X일 때 조건을 만족하는가?"라는 Yes/No 결정 문제로 변환한다. 결정 문제는 이분탐색으로 풀 수 있기 때문이다.
BOJ 1654 랜선 자르기
이 문제를 예로 들어보면 다음과 같이 변환할 수 있다.
- (최적화 문제) N개를 만들 수 있는 랜선의 최대 길이는?
- (결정 문제) 랜선의 길이가 X일 때 랜선이 N개 이상인가 아닌가?
아래 그림은 길이 X에 따라 만들 수 있는 랜선 개수가 어떻게 변하는지를 보여준다. X가 커질수록 개수는 줄어드므로, 조건을 만족하는 가장 오른쪽 경계를 이분탐색으로 찾으면 된다.
주의사항
Parametric Search가 성립하려면 결정 함수의 결과가 단조적이어야 한다. 즉, 특정 지점을 기준으로 한쪽은 모두 True, 다른 쪽은 모두 False인 형태여야 한다. 함수가 증가 또는 감소 함수여야 이분탐색으로 경계를 찾을 수 있다.
아래 코드에서 solve(x) 함수가 결정 함수 역할을 한다. 각 랜선을 길이 x로 잘랐을 때 총 개수가 n 이상인지를 반환한다. 이분탐색에서 mid = (st + en + 1) / 2로 올림 처리한 것은, st = mid로 갱신하는 구조에서 무한 루프를 방지하기 위함이다.
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
int k, n;
int arr[10005];
bool solve(ll x) {
ll cur = 0;
for(int i=0; i<k; i++) cur = arr[i] / x;
return cur >= n;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i=0; i<k; i++) cin >> arr[i];
ll st = 1;
ll en = 0x7fffffff;
while(st < en) {
ll mid= (st + en + 1) / 2;
if(solve(mid)) st= mid;
else en= mid - 1;
}
cout << st << endl;
return 0;
}문제 풀이
리뷰
이분탐색은 개념 자체는 단순하지만, 구현에서 실수하기 쉬운 알고리즘이다. 특히 st와 en의 초기값, while 조건의 등호 포함 여부, mid 계산 시 올림/내림 처리 등 디테일이 많다. Parametric Search는 "이 문제가 이분탐색인지 알아차리는 것" 자체가 가장 어려운 부분이다. 최적화 문제를 결정 문제로 바꿀 수 있는지 항상 생각해보는 습관을 들이면 좋겠다.
출처: 바킹독님의 실전알고리즘 강의