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

작성일 : 2025년 12월 27일

분할정복이란?

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

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)

동작 과정

구현

시간 복잡도

거듭제곱의 빠른 계산

핵심 아이디어

구현

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

예시

분할정복 적용 조건

마무리

이 블로그의 다른 글

[백준 4892] 숫자 맞추기 게임 (C#, C++) - soo:bak

[백준 3276] ICONS (C#, C++) - soo:bak

[백준 2609] 최대공약수와 최소공배수 (C#, C++) - soo:bak

[백준 2291] Sequence (C#, C++) - soo:bak