분할 정복법
1. 개요
분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트 나 병합정렬이 있다. 그 외에 오토마타에서도 top-down parser등의 개념을 위하여 이용된다.
[image]
<파이썬 알고리즘 인터뷰> p.548, 책만, 2020
그림에서와 같이 분할 정복법은 상단에서 '''분할'''하고 중앙에서 '''정복'''하고 하단에서 '''조합(Combine)'''하는 형태로 도식화 할 수 있다.
- 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
- 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
- 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
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)를 구한 값3. 장점
당연하겠지만 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 장점이 있다. 그리고 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며[1], 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.
4. 단점
함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있다[2]. 가장 중요한 것은 이 알고리즘의 핵심인 "F(x)가 간단"이 어떤 것이냐에 따라 알고리즘의 퍼포먼스가 생각보다 꽤 차이나게 된다는 것이다. 이 "F(x)가 간단하다"라는 것을 정의하는 것의 난해함 역시 단점 중에서 중요하게 다루어지고 있다.