[알고리즘] 분할정복(Divide and Conquer)의 개념과 이해

이 글은 분할정복에 대해 정리한 글입니다.

---

📖 분할정복이란?

➡️ 분할정복(Divide and Conquer)은 컴퓨터 과학, 특히 알고리즘 분야에서 매우 중요한 기법 중 하나로, 복잡한 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 해결한 뒤, 그 결과를 합쳐 원래의 문제를 푸는 전략을 의미

큰 문제를 작은 문제로 나누어(분할), 각각을 풀고(정복), 결과를 합쳐(결합)서 전체 문제를 푸는 방법!

⚡ 분할정복의 기본 원리와 단계

출처: https://rusyasoft.github.io/algorithms/2018/07/29/cormen-divide-and-conquer/

분할정복은 기본적을 분할(Divide), 정복(Conquer), 결합(Combine) 3단계로 이루어진다.

📌 분할 (Divide)

• 문제를 두 개 이상, 더 작은 부분 문제들로 쪼갠다.
• 이때 쪼개는 방식은 문제의 성격에 따라 다르게 적용한다.
  • ex. 배열을 절반씩 나누기, 수를 두 수로 쪼개기 등

📌 정복 (Conquer)

• 각 부분 문제를 재귀적으로 해결한다.
• 부분 문제가 더 이상 쪼갤 수 없을 만큼 작아지면, 직접 답을 구한다. (= 기저조건(base case)라고 한다.)
  • ex. 배열의 크기가 1이면, 이미 정렬된 상태

📌 결합 (Combine)

• 부분 문제들의 결과를 결합하여 전체 문제의 정답을 만든다.
• 어떻게 결합하느냐는 문제마다 다르며, 결합 단계가 없으면 단순 재귀와 다르지 않다.
  • ex. 정렬된 두 배열을 하나로 합치기 (병합정렬의 병합 단계), 두 개의 합을 더하기 등

---

⚙️ 구조적인 구현 방법

• 분할정복은 재귀함수를 자주 사용

ReturnType DivideAndConquer(문제 입력) {
    if (base case) { // 쪼갤 수 없으면
        return 정답;
    }

    // 1. 문제 분할
    부분문제1 = ...;
    부분문제2 = ...;

    // 2. 각각 정복(재귀 호출)
    해1 = DivideAndConquer(부분문제1);
    해2 = DivideAndConquer(부분문제2);

    // 3. 결합
    return Combine(해1, 해2);
}

✒️ 실제 예시: 배열의 최대값 찾기 (분할정복)

• 배열 전체에서 최대값을 찾는다.
• 배열을 절반으로 나눠, 각 절반에서 최대값을 재귀적으로 찾고, 두 값을 비교해서 큰 값을 반환한다.

int findMax(vector<int>& arr, int left, int right) {
    if (left == right) return arr[left]; // base case: 원소 1개

    int mid = (left + right) / 2;
    int leftMax = findMax(arr, left, mid);         // 왼쪽 부분 최대값
    int rightMax = findMax(arr, mid + 1, right);   // 오른쪽 부분 최대값

    return max(leftMax, rightMax); // 결합
}

---

📌 대표적인 분할정복 알고리즘

⚡ 이진 탐색 (Binary Search)

• 정렬된 배열에서 특정 값을 찾을 때 사용
• 배열을 절반씩 잘라가며 원하는 값을 찾음
• 시간복잡도 : $ O(\log n) $

int binarySearch(vector<int>& arr, int left, int right, int target) {
    if (left > right) return -1; // 못 찾은 경우
    int mid = (left + right) / 2;

    if (arr[mid] == target) return mid;
    else if (arr[mid] < target)
        return binarySearch(arr, mid + 1, right, target);
    else
        return binarySearch(arr, left, mid - 1, target);
}

⚡ 병합 정렬 (Merge Sort)

• 배열을 계속 반으로 나누고, 정렬된 배열을 합치는 과정
• 시간복잡도 : $ O(n \log n) $

void merge(vector<int>& arr, int left, int mid, int right) {
    // 임시 배열을 이용해 두 부분을 병합
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right)
        temp[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int l = 0; l < temp.size(); ++l)
        arr[left + l] = temp[l];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;

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

---

📖 분할정복의 조건

• 문제가 자기유사적(self-similar) 구조를 가질 때
  • 전체 문제와 부분 문제가 본질적으로 같은 구조를 가짐
  • ex. 정렬, 탐색, 행렬 곱셈 등
• 부분 문제들이 독립적일 때
  • 각 부분 문제의 해가 서로 영향을 주지 않음 ➡️ 병렬화에도 유리
• 분할, 정복, 결합 각각의 시간 복잡도가 중요
  • 분할/결합 단계가 너무 오래 걸리면 전체 효율이 떨어질 수 있음

 ⚡분할정복의 시간 복잡도

• 분할정복 알고리즘은 일반적으로 $ T(n) = a \times T(n / b) + O(n^d) $의 점화식으로 표현 가능
  • n: 입력 크기 | a: 부분 문제의 개수 | n/b: 각 부분의 문제 크기 | O(n^d): 분할과 결합에 드는 시간

---

⚠️ 분할정복의 잘못된 이해

• 재귀를 사용하면 분할정복인가요?
  • 당연히 아니다. 반드시 문제 분할과 부분 문제의 결과를 결합하는 과정이 있어야 한다. 재귀는 단순히 구현할 때 사용하는 방식일 뿐이다.
• 부분 문제가 겹치는 경우에도 분할정복을 쓸 수 있나요?
  • 부분 문제가 겹치는 경우에는 중복 계산이 많아지기 때문에 분할정복을 사용할 수 없다. 이런 경우엔 동적 계획법(Dynamic Programming, DP)이 더 효율적이다.
• 결합 단계가 없는 경우도 있나요?
  • 결합 단계가 없을 수도 있다. 이진 탐색과 같이 결합 없이 결과만 반환하는 경우도 있다.

---

📖 2차원 분할정복

• 1차원(ex. 배열, 수열 등)에서는 반으로 나누는 것이 자연스럽지만 2차원에서는 그렇지 않다.
• 2차원(ex. 행렬, 바둑판, 종이 등)에서는 "부분 정사각형" 혹은 "사각형 영역"으로 쪼개는 것이 핵심이다.

➡️ 2차원 공간에서 큰 문제를 더 작은 2차원 영역들로 분할하고, 각 영역을 독립적으로 해결한 뒤, 결과를 결합하여 전체 문제를 푸는 알고리즘 설계 기법

⚡ 2차원 분할정복의 단계

📌 분할 (Divide)

• 현재의 2차원 영역을 더 작은 하위 영역(보통 4분할)로 나눔
  • 사격형을 네 개(좌상, 우상, 좌하, 우하)로 쪼개기
  • 특정 규칙에 맞춰 다수의 하위 영역으로 분리

📌 정복 (Conquer)

• 쪼개진 각 하위 영역에 대해 동일한 문제 해결 과정을 재귀적으로 수행
• 각 영역이 충분히 작아지면(보통 1x1 크기 등) 직접 답을 계산

📌 결합 (Combine)

• 각 하위 영역에서 얻은 부분 결과들을 모아서 상위 영역(혹은 전체 영역)의 해답으로 합침
• 결합 방법은 문제마다 다름 (단순 합산, 최대/최소, 병합, 압축 등 다양)

---

⚡ 2차원 분할정복의 구조적 코드 패턴

• "영역"의 정의(정사각형, 직사각형, 특정 범위 등)는 문제 사오항에 따라 달라질 수 있음

void solve(int x, int y, int len) {
    // x, y: 영역의 좌상단 좌표
    // len: 영역의 한 변 길이 (정사각형일 때)
    if (len == 1) {
        // 기저 조건(base case): 1×1 영역은 직접 해결
        ...
        return;
    }

    // 문제의 성질에 따라, 현 영역이 "더 쪼갤 필요 없는" 상태라면 바로 처리(선택적)
    if (기저 조건이 더 있음) {
        ...
        return;
    }

    int half = len / 2;
    // 4개의 영역으로 재귀 호출 (예시: 정사각형)
    solve(x, y, half);                // 좌상
    solve(x, y + half, half);         // 우상
    solve(x + half, y, half);         // 좌하
    solve(x + half, y + half, half);  // 우하

    // 필요시, 네 영역의 결과를 결합 (문제마다 다름)
    ...
}

---

⚡ 2차원 분할정복이 사용되는 대표적 유형

• 쿼드트리(Quad Tree) 압축
  • 2차원 이미지를 여러 번 4분할하며, 각 영역이 모두 동일한 색이면 압축, 아니면 계속 쪼개는 방식
  • 컴퓨터 그래픽스, 지도 데이터, 영상 압축 등에서 활용
• 2차원 구간 질의 (2D RMQ, 2D 세그먼트 트리)
  • 2차원 배열(행렬)에서 특정 사각 영역의 합, 최소/최대 등을 빠르게 구하는 구조
  • 영역을 4분할하면서 각 영역 정보를 트리에 저장
• 2차원 탐색 (ex. 바둑판에서 특정 패턴 찾기 등)
  • 일부분만을 골라서(분할) 각 영역별로 패턴이 있는지 재귀적으로 탐색
• 2차원 병합 정렬 (행렬 병합, 매트릭스의 특정 값 찾기 등)
  • 2차원 배열을 행렬 단위로 나누어 정렬 및 병합