[알고리즘 문제해결전략] 분할 정복

분할 정복(Divide & Conquer)이란?

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 내는 방법

일반적인 재귀 호출과 분할 정복의 차이

분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것입니다. 아래의 그림을 보면 그림 (a)는 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고, 그림 (b)는 항상 문제를 절반씩 나누는 분할 정복 알고리즘을 보여줍니다.

(그림)

분할 정복 알고리즘의 구성 요소

분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 갖고 있습니다.

• 문제를 더 작은 문제로 분할하는 과정(divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

분할 방법에 따른 시간 복잡도

무조건 절반으로 나눈다 하여 빠르다고 볼 수는 없습니다. 예를 들어 거듭제곱을 구하는 과정에서 지수가 홀수일 때 절반에 가까운 수로 나누는 방법과 홀수에서 1을 빼서 짝수로 만드는 방법 두가지가 있는 데, 전자의 경우는 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 생기게 됩니다. 이런 속성을 부분 문제가 중복된다(overlapping subproblems)고 부르며, 동적 계획법이 고안된 계기가 됩니다.

병합 정렬과 퀵 정렬

병합 정렬(Merge sort)과 퀵 정렬(Quick sort)은 분할 정복을 기반으로 하여 만들어진 가장 널리 쓰이는 정렬 알고리즘입니다.

아래에 두 정렬의 코드와 동작 과정을 설명한 포스팅의 링크를 달아두겠습니다.

병합 정렬(merge sort)

퀵 정렬(quick sort)

분할 정복을 이용하여 푼 문제들은 divide and conquer 태그를 확인하시면 찾아보실 수 있습니다.