분할 정복

여러 알고리즘의 기본이 되는 해결방법

크고 방대한 문제를 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음, 그것들을 다시 합쳐서 해결하자는 개념

원리

큰 문제를 작은 문제로 분할하여 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결
이때 분할된 작은 문제는 원래 문제와 같은 형태이며, 작은 문제는 원래 문제의 일부분이 됨
작은 문제를 재귀적으로 해결하고, 이를 결합하여 원래 문제를 해결

- Divide
분할이 가능한 문제라면, 2개 이상의 문제로 나눈다.

- Conquer
나누어진 문제들이 여전히 분할이 가능하면, 다시 Divide를 수행한다.
그렇지 않으면 문제를 푼다.

- Combine
Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

종류 : 이진 탐색 , 병합 정렬 , 퀵 정렬

사진 클릭시 출처 이동
출처