# 분할 정복 알고리즘

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

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

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

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

![병합 정렬의 분할 정복 전략](divide_and_conquer.assets/divide_and_conquer_merge_sort.png)

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

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

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

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

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

## 분할 정복으로 효율 높이기

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

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

### 연산 수 최적화

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

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

![배열 분할 전후의 버블 정렬](divide_and_conquer.assets/divide_and_conquer_bubble_sort.png)

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

$$
\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)$에 이를 수 있다.

### 병렬 계산 최적화

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

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

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

![버킷 정렬의 병렬 계산](divide_and_conquer.assets/divide_and_conquer_parallel_computing.png)

## 분할 정복의 주요 응용

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

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

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

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

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