[알고리즘] 분할정복법

Posted by 백창
2015. 10. 12. 20:08 자료구조&알고리즘/개념
반응형

# 분할정복법


 분할정복법은 문제를 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);

}

}


반응형

'자료구조&알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] 동적계획법  (0) 2015.10.22
[정렬 알고리즘] 시간복잡도  (0) 2015.10.12
Map 과 HashMap 차이  (0) 2014.12.26
[개념] 리스트  (0) 2014.11.04