[알고리즘] 분할정복법

# 분할정복법

 분할정복법은 문제를 2개 이상의 더 작은 문제들로 나누어 해결한다. 작은 문제가 여전히 크다면 더 작은 문제들로 계속해서 나눈다. 작은 문제에 대한 해답을 바로 얻을 수 있다면 원래 문제의 해답은 이 해답들을 통합하여 구할 수 있다.

 

  분할정복법은 하향식 접근 방법(top-down)이다. 즉, 문제의 맨 상위 사례의 해답은 아래로 내려가서 작은 사례에 대한 해답을 구함으로써 구한다.

  재귀 함수가 이에 해당한다.

# 예시

  실례로는 binary search가 있다.

  값을 찾기 위해 계속해서 반절로 문제를 쪼개어 해답을 찾는다.

index location(index low, index high) {

index mid;

if(low > high)

return 0;

else {

mid = (low+high)/2;

if( x == S[mid] )

return mid;

else if( x < S[mid )

return location(low, mid - 1);

else

return location(mid + 1, high);

}

}