Divide and Conquer

큰 문제를 쪼개서 푼 다음, 이를 다시 합쳐가며 최종 답을 구하는 방법

크게 세 가지 파트로 나눌 수 있다.

1) Divide: 말 그대로, 문제를 더 작은 sub-problems로 나눈다.
2) Conquer: recursive 하게 DAC를 호출한다. sub-problems이 충분히 작아지면 직접 해결한다.
3) Combine: sub-problems의 결과들을 조합하여, 최종 답을 도출한다.

일반적인 pseudocode는 다음과 같다.

/* DAC: Divide and Conquer function
 * le: left end
 * re: right end
 * */
DAC( a, le, re )
{
	if ( baseCase )
    	return solution;
    else {
    	mid = divide( le, re )
        DAC( a, le, mid )
        DAC( a, mid+1, re )
        combine
    }
    return solution
}

이를 기반으로 문제에 맞게 변형하면 된다.

장점

하나로 보면 복잡하고 어려운 문제를, 문제를 나눔으로써 쉽고 빠르게 풀 수 있다.

단점

recursive call로 인한 다양한 이슈가 존재한다.
DAC 함수를 효율적으로 설계할 필요가 있다.

ex)

• 문제가 충분히 쪼개졌을 때, 더 간단한 다른 알고리즘으로 계산
• 문제를 쪼개는 기준을 잘 선택해, 불균형한 케이스 최소화

EXAMPLES

다음은, 쉽게 접할 수 있는 DAC 기반 알고리즘이다.
1. Quick Sort
2. Merge Sort
..