분할정복 개념
분할정복 (divide and conquer) : 여러 알고리즘의 기본이 되는 해결방법으로, 크고 방대한 문제를 조금씩 나눠가면서 풀기 쉬운 문제 단위로 만들어서 해결하고, 이후 다시 합쳐서 해결하는 개념
- 문제 해결 전략 중 하나
- 어떤 문제를 유사한 형태를 가지는 더 작은 크기의 서브 문제들로 나눈 후 이들을 재귀적으로 같은 방식으로 해결한 뒤, 각 서브 문제들을 해결한 결과를 활용하여 원래 문제를 해결하는 방식
- 대표적인 예시 합병정렬, 퀵정렬, 이진탐색
- 분할정복을 이해하기 좋은 예시는 합병정렬이다.
| 개념 | divide and conquer |
|---|---|
| divide (분할) | 문제를 작은 크기의 서브 문제들로 나눔 |
| conquer (정복) | 서브 문제들을 동일하게 재귀적인 방식으로 해결 만약 더 이상 나눌 수 없으면 직접 해결 |
| combine (조합) | 서브 문제들의 솔루션을 합쳐서 원래(original) 문제의 답을 만듬 |