분할정복 알고리즘

🟩 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후, 이들의 해를 결합하여 원래 문제의 해를 구하는 방식

 

🟩 분할된 작은 문제는 원래 문제와 동일하다.

입력의 크기만 작아진다.

 

🟩 분할된 문제는 서로 독립적이다.

순환적인 분할 및 결과 결합이 가능하다.

 

🚀 활용1 정렬 : 합병정렬, 퀵정렬

🚀 활용2 탐색 : 이진탐색