parametric search 란?

(예시 문제)아래 부등식의 해를 구하시오. 1 에서 20 사이의 정수값에서 해가 나오는다는 것은 보장된다.

2*x + 10 <= 26

1. 직접적인 방법.

10 을 이항하면 
2*x <= 16
 x <= 8

2. parametric search 방법.

put: f(x) = 2*x + 10

• 1..20 의 중간 값 (1 + 20)/2 = 10
  f(10) = 2*10 + 10 = 30
  f(10) > 26 이므로 x

• 1..9 의 중간 값 (1+9)/2 = 5
  f(5) = 20
  f(5) <= 24 이므로 5 는 가능한 해

• 6 .. 9 의 중간 값 (6+9)/2 = 7
  f(7) = 14
  f(7) <= 26 을 만족. 7 도 가능한 해

• 8..9 의 중간 값 (8+9)/2 = 8
  f(8)=26
  f(9) <= 26 이므로. 8 도 가능한 해

• 9..9 의 중간 값 (9+9)/2 = 9
  f(9)=28
  f(9) > 26 이므로 x

• 9 > 8 이면 종료

답은 8

이 방법에서는 f(x) 를 구하거나 f(x) 를 구할 수 없는 경우 대입 한 값이 문제의 조건에 만족하는지를 어떻게 효율적으로 판단하는지가 관건이다.

출처: dovelet