1. 분할정복 (Divide and Conquer)

하나의 문제를 작은 여러개의 문제로 쪼갠 후, 재귀적으로 부분 문제들에 대한 솔루션을 이용해 기존 문제를 해결하는 알고리즘

보통 다항식 시간 내에 해결할 수 있는 P 문제를 다루기 때문에, 대부분 전 주에 다룬 Brute-force 알고리즘을 이미 효율적으로 활용할 수 있습니다.

분할정복은 P 문제 중에서도 입력 크기가 커질 때 속도를 높이기 위해 사용됩니다. 즉, 기존 다항식보다 더 낮은 차수의 다항식 시간으로 풀기 위한 전략이라고 할 수 있습니다.

분할 정복의 해결 과정은 아래와 같습니다.

1. Devide: 문제를 각 부분 문제로 나눈다. 문제가 충분히 작아질 때까지 divide 단계를 반복해야한다.
2. Conquer: 각 부분 문제를 정복하여 각각의 솔루션을 도출한다.
3. Combine: 부분 문제들의 솔루션을 합쳐서 기존 문제를 해결한다.

2. 조건 및 장단점

분할된 문제는 두가지 조건을 만족해야 합니다.
1. 기존 문제와 성격이 동일하며 단순히 입력 크기만 작아진 것이다.
2. 서로 독립적이다. (이상적 조건이며 필수 조건은 아님)

장점

• 큰 문제를 나누어 해결하기 때문에 간단하고 빠릅니다.
• 각 부분 문제들이 독립적이면, 동시에 병렬적으로 문제를 해결할 수 있습니다.

단점

• 재귀 함수를 이용하는 경우, 인풋이 너무 크면 깊은 재귀로 인해 Stack Overflow가 발생할 수 있습니다. (반복(loop) 구조로 바꿔 해결 가능)

3. 예제

1부터 n까지의 합을 구하시오

start와 end를 받는 함수를 활용하여 start부터 end까지의 합을 리턴합니다.

• Base case: start == end일 때 그 값을 그대로 반환

• Divide: mid = (start + end) / 2로 중앙값을 기준으로 문제를 둘로 나눔

• Conquer + Combine: 왼쪽 절반과 오른쪽 절반의 합을 각각 구한 후 더함

public class Main {
    public static void main(String[] args) {
        System.out.println(consecutiveSum(1, 10));
        System.out.println(consecutiveSum(1, 100));
        System.out.println(consecutiveSum(1, 253));
        System.out.println(consecutiveSum(1, 388));
    }

    public static int consecutiveSum(int start, int end) {
        if (start == end) {
            return start; // Base case
        }

        int mid = (start + end) / 2;

        // Divide and Conquer
        return consecutiveSum(start, mid) + consecutiveSum(mid + 1, end);
    }
}

사진 출처: Divide and Conquer Approach to Quality Assurance