[알고리즘] 분할정복 - Divide and Conquer

분할 정복법이란? 문제의 사례를 2개 이상의 더 작은 사례로 나누어(divide) 각 작은 사례에 대한 해답(conquer)을 쉽게 얻을 수 있으면 이들의 해답을 결합(combine)하여 원문제의 해답을 얻는 방식.

 

- 문제를 나누는 과정은 해답을 쉽게 얻을 때까지 반복적으로 적용한다. 

- 하향식(top-down) 접근 방법이다.

• 분할(Divide) : 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
• 정복(Conquer): 나눈 작은 문제를 각각 해결한다. 
• 통합(Combine): (필요하다면) 해결된 해답을 모은다.

- 보통 재귀 프로시저로 먼저 해결한 다음에 보다 효율적인 반복 프로시저가 없는지 검토한다. 

 

- 대표적인 알고리즘

• 이진 검색(BinarySearch)
• 합병 정렬(MergeSort) 
• 빠른 정렬(QuickSort)
• 최대-최소값 찾기