이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)
이분 탐색(Binary Search)
개요
탐색 기법중 하나로, 배열이 정렬되어 있을 때 사용할 수 있다.
간단히 설명하자면, 배열의 중간 값이 자신이 찾는 값인지 확인하고
찾는 값이 아니면 배열을 왼쪽 절반, 또는 오른쪽 절반으로 범위를 줄여나가며
자신이 원하는 값을 찾을 때 까지 반복해 나가는 알고리즘이다.
시간복잡도는 $O(logN)$이다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
left = 0, right = N; // 1. 범위를 정한다.
while (left <= right) {
mid = (left + right) // 2. 중앙 위치를 탐색
if (target < mid) // 3. 결정문에 따라 위치를 반환하거나, 범위를 절반으로 조정
right = mid - 1;
else if (target > mid)
left = mid + 1;
else
return mid; // 값을 찾았으면 return, 못 찾았으면 범위를 절반으로 줄임
}
return -1;
STL
해당 알고리즘은
주의점은 배열은 반드시 오름차순으로 정렬되어 있어야 한다. 또한 반환값은 bool형이다.
1
2
binary_search(vec.begin(), vec.end(), target);
// target이 있으면 true, 없다면 false를 반환한다.
매개변수 탐색(Parametric Search)
개요
최적화 문제를 결정 문제로 변환하여 탐색하는 알고리즘으로, 이분 탐색을 사용한다.
최적화 문제와 결정 문제는 간단하게 설명하자면 다음과 같다.
- 최적화 문제: “조건이 주어졌을 때 가장 좋은 답인 $x$는 무엇인가”
- 결정 문제: “매개 변수로 $x$가 주어졌을 때, $x$는 정답이 될 수 있는가 (조건에 부합하는가)”
매개변수 탐색은 우리가 원하는 값($x$)을 매개변수로 바꾸어 해당 값이 정답이 가능한 값인지를 확인한 후
이에 부합하는 값중에 최적인 값을 찾는 알고리즘이다.
이 때 해당 값($x$)을 찾기 위하여 이분 탐색을 사용하고. 결정 문제(=결정 함수) $f(x)$를 탐색 범위를 조절하는 기준으로 삼는다.
(이 때 탐색 범위는 ($x$)가 될 수 있는 범위이다.)
매개변수 탐색은 보통 어느 시기를 기점으로 조건을 만족하다가 조건에 만족하지 않는 경우(또는 그 반대의 경우)에 사용한다.
시간 복잡도는 이분탐색을 사용하므로 $O(logN)$이다.
예제: BOJ 13397 - 구간 나누기 2
해당 문제는 “배열이 주어졌을 때, 구간을 나누어 각 구간의 점수들의 최댓값들 중 최솟값은 무엇인가?”를 묻는 문제이다.
이 때 구간의 점수는 구간에 존재하는 최댓값과 최솟값의 차이이다.
문제의 형태를 잘 보면 궁극적으로는 “가장 좋은 답이 무엇인가” 를 묻는 최적화 문제이다.
이를 결정 문제로 바꾸어보자.
” $x$ 가 주어졌을 때, 각 구간의 점수들의 최댓값이 $x$ 보다 작은가?”
결정 문제로 변환했다면, 해당 조건에 부합하는 $x$의 값 중에서 최솟값을 찾으면 될 것이다.
정답코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector <int> vec;
bool func(int x) { // M개 이하의 배열로 구간 점수의 최댓값이 x 이하이도록 만들 수 있는가
int max_v, min_v, cnt;
max_v = vec[0], min_v = vec[0], cnt = 1;
for (int i = 1; i < N; i++) {
max_v = max(max_v, vec[i]);
min_v = min(min_v, vec[i]);
if (max_v - min_v > x) {
max_v = vec[i];
min_v = vec[i];
cnt++;
}
}
return cnt <= M;
}
int main() {
cin >> N >> M;
vec.resize(N);
for (auto &el : vec) {
cin >> el;
}
int ans = 0, left = 0, right = 1e4 * N;
while (left <= right) {
int mid = (left + right) / 2;
if (func(mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans;
return 0;
}
upper_bound와 lower_bound
개요
이분 탐색에서 응용할 수 있는 알고리즘이다.
배열이 오름차순으로 정렬되어 있다고 가정하여 사용했을 때, 두 알고리즘의 차이점은 다음과 같다.
- upper_bound는 배열에서 목표값을 초과하는 값 중에서 가장 좌측에 위치한 값을 찾는 알고리즘이다.
- lower_bound는 배열에서 목표값과 같거나 큰 값 중에서 가장 좌측에 위치한 값을 찾는 알고리즘이다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int upper_bound(int target, vector<int> &v) {
int left = 0, right = v.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (target <= v[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lower_bound(int target, vector<int> &v) {
int left = 0, right = v.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (target < v[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
STL
해당 알고리즘은
사용시 주의점은 매개변수로 사용하는 배열은 반드시 오름차순으로 정렬되어 있어야 한다.
1
2
3
4
5
auto lower = lower_bound(vec.begin(), vec.end(), key);
// iterator 형태로 lower에 저장된다.
auto upper = upper_bound(vec.begin(), vec.end(), key);
// iterator 형태로 upper에 저장된다.
예제
- BOJ 1654 - 랜선 자르기 <- 가장 기초적인 문제
- BOJ 1300 - K번째 수 <- 접근법 향상을 위한 문제
그 외 solved.ac 이분 탐색(binary_search) 태그 및 매개 변수 탐색(parametric_search) 태그 문제들..