1. 개요
분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다. 그 외에 오토마타에서도 top-down parser등의 개념을 위하여 이용된다. 어원은 로마 제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분할통치(Divide and Rule).그림에서와 같이 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합(Combine)하는 형태로 도식화 할 수 있다.
- 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
- 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
- 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
폰 노이만이 병합 정렬을 통해 분할 정복을 설명한 것은 1945년이었는데, 사실 문제를 축소해서 정복한다는 개념의 역사는 훨씬 더 이전인 기원 전까지 거슬러 올라간다. 고대 그리스의 수학자 유클리드(Euclid)는 자신이 저술한 『원론』에서 문제를 분할해 풀이하는 최대 공약수 알고리즘을 정리했으며, 이 유클리드 알고리즘은 인류 최초의 알고리즘으로 일컬어진다.
또한 뉴턴도 divide and conquer와 비슷한 아이디어로 미분을 개발했다. 잘게 쪼개어 합한후 극한으로 보낸다는 말은 고등학교 수학시간에 주구장창 들었을것이다.
2. 적용 방식
분할 정복법은 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식이다. 분할 정복의 프로세스는 대체로 아래와 같다.function F(x):
if F(x)가 간단 then:
return F(x)를 계산한 값
else:
x 를 x1, x2로 분할
F(x1)과 F(x2)를 호출
return F(x1), F(x2)로 F(x)를 구한 값
한 마디로 "F(x)가 간단"이라는 조건을 만족할 때까지 문제를 쪼개고 쪼개서 값을 구하자는 것이다.