12.1 분할 정복 알고리즘¶

분할 정복(divide and conquer)은 '나누어 해결한다'는 뜻으로, 매우 중요하고 흔히 쓰이는 알고리즘 전략이다. 보통 재귀로 구현하며 '분할'과 '정복'의 두 단계로 이루어진다.

분할(나누는 단계): 원래 문제를 둘 이상의 부분 문제로 재귀적으로 나누고, 가장 작은 부분 문제에 도달하면 멈춘다.
정복(합치는 단계): 해를 이미 아는 가장 작은 부분 문제부터 시작하여 아래에서 위로 부분 문제의 해를 합침으로써 원래 문제의 해를 구성한다.

아래 그림(12-1)의 '병합 정렬'은 분할 정복 전략의 대표적인 응용이다.

분할: 원래 배열(원래 문제)을 두 부분 배열(부분 문제)로 재귀적으로 나누고, 부분 배열에 원소가 하나만 남으면(가장 작은 부분 문제) 멈춘다.
정복: 정렬된 부분 배열(부분 문제의 해)을 아래에서 위로 합쳐 정렬된 원래 배열(원래 문제의 해)을 얻는다.

병합 정렬의 분할 정복 전략

그림 12-1 병합 정렬의 분할 정복 전략

12.1.1 분할 정복 문제를 판단하는 방법¶

문제가 분할 정복에 적합한지는 보통 다음 기준으로 판단할 수 있다.

문제를 나눌 수 있다: 원래 문제를 크기가 더 작고 형태가 비슷한 부분 문제로 나눌 수 있으며, 같은 방식으로 재귀적으로 나눌 수 있다.
부분 문제가 독립적이다: 부분 문제들이 겹치지 않고 서로 의존하지 않으며, 독립적으로 해결할 수 있다.
부분 문제의 해를 합칠 수 있다: 부분 문제의 해를 합쳐 원래 문제의 해를 얻는다.

병합 정렬은 위 세 기준을 모두 만족한다.

문제를 나눌 수 있다: 배열(원래 문제)을 두 부분 배열(부분 문제)로 재귀적으로 나눈다.
부분 문제가 독립적이다: 각 부분 배열을 독립적으로 정렬할 수 있다(부분 문제를 독립적으로 해결할 수 있다).
부분 문제의 해를 합칠 수 있다: 정렬된 두 부분 배열(부분 문제의 해)을 하나의 정렬된 배열(원래 문제의 해)로 합칠 수 있다.

12.1.2 분할 정복으로 효율 높이기¶

분할 정복은 알고리즘 문제를 효과적으로 해결할 뿐 아니라 효율을 높이는 경우도 많다. 퀵 정렬, 병합 정렬, 힙 정렬이 선택 정렬, 버블 정렬, 삽입 정렬보다 빠른 이유도 분할 정복 전략을 사용하기 때문이다.

여기서 궁금해진다. 분할 정복이 알고리즘의 효율을 높이는 근본적인 원리는 무엇일까? 큰 문제를 여러 부분 문제로 나누고, 부분 문제를 해결하고, 그 해를 합쳐 원래 문제의 해를 구하는 과정이 왜 원래 문제를 직접 푸는 것보다 효율적일까? 연산 수와 병렬 계산이라는 두 관점에서 살펴볼 수 있다.

1. 연산 수 최적화¶

'버블 정렬'은 길이 \(n\)의 배열을 처리하는 데 \(O(n^2)\) 시간이 걸린다. 아래 그림(12-2)처럼 중간에서 두 부분 배열로 나눈다고 하자. 분할에는 \(O(n)\) 시간, 각 부분 배열의 정렬에는 \(O((n / 2)^2)\) 시간, 두 부분 배열의 병합에는 \(O(n)\) 시간이 걸리므로 전체 시간 복잡도는 다음과 같다.

\[ O(n + (\frac{n}{2})^2 \times 2 + n) = O(\frac{n^2}{2} + 2n) \]

배열 분할 전후의 버블 정렬

그림 12-2 배열 분할 전후의 버블 정렬

이어서 왼쪽은 분할 전, 오른쪽은 분할 후의 총연산 수를 나타내는 다음 부등식을 계산해 보자.

\[ \begin{aligned} n^2 & > \frac{n^2}{2} + 2n \newline n^2 - \frac{n^2}{2} - 2n & > 0 \newline n(n - 4) & > 0 \end{aligned} \]

이는 \(n > 4\)일 때 분할 후의 연산 수가 더 적어 정렬 효율이 높아질 것임을 뜻한다. 분할 후에도 시간 복잡도는 여전히 이차인 \(O(n^2)\)이며, 상수항만 작아졌다는 점에 주의하자.

여기서 더 나아가 부분 배열을 계속 중간에서 두 개로 나누고, 원소가 하나만 남을 때까지 반복하면 어떨까? 이 발상은 바로 '병합 정렬'이며 시간 복잡도는 \(O(n \log n)\)이다.

다시 생각해 보자. 분할 지점을 더 많이 두어 원래 배열을 \(k\) 개의 부분 배열로 고르게 나누면 어떨까? 이는 '버킷 정렬'과 매우 비슷하다. 대규모 데이터 정렬에 적합하며 이론적으로 시간 복잡도가 \(O(n + k)\)에 이를 수 있다.

2. 병렬 계산 최적화¶

분할 정복으로 만들어진 부분 문제는 서로 독립적이므로 보통 병렬로 해결할 수 있다. 즉, 분할 정복은 알고리즘의 시간 복잡도를 줄일 뿐 아니라 운영체제의 병렬 최적화에도 유리하다.

병렬 최적화는 멀티코어나 다중 프로세서 환경에서 특히 효과적이다. 여러 부분 문제를 동시에 처리하여 계산 자원을 더 충분히 활용하고 전체 실행 시간을 크게 줄일 수 있기 때문이다.

예를 들어 아래 그림(12-3)의 '버킷 정렬'에서 대규모 데이터를 각 버킷에 고르게 분배하면, 버킷별 정렬 작업을 여러 계산 장치에 나누어 맡긴 뒤 결과를 합칠 수 있다.

버킷 정렬의 병렬 계산

그림 12-3 버킷 정렬의 병렬 계산

12.1.3 분할 정복의 주요 응용¶

분할 정복은 여러 대표적인 알고리즘 문제를 해결할 수 있다.

가장 가까운 점 쌍 찾기: 먼저 점 집합을 두 부분으로 나누고 각 부분에서 가장 가까운 점 쌍을 찾은 뒤, 마지막으로 두 부분에 걸쳐 있는 가장 가까운 점 쌍을 찾는다.
큰 정수의 곱셈: Karatsuba 알고리즘은 큰 정수의 곱셈을 더 작은 정수들의 곱셈과 덧셈으로 나눈다.
행렬 곱셈: Strassen 알고리즘은 큰 행렬의 곱셈을 작은 행렬들의 곱셈과 덧셈으로 나눈다.
하노이의 탑 문제: 재귀로 해결할 수 있는 하노이의 탑은 분할 정복 전략의 대표적인 응용이다.
역전 쌍 구하기: 수열에서 앞의 수가 뒤의 수보다 크면 두 수가 역전 쌍을 이룬다. 역전 쌍 문제는 분할 정복의 아이디어로 병합 정렬을 이용하여 해결할 수 있다.

또한 분할 정복은 알고리즘과 자료 구조의 설계에도 매우 널리 쓰인다.

이진 탐색: 정렬된 배열을 중간 인덱스에서 두 부분으로 나누고, 목표 값과 중간 원소를 비교한 결과에 따라 제외할 절반을 정한다. 남은 구간에서 같은 이진 탐색 연산을 수행한다.
병합 정렬: 이 절의 앞부분에서 소개했으므로 다시 설명하지 않는다.
퀵 정렬: 피벗을 하나 고르고 피벗보다 작은 원소와 큰 원소를 각각 두 부분 배열로 나눈다. 부분 배열에 원소가 하나만 남을 때까지 같은 분할을 반복한다.
버킷 정렬: 데이터를 여러 버킷에 분산하고 각 버킷의 원소를 정렬한 뒤, 버킷별 원소를 차례로 꺼내 정렬된 배열을 얻는다.
트리: 이진 탐색 트리, AVL 트리, 레드-블랙 트리, B 트리, B+ 트리 등의 탐색, 삽입, 삭제 연산은 모두 분할 정복 전략의 응용으로 볼 수 있다.
힙: 특수한 완전 이진 트리인 힙의 삽입, 삭제, 재정렬 등에도 분할 정복의 아이디어가 숨어 있다.
해시 테이블: 분할 정복을 직접 적용하지는 않지만 일부 해시 충돌 해결 방법에는 간접적으로 사용된다. 예를 들어 체이닝의 긴 연결 리스트를 레드-블랙 트리로 바꾸어 조회 효율을 높인다.

이처럼 분할 정복은 조용히 스며들어 작용하는 알고리즘 사고방식이며, 다양한 알고리즘과 자료 구조 속에 숨어 있다.