divide and conquer, 분할정복이라고 하죠~ 개념과 동작 방식을 설명하구요, merge sort를 통해 divide & conquer가 어떻게 동작하는지 살펴봅니다~

https://youtu.be/aj3vw_KDmxc

분할 정복(Divide and Conquer)

- 어떤 문제를 유사한 형태를 가지는 더 작은 크기의 서브 문제들로 나눈 후 이들을 재귀적으로 같은 방식으로 해결한 뒤 각 서브 문제들을 해결한 결과를 활용하여 원래 문제를 해결하는 방식

- 병합 정렬, 퀵 정렬, 이진 탐색 등에 사용된다.

 

- divide : 문제를 작은 크기의 서브 문제들로 나눈다.

- conquer : 서브 문제들을 동일하게 재귀적인 방식으로 해결하고, 만약 더이상 나눌 수 없다면 직접 해결한다.

- combine : 서브 문제들의 솔루션을 합쳐서 원래 문제의 솔루션을 만든다.