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