[Algorithm] 분할 정복 알고리즘 (Divide and Conquer)

분할 정복

크고 방대한 문제를 작은 문제 단위로 나눈 다음 그것을 다시 합쳐서 해결하는 알고리즘이다. 

이 알고리즘은 3가지 단계를 가진다.

1. Divide : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
2. Conquer : 작은 단위의 문제를 해결한다.
3. Combine : 해결한 문제의 결과를 통합하여 답을 얻는다.

대표적인 예로 quick sort나 병합정렬이 있다.

 

 

병합 정렬

https://miraekwak.tistory.com/73?category=922962 

[Algorithm] 정렬 알고리즘 & Python3 코드 & 시간복잡도 정리