[알고리즘] 파라메트릭 서치(Parametric Search)

1. 파라메트릭 서치(Parametric Search)란?

• 최적화 문제를 결정 문제로 바꾸어 푸는 기법
  • 최적화 문제 : 결과값을 최소화 또는 최대화 해야하는 문제
    (ex. f(x) = True가 되는 x의 최댓값을 구하시오.)
  • 결정 문제 : '예' 또는 '아니오'로 답하는 문제
    (ex. 어떤 값 x에 대해서 f(x) = True인가?)
• 주로 특정 조건을 만족하면서 동시에 가장 적합한 변수값을 찾아나가는 문제에서 활용
• 이진 탐색(Binary Search)을 이용해 구현

2. 파라메트릭 서치 사용 조건

• 특정 조건을 만족하는 최댓값 또는 최솟값을 구하는 형식의 문제여야 한다.
• 최댓값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값 미만의 값도 모두 조건을 만족해야 한다.
  최소값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값을 초과하는 값도 모두 조건을 만족해야 한다.
• 답의 범위가 이산적이거나 허용 오차 범위가 있어야 한다.
  • 이분탐색으로는 연속적 범위에서 정답에 한없이 가까워질 수는 있지만 완전히 정확한 값은 구할 수 X

  ---

3. 이진 탐색과 파라메트릭 서치의 차이점

• 이진 탐색 : 주어진 일련의 값들 중 원하는 조건과 일치하는 값을 찾아내는 알고리즘
  • ex. [1, 3, 4, 5, 8, 10]의 값들 중에서 3이라는 값 찾아내기
• 파라메트릭 서치 : 주어진 일련의 연속적 범위 내에서 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘
  • ex. 1 ~ 9 범위 내에서 3을 초과하는 가장 큰 값을 찾아내기
• 결정 문제인지 아닌지가 가장 큰 차이점.

4. 예시 문제

• 백준 1654번 : 랜선 자르기 (https://www.acmicpc.net/problem/1654)
• 백준 2805번 : 나무 자르기 (https://www.acmicpc.net/problem/2805)

👁️‍🗨️ 참고
https://heytech.tistory.com/97
https://velog.io/@sorzzzzy/Algorithm-이진탐색-파라메트릭-서치