https://namu.wiki/w/분할 정복 알고리즘

개요

분할 정복은 엄청나게 크고 방대한 문제를 부분문제로 나눌수 없을때까지 나눠가며, 그것들의 결과를 하나로 합치는 개념이다.

어원은 로마 제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분할통치(Devide and Rule)에서 나왔다.

1. 분할 (Divide) : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 하위 문제로 나눈다.
2. 정복 (Qonquer) : 가장 작은 단위의 하위 문제를 재귀적으 해결하여 정복한다.
3. 조합 (Combine) : 결과들을 통합하여 원래 문제의 답을 얻는다.

예시 :

• 병합 정렬