분할 정복 Divide and Conquer

분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임

• 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음,
• 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 냄

큰 문제를 작은 문제로 나누어서 해결하는 방법

• 전체 집합을 찾으려는 원소와 비교하여 부분 집합으로 나누어 찾음

• 이 알고리즘은 다시 나누어진 부분 집합에서 같은 방법을 수행함

• 대표적인 분할 정복 알고리즘으로는 병합 정렬
  • 병합 정렬 과정을 표현한 밑의 그림은 분할 정복의 원리를 잘 보여준다.
• 분할: 문제를 동일한 유형의 여러 하위 문제로 나눔
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합

즉, 분할 정복은 말 그대로 문제를 ‘분할’ 해서 ‘정복’ 한 다음 정답을 ‘조합’해 나간다는 의미

• 분할 정복은 재귀를 활용하는 대표적인 알고리즘