파라메트릭 서치(Parametric Search) 알고리즘이란?

이진 탐색(Binary Search)을 활용하여 최적화 문제를 결정 문제(decision problem)으로 바꾼 뒤, 이것을 이분법(이진 탐색과 비슷하게 수치 해석 문제를 해결하는 기법)을 이용해 해결하는 방법이다.

• 결정 문제란 true 혹은 false 형태의 답만이 나오는 문제들을 가리킨다.

  
  

파라메트릭 서치 진행 과정:

1. 가능한 매개변수 값의 범위를 결정

2. 범위 내에서 중간값을 선택하고, 그 값을 기준으로 문제를 풉니다.

3. 선택한 값이 최적해인지 확인.

4. 만약 아니라면, 범위를 좁혀서 다시 탐색.

예를 들어, 정렬된 배열에서 특정 값을 찾는 문제가 있다면 파라메트릭 서치 알고리즘은 배열의 중간값을 선택하고, 찾으려는 값이 중간값보다 큰지 작은지 비교하여 탐색 범위를 반으로 줄인다.

 또 다른 예로, 최소 또는 최대 비용을 구하는 문제가 있다면 파라메트릭 서치 알고리즘은 가능한 비용 범위에서 중간값을 선택하고, 그 비용으로 문제를 풀어 보아 결과가 충분히 좋거나 나쁜지 판단하여 비용의 범위를 좁혀나간다.

파라메트릭 서치 알고리즘은 시간복잡도 O(logN)을 지니며 문제 해결에 효율적인 방법입니다. 하지만 모든 종류의 문제에 적합하지 않으며 주로 연속된 공간 내에서 최적해를 찾아야 하는 경우에 사용됩니다.

다시 풀어 보기 : 프로그래머스 level3 징검다리 건너기