![[알고리즘] 분할정복, 동적 프로그래밍 조사-1](http://images.happyhaksul.com/thumb/651/650712-0001.gif)
![[알고리즘] 분할정복, 동적 프로그래밍 조사-2](http://images.happyhaksul.com/thumb/651/650712-0002.gif)
![[알고리즘] 분할정복, 동적 프로그래밍 조사-3](http://images.happyhaksul.com/thumb/651/650712-0003.gif)
![[알고리즘] 분할정복, 동적 프로그래밍 조사-4](http://images.happyhaksul.com/thumb/651/650712-0004.gif)
![[알고리즘] 분할정복, 동적 프로그래밍 조사-5](http://images.happyhaksul.com/thumb/651/650712-0005.gif)
![[알고리즘] 분할정복, 동적 프로그래밍 조사-6](http://images.happyhaksul.com/thumb/651/650712-0006.gif)
![[알고리즘] 분할정복, 동적 프로그래밍 조사-7](http://images.happyhaksul.com/thumb/651/650712-0007.gif)
![[알고리즘] 분할정복, 동적 프로그래밍 조사-8](http://images.happyhaksul.com/thumb/651/650712-0008.gif)
분야
docx분할정복법은 주어진 문제를 작은 사례로 나누어(Divide) 각각의 작은 문제들을 해결(Conquer)하는 방법이다.
1805년 12월 2일 아우스터리츠 전투에서 프랑스의 황제 나폴레옹은 숫자면에서 우세했던 연합군을 물리치기 위해서 나폴레옹은 연합군의 중앙으로 쳐들어가 그들의 병력을 둘로 갈라 놓았고, 둘로 나누어진 병력은 개별적으로는 나폴레옹의 군대보다 숫자가 적었기 때문에 전투는 나폴레옹의 승리로 끝나게 되었다.
분할정복법은 위와 같은 사례를 프로그램에 이용한 것이다. 문제의 사례를 2개 이상의 더 작은 사례로 나눈다. 이 작은 사례는 주로 원래 문제에서 따온다. 나눈 작은 사례의 해답을 바로 얻을 수 있으면 해를 구하고 아니면 더 작은 사례로 나눈다. 이처럼 해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법이다. 또한 분할정복법은 하향식(top-down)접근 방법이다. 즉, 문제의 최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다. 그렇기 때문에 분할정복법을 해결할때는 재귀적 방법이 많이 쓰인다.
