이분 탐색, 매개 변수 탐색
정렬된 배열에서 최대와 최소를 잡고 중앙값을 이동시킨다.
그러다 보면 원하는 값이나 위치에서 멈추게 된다.
이것을 이분 탐색(Binary search)이라고 부른다.
기본적인 탐색은 다음과 같이 진행할 수 있다.
low = 배열의 시작 인덱스
high = 배열의 끝 인덱스
while(low < high) {
1. low와 high의 중앙값을 찾음.
2. 중앙값이 원하는 수보다 큰지 작은지 판별
3. 큰 경우 : low = mid+1
작은 경우 : high = mid-1
}
탐색이 끝난 후에는 조건을 어떻게 처리했느냐에 따라 답이 저장되는 변수가 달라진다.
(그래 봐야 low, middle, high 중이지만...)
하지만 이 테크닉을 실전에서 사용하기 위해서는 약간의 가공(?)이 필요하다.
이것을 매개 변수 탐색(Parametric search)이라고 부른다.
달라진 점은 low = 0, high = 답으로 가능한 최댓값으로 설정한 다는 것과
중앙값이 이동조건을 문제에 따라 유동적으로? 만들어 주어야 한다는 점이 다르다.
문제 예시는 나에게 가장 익숙한 codeup을 이용해 들어보겠다.
https://codeup.kr/problem.php?id=3006
완전 제곱수 찾기
각 줄에 $a_i$를 넘지 않는 가장 큰 완전제곱수를 출력한다.
codeup.kr
문제를 대충 요약하자면 제곱을 했을 때, ai를 넘지 않는 최대 수를 찾는 문제이다.
탐색 방법은 매개 변수 탐색 하면서 중앙값의 제곱이 ai보다 작으면 low를 크면 high를 갱신해 주면 된다.
구현 코드는 다음과 같다.
|
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
|
#include <iostream>
using namespace std;
typedef long long int INT;
int n;
INT ai, lo, hi, mid;
int main()
{
cin >> n;
while(n--) {
cin >> ai;
lo = 0, hi = 4000000000;
while(lo+1 < hi) {
mid = (lo+hi)/2;
if(mid*mid < ai) {
lo = mid;
} else {
hi = mid;
}
}
if(hi*hi > ai) {
cout << lo*lo << "\n";
} else {
cout << hi*hi << "\n";
}
}
return 0;
}
|
cs |
연습해 보고 싶다면?
https://codeup.kr/problemsetsol.php 문제집에 연습 문제가 있으니 도전해 보시길...