이분/삼분 탐색과 구현

2015. 7. 7. 01:02알고리즘 문제풀기/이·삼분탐색

1. 이분 탐색

이분 탐색이란 탐색의 범위를 절반으로 줄여나가는 방법을 말한다.

결정 문제
답이 yes 혹은 no로 나오는 문제.

일반적으로 이분탐색으로 풀 수 있는 문제들은

  • 우리가 정할 수 있는 어떤 값 x가 있다.
  • x에 따라, 어떤 결정 문제의 yes/no가 정해진다.
  • 문제에서는 그 값이 yes가 나오는 최소/최대의 x를 요구한다.
  • x에 의한 결과는 연속적으로 변한다. 즉, x의 값이 증가/감소하다보면, 어느 순간 yes가 no로 바뀐다.
  • 즉, x일때 yes이면 x+1(혹은 x-1)일때 no이다.

이러한 성질들을 만족한다.
O와 X의 경계를 찾는 것이 목적인 문제이다.

l-4 l-3 l-2 l-1 l r r+1 r+2 r+3
O O O O O X X X X

KOI 2012 중,고등부 1번 : 예산 (acmicpc.net 링크, dovelet 옥상에서 koi_money와 koi_budget 둘다)

이 문제와 비교해보자.

  1. 우리는 정수 상한액을 정할 수 있다.
  2. “해당 상한액을 설정했을 때 필요한 예산이 M을 넘지 않는다”
  3. 최대를 요구한다
  4. 특정 상한액을 배정할 수 있었다면, 그보다 더 작은 상한액을 배정했을 때 필요한 예산은 더 적으므로 당연히 가능하다.

이들은 ‘이 문제를 이분 탐색으로 풀 수 있다!’라는 추측을 하는데에 아주 큰 도움이 된다.

이제 이분 탐색의 원리를 알아보자.
이분 탐색은 앞에서 말한듯이 탐색의 범위를 절반으로 줄인다.
탐색의 범위라는 것은 ‘이 안에 경계가 있다!’라는 뜻이다.
탐색의 범위가 [l,r] 이라고 하자. 또한 l의 값은 yes, r의 값은 no라고 하자.

그러면 lr 사이에는 경계가 반드시 있다. ( (4)에서 연속적이므로 )
lr 사이의 어떤 m을 잡고, m에 의한 결과가 yes인지 no인지 살펴본다.

  1. m이 yes이면…
    l ~ m까지는 모두 yes이므로 경계는 이 안에 없다.
    따라서 경계는 [m,r]에 대해 탐색하면 구할 수 있을 것이다.
    r=m;으로 만들어도 된다.
  2. m이 no이면…
    m ~ r까지는 모두 no이므로 경계가 아니다.
    따라서 경계는 [l,m]에 대해 탐색하면 구할 수 있을 것이다.
    l=m;으로 만들어도 된다.

이 과정을 한 번 거치면, 여전히 l은 yes, r은 no를 유지하면서, 탐색 범위가 조금 더 줄어든다.
또한 l+1 == r이 되는 순간 우리는 우리가 원했던 ‘경계’를 찾게 될 것이다.
m을 항상 로 만들면 탐색 범위가 항상 절반에 가깝게 줄어들기 때문에, 처음의 탐색 범위가 라고 하면 약 번의 탐색만 거치면 ‘경계’를 찾을 수 있다.
구현은 간단하다.

while(l+1 != r){
    m=(l+r)/2;
    (f(m)?l:r)=m;
}

참고로 예산 문제는 이분 탐색 이외의 풀이가 존재한다.

2. 삼분 탐색

(작성중)


참고로, parametric search라고 부르는 것은 이/삼분탐색을 지칭하기보다는 (2)의 성질을 말한다.
x라는 parameter(인수)에 의해 나오는 어떤 값을 이용하여 원하는 것을 찾는(search) 알고리즘인 것이다.
[l,r] 사이의 모든 x에 대해서 다 테스트해보고 경계를 찾아도 parametric search라고 말할 수 있을 것이다.
다만 많은 경우 모두 테스트하기에는 오래 걸리고, 그러한 문제를 이/삼분탐색으로 해결하는 경우가 많기 때문에, ‘파라메트릭’을 이/삼분 탐색의 대명사로 쓰는 경우가 잦다.

'알고리즘 문제풀기 > 이·삼분탐색' 카테고리의 다른 글

이분/삼분 탐색과 구현  (0) 2015.07.07
1