[자료구조 및 알고리즘] 파라메트릭 서치 (Parametric Search)

파라메트릭 서치

 

파라메트릭 서치는 최적화 문제를 결정문제로 바꾸어 해결하는 기법, 즉 주어진 상황에서 최소값, 최대값 등의 값을 구하는 문제를 그 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바꾸어 해결하는 기법이다. 이 기법에 의하면 중간점의 값은 시간이 지날수록 최적화된 값이 되기 때문이다. 이를테면 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제이다. 파라메트릭 서치와 이진 탐색은 비슷하게 생겼는데, 활용에 있어서 차이가 조금 있다. 

 

이진탐색은 정렬된 주어진 값 중에서 원하는 값을 찾는 알고리즘이다. (이진탐색 알고리즘을 사용하는 것에 있어 정렬은 전제조건이다.) 순차탐색을 했을 때 시간이 너무 오래걸릴 것 같으면 (ex. 탐색할 것이 몇 억을 넘어갈 경우) 이진탐색을 선택하는 것이 적절하다.

 

파라메트릭 서치는 이진탐색과 비슷한데, 결정문제로 바꿀 때 사용가능하다. 파라메트릭 서치를 사용할 수 있는 조건이 있다.

 

1. 특정 조건을 만족하는 최소값, 최대값을 구하는 형식의 문제여야 한다. 

 

2. 답의 범위가 이산적이거나 허용 오차 범위가 있어야 한다. 연속적일 경우, 답에 가까워질 수는 있으나 정확한(최적화 된) 값을 구할 수는 없기 때문이다.

 

3. 최댓값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값보다 작은 값은 모두 조건을 만족해야 한다.