[목차] == 개요 == 분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 [[정렬 알고리즘#s-2.2.3|퀵소트]] 나 [[정렬 알고리즘#s-2.2.1|병합정렬]]이 있다. 그 외에 [[오토마타]]에서도 top-down parser등의 개념을 위하여 이용된다. [[파일:5-22-2.png|width=500]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.548, 책만, 2020 그림에서와 같이 분할 정복법은 상단에서 '''분할'''하고 중앙에서 '''정복'''하고 하단에서 '''조합(Combine)'''하는 형태로 도식화 할 수 있다. * 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. * 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. * 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. 폰 노이만이 병합 정렬을 통해 분할 정복을 설명한 것은 1945년이었는데, 사실 문제를 축소해서 정복한다는 개념의 역사는 훨씬 더 이전인 기원 전까지 거슬러 올라간다. 고대 그리스의 수학자 유클리드(Euclid)는 자신이 저술한 『원론』에서 문제를 분할해 풀이하는 최대 공약수 알고리즘을 정리했으며, 이 유클리드 알고리즘은 인류 최초의 알고리즘으로 일컬어진다. == 적용 방식 == 분할 정복법은 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식이다. 예를 들어 {{{ 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)가 간단"이라는 조건을 만족할 때까지 문제를 쪼개고 쪼개서 값을 구하자는 것이다. == 장점 == 당연하겠지만 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 ~~엄청나게 중요한~~ 장점이 있다. 그리고 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며[* 대표적으로 합병정렬은 O(n log n)이다. 그것도 최악의 경우에도 말이다.], 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다. == 단점 == 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 [[버퍼 오버플로|스택 오버플로우]]가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있다[* 일반적으로 [[메모이제이션]]을 사용함으로써 해결한다.]. 가장 중요한 것은 이 알고리즘의 핵심인 "F(x)가 간단"이 어떤 것이냐에 따라 알고리즘의 퍼포먼스가 생각보다 꽤 차이나게 된다는 것이다. 이 "F(x)가 간단하다"라는 것을 정의하는 것의 난해함 역시 단점 중에서 중요하게 다루어지고 있다. == 예시 == * [[정렬 알고리즘#s-2.2.3|퀵소트]] * [[정렬 알고리즘#s-2.2.1|합병정렬]] * [[푸리에 해석#s-3|고속 푸리에 변환]] * [[카라추바 알고리즘]] [[분류:알고리즘]]