분할정복(Divide and Conquer)의 원리와 설계 - soo:bak

작성일 : 2025년 12월 27일

분할정복이란?

7개의 숫자 [38, 27, 43, 3, 9, 82, 10]을 정렬해야 한다고 가정해보겠습니다.

8개를 한 번에 정렬하기는 복잡하지만, 4개씩 나누어 각각 정렬한 뒤 합치면 더 쉽습니다.

[38, 27, 43, 3, 9, 82, 10, 7]
         ↓ 분할
[38, 27, 43, 3]    [9, 82, 10, 7]
         ↓ 각각 정렬
[3, 27, 38, 43]    [7, 9, 10, 82]
         ↓ 합치기
[3, 7, 9, 10, 27, 38, 43, 82]

4개도 복잡하다면, 2개씩 나누고 또 나눕니다. 1개가 되면 이미 정렬된 것이므로, 이를 합쳐나가면 전체가 정렬됩니다.

분할정복(Divide and Conquer)은 이처럼 큰 문제를 작은 부분 문제로 나누어 해결한 뒤, 그 결과를 합쳐서 전체 문제의 답을 구하는 알고리듬 설계 기법입니다.

분할정복은 세 단계로 구성됩니다:

분할(Divide): 문제를 동일한 유형의 더 작은 부분 문제로 나눕니다.
정복(Conquer): 부분 문제가 충분히 작으면 직접 해결하고, 그렇지 않으면 재귀적으로 분할정복을 적용합니다.
결합(Combine): 부분 문제의 해를 합쳐서 원래 문제의 해를 구합니다.

세 번째 단계인 결합이 핵심입니다. 분할정복은 단순히 “나누어 푸는 것”이 아니라, 나눈 결과를 합치는 과정이 있어야 합니다.

이 기법은 많은 효율적인 알고리듬의 기반이 됩니다. 병합 정렬, 퀵 정렬, 거듭제곱의 빠른 계산, 최근접 점의 쌍 찾기 등이 분할정복을 사용합니다.

분할정복이 효과적인 이유

분할정복이 왜 효율적인지 직관적으로 이해해보겠습니다.

선형 탐색 vs 이분 탐색

1,000개의 정렬된 데이터에서 특정 값을 찾는다고 가정합니다.

선형 탐색: 최악의 경우 1,000번 비교
이분 탐색: 매번 절반을 제거하므로 최대 10번 비교

1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1
     ↓    ↓    ↓    ↓    ↓   ↓    ↓   ↓   ↓   ↓
     1    2    3    4    5   6    7   8   9   10번

핵심 아이디어: 문제의 크기를 절반으로 줄이면, 전체 단계 수가 \(\log n\)이 됩니다.

분할정복 vs 동적 계획법

두 기법 모두 문제를 부분 문제로 나누지만, 중요한 차이가 있습니다.

특성	분할정복	동적 계획법
부분 문제 중복	없음	있음
결과 저장	불필요	필요 (메모이제이션)
접근 방식	Top-down (재귀)	Top-down 또는 Bottom-up
대표 예시	병합 정렬, 퀵 정렬	피보나치 수열, 배낭 문제

분할정복에서는 부분 문제들이 서로 독립적입니다. 왼쪽 절반을 정렬하는 것과 오른쪽 절반을 정렬하는 것은 서로 영향을 주지 않습니다. 따라서 같은 부분 문제를 여러 번 풀지 않으므로 결과를 저장할 필요가 없습니다.

반면, 동적 계획법에서는 부분 문제가 중복됩니다. 예를 들어, 피보나치 수열에서 F(5)를 계산할 때 F(3)이 여러 번 필요합니다. 따라서 결과를 저장하여 재사용합니다.

F(5)를 계산할 때 F(3)이 두 번 등장 (중복)

F(5)
├── F(4)
│   ├── F(3)  ← 중복!
│   │   ├── F(2)
│   │   └── F(1)
│   └── F(2)
└── F(3)      ← 중복!
    ├── F(2)
    └── F(1)

참고 : 동적 계획법(DP)의 원리와 구현 - soo:bak

병합 정렬 (Merge Sort)

병합 정렬은 분할정복의 대표적인 예시입니다.

핵심 아이디어

배열을 반으로 나누어 각각 정렬한 뒤, 정렬된 두 배열을 하나로 합칩니다. “정렬된 두 배열을 합치는 것”은 O(n)에 가능하므로, 전체 시간 복잡도가 O(n log n)이 됩니다.

동작 과정

원본: [38, 27, 43, 3, 9, 82, 10]

[분할 단계]
[38, 27, 43, 3, 9, 82, 10]
        ↓ 분할
[38, 27, 43, 3]    [9, 82, 10]
     ↓ 분할           ↓ 분할
[38, 27] [43, 3]  [9, 82] [10]
   ↓        ↓        ↓      ↓
[38][27] [43][3]  [9][82]  [10]

[정복 & 결합 단계]
[38][27] [43][3]  [9][82]  [10]
   ↓        ↓        ↓      ↓
[27, 38] [3, 43]  [9, 82]  [10]
     ↓ 결합           ↓ 결합
[3, 27, 38, 43]    [9, 10, 82]
        ↓ 결합
[3, 9, 10, 27, 38, 43, 82]

두 정렬된 배열 합치기

정렬된 두 배열을 합치는 과정을 자세히 살펴보겠습니다.

왼쪽: [3, 27, 38, 43]  →  i = 0
오른쪽: [9, 10, 82]    →  j = 0
결과: []

단계 1: 3 < 9 → 3 선택, i++
        결과: [3]

단계 2: 27 > 9 → 9 선택, j++
        결과: [3, 9]

단계 3: 27 > 10 → 10 선택, j++
        결과: [3, 9, 10]

단계 4: 27 < 82 → 27 선택, i++
        결과: [3, 9, 10, 27]

단계 5: 38 < 82 → 38 선택, i++
        결과: [3, 9, 10, 27, 38]

단계 6: 43 < 82 → 43 선택, i++
        결과: [3, 9, 10, 27, 38, 43]

단계 7: 왼쪽 끝, 오른쪽 남은 것 추가
        결과: [3, 9, 10, 27, 38, 43, 82]

두 포인터를 사용하여 작은 값을 순서대로 선택하면 됩니다.

구현

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

// 두 정렬된 부분을 하나로 병합
// arr[left..mid]와 arr[mid+1..right]를 합침
void merge(vi& arr, int left, int mid, int right) {
  vi temp;
  int i = left, j = mid + 1;

  // 두 부분을 비교하며 작은 값부터 추가
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j])
      temp.push_back(arr[i++]);
    else
      temp.push_back(arr[j++]);
  }

  // 왼쪽에 남은 원소 추가
  while (i <= mid)
    temp.push_back(arr[i++]);

  // 오른쪽에 남은 원소 추가
  while (j <= right)
    temp.push_back(arr[j++]);

  // 원본 배열에 복사
  for (int k = left; k <= right; k++)
    arr[k] = temp[k - left];
}

void mergeSort(vi& arr, int left, int right) {
  // 기저 조건: 원소가 1개 이하면 이미 정렬됨
  if (left >= right)
    return;

  int mid = (left + right) / 2;

  mergeSort(arr, left, mid);       // 왼쪽 절반 정렬
  mergeSort(arr, mid + 1, right);  // 오른쪽 절반 정렬
  merge(arr, left, mid, right);    // 병합
}

int main() {
  vi arr = {38, 27, 43, 3, 9, 82, 10};

  mergeSort(arr, 0, arr.size() - 1);

  for (int x : arr)
    cout << x << " ";
  cout << "\n";

  return 0;
}

시간 및 공간 복잡도

시간 복잡도: O(n log n)

분할: 매 단계마다 문제를 절반으로 나누므로 log n 단계
결합: 각 단계에서 총 n개의 원소를 병합하므로 O(n)
전체: O(n) × O(log n) = O(n log n)

공간 복잡도: O(n)

병합 과정에서 임시 배열이 필요

장점:

항상 O(n log n) 보장 (최악의 경우에도)
안정 정렬 (같은 값의 상대적 순서 유지)

단점:

추가 메모리 O(n) 필요
캐시 효율이 퀵 정렬보다 낮음

참고 : 병합 정렬(Merge Sort)의 원리와 구현 - soo:bak

퀵 정렬 (Quick Sort)

퀵 정렬도 분할정복을 사용하지만, 병합 정렬과는 다른 방식으로 동작합니다.

핵심 아이디어

피벗(pivot) 을 기준으로 배열을 두 부분으로 나눕니다.

피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 보냅니다.

분할 후에는 피벗이 정확히 자기 위치에 있게 되므로, 결합 단계가 필요 없습니다.

동작 과정

원본: [3, 7, 8, 5, 2, 1, 9, 5, 4]  피벗: 5 (중간값)

[분할]
피벗 5보다 작은 것: [3, 2, 1, 4]
피벗: [5]
피벗 5보다 큰 것: [7, 8, 9, 5]

→ [3, 2, 1, 4] [5] [7, 8, 9, 5]

[각 부분에 대해 재귀적으로 정렬]
[1, 2, 3, 4] [5] [5, 7, 8, 9]

[결합 (자동)]
[1, 2, 3, 4, 5, 5, 7, 8, 9]

시간 복잡도

평균: O(n log n) 최악: O(n²) - 이미 정렬된 배열에서 첫 번째 또는 마지막 원소를 피벗으로 선택하면 발생

장점:

추가 메모리가 거의 필요 없음 (제자리 정렬)
평균적으로 빠름 (상수 계수가 작음)
캐시 효율이 좋음

단점:

최악의 경우 O(n²)
불안정 정렬

참고 : 퀵 정렬(Quick Sort)의 원리와 구현 - soo:bak

이분 탐색 (Binary Search)

이분 탐색은 분할정복의 가장 단순한 형태입니다. 문제를 두 부분으로 나눈 뒤, 하나만 탐색합니다.

동작 과정

정렬된 배열 [1, 3, 5, 7, 9, 11, 13, 15, 17]에서 11을 찾는다고 가정합니다.

[1, 3, 5, 7, 9, 11, 13, 15, 17]  목표: 11
            ↑ mid = 9

9 < 11 → 오른쪽 탐색
        [11, 13, 15, 17]
              ↑ mid = 13

13 > 11 → 왼쪽 탐색
        [11]
         ↑ mid = 11

11 == 11 → 찾음!

구현

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

// target이 있으면 인덱스 반환, 없으면 -1 반환
int binarySearch(vi& arr, int target) {
  int left = 0, right = arr.size() - 1;

  while (left <= right) {
    int mid = (left + right) / 2;

    if (arr[mid] == target)
      return mid;  // 찾음
    else if (arr[mid] < target)
      left = mid + 1;  // 오른쪽 탐색
    else
      right = mid - 1;  // 왼쪽 탐색
  }

  return -1;  // 못 찾음
}

int main() {
  vi arr = {1, 3, 5, 7, 9, 11, 13, 15, 17};
  cout << binarySearch(arr, 11) << "\n";  // 5

  return 0;
}

시간 복잡도

O(log n) - 매번 탐색 범위가 절반으로 줄어듦

참고 : 이분 탐색(Binary Search)의 원리와 구현 - soo:bak

거듭제곱의 빠른 계산

분할정복을 이용하면 \(a^n\)을 O(log n)에 계산할 수 있습니다.

핵심 아이디어

\(a^n = (a^{n/2})^2\) 라는 성질을 이용합니다.

2^16을 계산하는 방법:

[일반적인 방법] O(n)
2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2
→ 15번의 곱셈

[분할정복] O(log n)
2^16 = (2^8)^2
2^8 = (2^4)^2
2^4 = (2^2)^2
2^2 = (2^1)^2
2^1 = 2

→ 4번의 곱셈 (각 단계에서 제곱 1번)

구현

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// a^n mod m 계산
ll power(ll a, ll n, ll mod) {
  // 기저 조건: a^0 = 1
  if (n == 0)
    return 1;

  // a^(n/2) 계산
  ll half = power(a, n / 2, mod);

  // (a^(n/2))^2 계산
  ll result = (half * half) % mod;

  // n이 홀수면 a를 한 번 더 곱함
  // a^5 = a^2 × a^2 × a
  if (n % 2 == 1)
    result = (result * a) % mod;

  return result;
}

int main() {
  // 2^10 mod 1000 = 1024 mod 1000 = 24
  cout << power(2, 10, 1000) << "\n";  // 24

  return 0;
}

시간 복잡도 분석: 마스터 정리

분할정복 알고리듬의 시간 복잡도는 마스터 정리(Master Theorem) 로 분석합니다.

재귀 관계식이 다음 형태일 때:

\[T(n) = aT(n/b) + f(n)\]

a: 부분 문제의 개수
b: 문제 크기가 줄어드는 비율
f(n): 분할과 결합에 드는 비용

예시

병합 정렬: \(T(n) = 2T(n/2) + O(n)\)

a = 2 (두 부분으로 나눔)
b = 2 (각 부분의 크기가 절반)
f(n) = O(n) (병합 비용)
결과: O(n log n)

이분 탐색: \(T(n) = T(n/2) + O(1)\)

a = 1 (한 부분만 탐색)
b = 2 (탐색 범위가 절반)
f(n) = O(1) (비교 비용)
결과: O(log n)

거듭제곱: \(T(n) = T(n/2) + O(1)\)

결과: O(log n)

분할정복 적용 조건

분할정복이 효과적인 문제는 다음 특성을 가집니다:

1. 문제를 같은 유형의 작은 문제로 나눌 수 있어야 함

배열 정렬 → 왼쪽 절반 정렬 + 오른쪽 절반 정렬

2. 부분 문제의 해를 합쳐 전체 해를 구할 수 있어야 함

정렬된 두 배열을 합치면 전체가 정렬됨

3. 부분 문제들이 서로 독립적이어야 함

왼쪽 정렬이 오른쪽 정렬에 영향을 주지 않음. 중복 계산이 많으면 동적 계획법이 더 적합합니다.

마무리

분할정복은 문제를 작은 단위로 나누어 해결하는 알고리듬 설계 기법입니다.

분할, 정복, 결합의 세 단계로 구성되며, 문제 크기를 절반으로 줄이면 단계 수가 \(O(\log n)\)이 됩니다.

부분 문제가 독립적이어야 효과적이며, 병합 정렬, 빠른 정렬, 이분 탐색, 거듭제곱 등에 활용됩니다.

분할정복을 이해하면 많은 효율적인 알고리듬의 원리를 파악할 수 있습니다.

재귀 구조를 이해하고, 분할-정복-결합의 세 단계를 명확히 정의하는 것이 중요합니다.

관련 글:

관련 문제

분할정복(Divide and Conquer)의 원리와 설계 - soo:bak

분할정복이란?

분할정복이 효과적인 이유

분할정복 vs 동적 계획법

병합 정렬 (Merge Sort)

핵심 아이디어

동작 과정

두 정렬된 배열 합치기

구현

시간 및 공간 복잡도

퀵 정렬 (Quick Sort)

핵심 아이디어

동작 과정

시간 복잡도

이분 탐색 (Binary Search)

동작 과정

구현

시간 복잡도

거듭제곱의 빠른 계산

핵심 아이디어

구현

시간 복잡도 분석: 마스터 정리

예시

분할정복 적용 조건

마무리

관련 문제

[백준 14956] Philosopher’s Walk (C#, C++) - soo:bak

[백준 1891] 사분면 (C#, C++) - soo:bak

[백준 2263] 트리의 순회 (C#, C++) - soo:bak

[백준 1992] 쿼드트리 (C#, C++) - soo:bak

분할정복이란?

분할정복이 효과적인 이유

분할정복 vs 동적 계획법

병합 정렬 (Merge Sort)

핵심 아이디어

동작 과정

두 정렬된 배열 합치기

구현

시간 및 공간 복잡도

퀵 정렬 (Quick Sort)

핵심 아이디어

동작 과정

시간 복잡도

이분 탐색 (Binary Search)

동작 과정

구현

시간 복잡도

거듭제곱의 빠른 계산

핵심 아이디어

구현

시간 복잡도 분석: 마스터 정리

예시

분할정복 적용 조건

마무리

관련 문제 풀이

관련 문제

[백준 14956] Philosopher’s Walk (C#, C++) - soo:bak

[백준 1891] 사분면 (C#, C++) - soo:bak

[백준 2263] 트리의 순회 (C#, C++) - soo:bak

[백준 1992] 쿼드트리 (C#, C++) - soo:bak