분할 정복법과 동적 계획법의 차이

공통점

• 문제를 작은 단위로 나누어 해결

차이점

• 분할정복법은 Top-down 방식
• 동적 프로그래밍은 Bottom-up 방식, Memoizition 사용

분할정복 (Divide & Conquer)

접근 방법

분할정복법은 보통 재귀함수를 이용하여 구현하는 것이 일반적이나, 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조를 이용하여 구현하기도 함.

어떠한 큰 문제를 해결하기 위해 큰 문제를 작은 단위의 문제로 나누어 해결하는 방법 하향식 (Top-down) 접근방식 1. 주어진 문제를 둘 이상의 부분 문제로 나눈다. (Divide) 2. 각 문제에 대한 답을 재귀 호출을 이용하여 분할한다. 더 분할되지 않을 정도로 크기가 작다면, 문제에 해답을 구한다.(Conquer) 3. 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. (Merge)

주의사항

일반 재귀호출과 분할정복법의 재귀호출은 조금 다름

• 분할정복법은 각 부분 문제는 거의 같은 크기로 나눈다.

장점

• 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결

단점

• 함수를 재귀적으로 호출함으로 인해 오버헤드가 발생
• 스택에 다양한 데이터를 보관하고 있어야 하므로 스택오버플로우가 발생한다.

구현 예시

int DiveAndConquer(int x)
{
    if (x == 1) return 1;
    if (x == 2) return 1;
    return DiveAndConquer(x - 1) + DiveAndConquer(x + 1);
}

• 대표적인 예 : 병합정렬, 퀵 정렬 등 (문제를 쪼갤 때 부분 문제가 서로 중복되지 않을 때)