[C++] 매개변수 탐색

매개변수 탐색?

- 이분 탐색(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