분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer)이란?

큰 문제를 해결하기 어려울 때 작은 하위 문제들로 나누어서 해결하는 문제 해결 전략이다.

이 방식은 하위 문제를 재귀적으로 해결하고, 그 결과를 합쳐서 원래 문제의 해답을 구한다.

 

분할 정복의 세 단계

1. 분할(Divide): 문제를 여러 개의 하위 문제로 나눈다. 이때, 하위 문제들은 원래 문제와 동일하거나 유사한 형태를 가져야 한다.
2. 정복(Conquer): 각 하위 문제를 재귀적으로 해결한다. 이 단계에서 하위 문제들이 충분히 작아지면 직접 해결할 수 있다.
3. 병합(Combine): 하위 문제의 해답을 모아서 원래 문제를 해결한다.

분할 정복의 특징

• 재귀적 접근: 문제를 계속해서 더 작은 문제로 나누고, 각 문제를 재귀적으로 해결한다.
• 효율적 탐색: 분할을 통해 문제의 크기를 줄이기 때문에, 억지기법보다 훨씬 빠르게 최적의 해를 찾을 수 있다.
• 병합 과정: 하위 문제의 해를 결합하여 전체 문제의 해를 구할 수 있어야 한다.

 

예시로 이해하기

1. 병합 정렬 (Merge Sort)

• 분할: 배열을 절반으로 나눈다.
• 정복: 각 절반을 재귀적으로 병합 정렬을 사용해 정렬한다.
• 병합: 두 개의 정렬된 절반을 합쳐서 하나의 정렬된 배열로 만든다.
• 시간 복잡도: 분할을 반복하기 때문에 O(n logn)의 시간 복잡도를 가진다.

2. 이진 탐색 (Binary Search)

• 분할: 정렬된 배열에서 중간 요소와 목표 값을 비교하여 배열을 반으로 나눈다.
• 정복: 목표 값이 중간 값보다 크면 오른쪽 절반, 작으면 왼쪽 절반을 탐색한다.
• 병합: 이진 탐색에서는 병합 단계가 필요하지 않다. 분할을 통해 최종 해답을 찾는다.
• 시간 복잡도: 배열을 계속 절반으로 나누기 때문에 O(logn)의 시간 복잡도를 가진다.

 

분할 정복의 장점과 단점

• 장점:
  
  • 많은 문제에서 시간 복잡도를 크게 줄일 수 있습니다.
• 단점:
  • 모든 문제에 적용할 수 있는 것은 아니다. 문제를 하위 문제로 나누고 다시 결합할 수 있는 경우에만 보통 사용한다.
  • 재귀 호출이 많아지면 스택 오버플로우가 발생할 수 있다.

예시로 막대 자르기 문제가 있다.

 

 

 

public class RodCutting {

    public static int cutRod_DC(int[] p, int i) {
        // 기저 사례: 길이가 0인 막대일 때, 판매 금액은 0이다.
        if (i == 0) {
            return 0;
        }

        int maxSell = 0;

        // 길이 j만큼 잘라서 판매하는 경우를 모두 계산하여 최대 판매 금액을 찾는다.
        for (int j = 1; j <= i; j++) {
            // p[j-1]은 길이 j에 대한 가격이므로, p 배열 인덱스를 맞추기 위해 j-1로 접근
            maxSell = Math.max(maxSell, p[j - 1] + cutRod_DC(p, i - j));
        }

        return maxSell;
    }

    public static void main(String[] args) {
        int[] prices = {2,5,9,10}; // 각 길이의 막대에 대한 가격
        int n = 4; // 막대의 전체 길이

        int maxSellValue = cutRod_DC(prices, n);
        System.out.println("최대 판매 금액: " + maxSellValue);
    }
}

 

분할 정복으로 위에 막대문제를 풀면 다음과 같다.

 

시간복잡도는 다음과 같이 점화식을 풀어가며 구할 수 있다.

 T(n): cutRod_DC(p, n)을 호출시 cutRod_DC가 호출되는 총 횟수

    T(n)=1+(T(n-1)+T(n-2)+⋯+T(1)+T(0)),    n≥1

    T(0)=1

    T(n)=1+(T(n-1)+T(n-2)+⋯+T(1)+T(0))  - (식 1)

    T(n-1)=1+(T(n-2)+T(n-3)+⋯+T(1)+T(0))  - (식 2)

    식 1에서 식 2를 빼면  T(n) – T(n-1) = T(n-1) 

    T(n)=2T(n-1)

          =2(2T(n-2))=2^2 T(n-2)

          =2^2 (2T(n-3))=2^3 T(n-3)

     ⋮

          =2^n T(0)

          =2^n 

 

 O( 2^n)이라는 시간 복잡도가 나온다.  지수 시간의 시간 복잡도를 가진다면 매우 안좋은 상황인 것이다.

 

따라서 중복을 제거하며 쌓아가는 동적계획 알고르즘 (Dynamic Programming) 이 나오게 되었다. 이건 그 다음에 정리하고자 한다.