Parametric Search

1. 정의

• 조건을 만족한는 최소/최댓값을 구하는 문제(최적화 문제)를 결정문제로 ****변환하여 이분탐색을 수행하는 탐색법

 

2. 적용하기 전 확인해야 할 것

• 최적화 문제를 결정 문제로 바꿀 수 있는지 확인하기
  • 최적화 문제 : 여러가지 경우의 수 중 최적의 해를 찾는 문제, 여러 경우의 수가 존재
  • 결정 문제 : 예/아니오 두 가지의 결정만이 있는 문제
  • ex
    • 어떤문제에서 최대가 되는 x를 구하고자 한다. y이상일 때 문제가 해결되는 지 알고 싶다. ⇒ 최대가 되는 x값을 구하는 문제(최적화 문제)를 y이상일 때 되는지 안 되는지(결정문제) 로 변경
• 이 결정 문제로 얻어낸 함수가 감소 혹은 증가 함수인지 따져봐야한다.
  • ex
    • 최소 혹은 최대라는 얘기가 있는 경우
    • 범위가 무지막지하게 큰 경우
    • 시간 복잡도에서 값 하나를 로그로 어떻게 잘 떨구면 될 것 같을 때

•  
• 가능한 결정함수

• 불가능한 결정함수