40. Parametric Search

매개변수 탐색(Parametric Search)은 최적화 문제를 결정 문제로 변형한 뒤 이분 탐색, 삼분 탐색 등을 이용하여 답을 찾아내는 탐색 방법이다. 예를 들어 어떤 함수 $f(x)$가 특정 구간에서 증가하고 $f(x)$가 $k$ 이상이 되는 최소의 $x$를 찾아야 할 경우 해결해야 하는 것은 주어진 조건을 만족하는 $x$의 최소값이므로 이것은 최적화 문제이다. 하지만 단순히 $f(x)$가 $k$ 이상인지를 판별하는 것은 참, 거짓만 확인하면 되므로 결정 문제가 된다. 또한 이 결정 문제의 답은 $x$가 특정 값보다 작다면 거짓, 그렇지 않다면 참이므로 참, 거짓의 기준이 되는 $x$를 이분 탐색으로 찾아낼 수 있다. 이 방법을 응용하면 일부 조건이 '최대의 $x$', '$k$ 초과', '$k$ 미만', '$k$ 이하', '감소함수' 등으로 달라지더라도 문제를 해결할 수 있다.

 

[연습문제]

 

BOJ 1654. 랜선 자르기 (Silver III)

매개변수 탐색으로 풀 수 있는 가장 기본적인 문제 중 하나이다. $f(x)$ = '만들 랜선의 길이가 $x$일 때 기존의 랜선에서 그 길이의 랜선을 만들 수 있는 최대 개수'라고 정의하면 $f(x)$는 감소함수이고, $f(x)$에 대한 이분 탐색으로 답을 구할 수 있다.

 

BOJ 2110. 공유기 설치 (Silver I)

$f(x)$를 '각각의 공유기 사이의 거리가 $x$ 이상이 되게 할 때 설치할 수 있는 공유기의 최대 개수'라고 정의하면 $f(x)$는 감소함수이고, $f(x)$가 $c$ 이상이 되는 $x$의 최대값을 $f(x)$에 대한 이분 탐색으로 구할 수 있다.

 

BOJ 1300. K번째 수 (Gold III)

$f(x)$를 '$A$ 배열에서 $x$ 이하인 값의 개수'로 정의하면 $f(x)$는 증가함수이고, $f(x)$가 $k$ 이상이 되는 $x$의 최소값을 $f(x)$에 대한 이분 탐색으로 구할 수 있다.

 

BOJ 6209. 제자리 멀리뛰기 (Gold II)

$f(x)$를 '학생들의 점프 거리가 항상 $x$ 이상일 때 밟을 수 있는 돌의 최대 개수'라고 정의하면 $f(x)$는 감소함수이고, $f(x)$가 $n-m$ 이상이 되는 $x$의 최대값을 $f(x)$에 대한 이분 탐색으로 구할 수 있다.

 

→ solved.ac tag: parametric_search