[파라메트릭 서치] Parametric Search의 이해 및 구현

Parametric Search의 이해 및 구현 코드

"파라메트릭 서치"

최적화 문제를 결정 문제로 바꾸어 푸는 것

이론

파라메트릭 서치 (Parametric search)는 이분 탐색(binary search)의 일종으로
선형 탐색에 비해 효율적인 시간 복잡도를 가집니다.

최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 
결정문제 로 바꾸어 푸는 것이라고도 할 수 있습니다. 

어떤 명제 

 에 대해

 

 

 

True와 False의 경곗값 v0를 찾아야 할 경우 파라메트릭 서치를 이용하게 됩니다. 

 

이 경우 찾아야 하는 v0는 3입니다.

중간 위치는 (0+8)/2 =4 이므로, p(4)를 확인해보니 True -> 4는 v0의 후보군이 되고, 5~8은 탈락.
다음 중간 위치는 (0+3)/2 =1 이므로,p(1)을 확인해보니 False -> 0~1은 탈락.
다음 중간 위치는 (2+3)/2 =2 이므로, p(2)를 확인해 보니 False -> 2도 탈락.
남은 중간위치 (3+3)/2 =3, p(3)은 True 이므로 v0의 후보가 됩니다.

최종적으로 3,4가 v0의 후보가 되며, 그중 작은 값인 3이 v0가 됩니다. 

 

v0의 범위의 크기가 L이라고 했을 때, 선형탐색의 경우 O(L)의 시간이 걸리지만 
파라메트릭 서치는 O(log L)시간만에 v0를 찾을 수 있습니다. 

파라메트릭 서치의 핵심은 "결정문제" 입니다.
해당 값이 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야 최적화 문제를 파라메트릭 서치로 풀 수 있습니다. 
또한, 정답이 될 수 있는 값들이 연속적이어야 파라메트릭 서치를 이용할 수 있습니다.

마지막으로 답의 범위가 이산적이거나(ex.정수) 허용 오차 범위가 있어야 합니다. 

 

코드

//Domain v가 정수인 경우
bool satisfy_p(int v);

int parametric_serach(int l, int r) {
	double v0 = 0, v;
	while (l<=r) {
		v = (l + r) / 2;
		if (satisfy_p(v)) {
			v0 = v;
			r = v-1;
		}
		else {
			l = v+1;
		}
	}
	return v0;
}

//Domain v가 정수가 아닌 경우
//오차 범위로 확인 eps = 10 ^-9
bool satisfy_p(double v);

double parametric_serach(double l, double r) {
	double v0 = 0, v;
	counst double dps = (1e-9);
	while (r - 1 > eps) {
		v = (l + r) / 2;
		if (satisfy_p(v)) {
			v0 = v;
			r = v;
		}
		else {
			l = v;
		}
	}
	return v0;
}