Parametric Search(파라메트릭 서치)

Parametric Search (파라메트릭 서치)

[개요]

이진탐색의 응용 버전.

최소값이나 최대값 등의 최적해 문제를 구할 때 유용하게 쓸 수 있다.

혹자는 이것을 

최적화문제 = 이진탐색 + 결정문제 (Yes or No) 로 쪼개는 것이라고 표현하기도 한다.

[기본 뼈대]

1. 이진탐색을 이용해 임의의 값 계산(보통 mid값이다)

2. 이 값은 문제의 조건을 만족합니까 안합니까? 

3. 문제 조건을 만족할시 일단 저장해두고 범위를 좁혀가면서 최적화된 해에 도달  

[전제 조건]

이 서치를 적용하려면 해의 구간이 연속적이어야한다.

만일 mid가 문제의 조건을 만족한다면, [Left,mid] 혹은 [mid,Right] 범위에 있는 해는 모두 문제의 조건을 만족할 만한 '가능성'을 가지고 있어야한다.

당연한 얘기긴 한데, 5를 mid값으로 했을 때 오른쪽 부분은 5보다 크다는 보장이 있고 왼쪽 부분은 5보다 작다는 보장이 있는 것처럼. 

[참고하면 좋은 문제]

나는 백준 2110번 공유기 설치 문제를 풀면서 이에 대해 공부했었다.