분할 정복법

분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트 나 병합정렬이 있다. 그 외에 오토마타에서도 top-down parser등의 개념을 위하여 이용된다.

파일:5-22-2.png
<파이썬 알고리즘 인터뷰> 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)가 간단"이라는 조건을 만족할 때까지 문제를 쪼개고 쪼개서 값을 구하자는 것이다.

당연하겠지만 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 엄청나게 중요한 장점이 있다. 그리고 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며[1], 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.

함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있다[2]. 가장 중요한 것은 이 알고리즘의 핵심인 "F(x)가 간단"이 어떤 것이냐에 따라 알고리즘의 퍼포먼스가 생각보다 꽤 차이나게 된다는 것이다. 이 "F(x)가 간단하다"라는 것을 정의하는 것의 난해함 역시 단점 중에서 중요하게 다루어지고 있다.