매개변수 탐색?
- 이분 탐색(Binary search)와 상당히 유사한 알고리즘
- Nimrod Megido에 의해 발명되었으며, 최적화 문제를 "결정 문제"로 풀 수 있는 알고리즘
- 시간 복잡도(Time complexity): O(log N)
최적화 문제: 어떠한 함수값을 최적화 시키는 변수를 찾는 문제
결정 문제: 예-아니오의 형태로 답안이 나오는 문제
알고리즘 동작 방식
1. 특정 변수 값(mid)을 토대로 조건을 만족하는지 안하는지 탐색한다.
※ 이때, 구현은 이분 탐색으로 구현한다.
2. 이 탐색 과정에서 우리는 두 가지를 알 수 있다.
- 조건을 만족하는 가? -> 결정문제
- 나머지 범위가 조건을 만족하는 가? -> 이분 탐색
3. 조건을 만족하는 범위를 계속 좁혀가며(start와 end 값의 변경) 조건을 만족하는 최적의 답을 찾는다.
예제 문제 - 백준 1654(랜선 자르기)
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int k, n;
ll line[10005];
ll myMax = -1;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>k>>n;
for(int i = 0; i < k; i++){
cin>>line[i];
myMax = max(myMax, line[i]);
}
ll start = 1;
ll end = myMax;
ll mid;
ll ans = 0;
while(start <= end){
mid = (start+end)/2;
ll sum = 0;
for(int i = 0; i < k; i++){
sum += line[i] / mid;
}
if(sum >= n){
start = mid + 1;
ans = max(ans, mid);
}else{
end = mid-1;
}
}
cout<<ans;
return 0;
}
매개변수 탐색 알고리즘은 이 값이 최적의 값인가/ 이 값이 정답인가 라는 문제를
이 값이 정답이 될 수 있는가? 라는 쉬운 문제로 변환하는 알고리즘이다!!
참고한 사이트: https://sete3683.tistory.com/50
'알고리즘을 위한 간략 정리 > 데이터 탐색' 카테고리의 다른 글
투 포인터(TWO-POINTER) (0) | 2023.10.02 |
---|---|
[C++] 이분 탐색(Binary Search) - lower_bound, upper_bound (0) | 2023.09.30 |
[C++] 이분 탐색(Binary Search) - while문 (0) | 2023.09.30 |