[알고리즘 패러다임 - 4] 분할 정복

분할 정복

문제를 더 이상 나눌 수 없을 때까지 나누고 (분할), 나누어진 부분 문제를 품으로써 (정복) 전체 문제의 답을 얻는 방식의 알고리즘 패러다임. 이진 탐색, 퀵 정렬 등이 대표적인 알고리즘이다.

 

[동작 방식]

1. 분할 : 문제를 더 이상 나눌 수 없을 때까지 2개 이상의 부분 문제로 나눈다. 나눠진 문제들은 서로 독립적이다.
2. 정복 : 부분 문제를 푼다.
3. 결합 : 정복된 답을 취합한다.