분할 정복 알고리즘 편집하기 (부분)

== 개요 ==
[[파일:분할 정복 개요도.png|섬네일|분할 정복 개요 도식]]
그림에서와 같이 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합(Combine)하는 형태로 도식화 할 수 있다.

# '''분할''': 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
# '''정복''': 가장 작은 단위의 하위 문제를 해결하여 정복한다.
# '''조합''': 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

[[폰 노이만]]이 병합 정렬을 통해 분할 정복을 설명한 것은 1945년이었는데, 사실 문제를 축소해서 정복한다는 개념의 역사는 훨씬 더 이전인 기원 전까지 거슬러 올라간다. 고대 그리스의 수학자 유클리드(Euclid)는 자신이 저술한 『원론』에서 문제를 분할해 풀이하는 최대 공약수 알고리즘을 정리했으며, 이 유클리드 알고리즘은 인류 최초의 알고리즘으로 일컬어진다.

또한 뉴턴도 분할 정복과 비슷한 아이디어로 미분을 개발했다. 잘게 쪼개어 합한후 극한으로 보낸다는 말은 고등학교 수학시간에 주구장창 들었을것이다.