분할 정복(Divide and Conquer) 알고리즘

분할 정복은 문제를 더 작은 하위 문제로 분할(Divide)하고, 각각을 독립적으로 정복(Conquer)한 뒤 다시 결합(Combine)하여 원래 문제의 해답을 구하는 알고리즘 설계 기법이다. 복잡한 문제를 직접 풀기보다는 작고 단순한 문제들의 해를 구해서 합치는 방식으로 동작한다.

대표적인 예시: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이분 탐색(Binary Search), 행렬 곱셈(DAC Matrix Multiplication)

동작 원리

1. Divide (분할)
문제를 더 작은 부분 문제로 쪼갠다.
2. Conquer (정복)
부분 문제를 재귀적으로 해결한다.
3. Combine (결합)
부분 문제의 결과를 합쳐 원래 문제의 해답을 만든다.

예시 1: 이분 탐색(Binary Search)

정렬된 배열에서 특정 값을 찾는 문제를 생각해보자.

• 배열을 반으로 나눈 뒤 중간값과 찾는 값(target)을 비교한다.
• target이 더 작으면 왼쪽 절반, 크면 오른쪽 절반으로 범위를 좁힌다.
• 이 과정을 반복하면 결국 target을 찾거나 없음을 알 수 있다.

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 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;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        System.out.println(binarySearch(arr, 7)); // 출력: 3
    }
}

예시 2: 병합 정렬(Merge Sort)

• 배열을 반으로 나눈다.
• 각각을 재귀적으로 정렬한다.
• 정렬된 두 배열을 병합하여 하나의 정렬된 배열을 만든다.

import java.util.*;

public class MergeSort {
    public static void mergeSort(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);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        List<Integer> temp = new ArrayList<>();
        int i = left, j = mid+1;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) temp.add(arr[i++]);
            else temp.add(arr[j++]);
        }
        while (i <= mid) temp.add(arr[i++]);
        while (j <= right) temp.add(arr[j++]);

        for (int k = left; k <= right; k++) {
            arr[k] = temp.get(k-left);
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr)); // [1, 2, 5, 7, 9]
    }
}

시간 복잡도

• 이분 탐색: O(log N)
• 병합 정렬: O(N log N)
• 퀵 정렬: 평균 O(N log N), 최악 O(N²)
• 일반적 분할 정복 패턴:
  • 하위 문제의 개수 = a
  • 각 하위 문제 크기 = n/b
  • 합치는 비용 = O(n^d) → 마스터 정리(Master Theorem)로 복잡도를 계산

📝 배운점

분할 정복은 “문제를 작게 나누어 해결한다”는 단순한 아이디어지만 정렬/탐색/행렬 연산 등 다양한 알고리즘에 적용된다. 중요한 점은 문제를 적절하게 분할할 수 있는가와 부분 문제의 해답을 어떻게 결합할 것인가이다. 또한 시간 복잡도 계산에는 마스터 정리를 활용하면 패턴을 빠르게 파악할 수 있다.

참고

• Divide and Conquer Algorithms - GeeksforGeeks