[Problem Solving Paradigms] Divide and Conquer | 분할 정복

Divide and Conquer

• 탐색공간의 전체 혹은 일부를 살펴 봄으로써 원하는 답을 찾는 방법
• 문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

 

 

설계

 

#Divide

• 주어진 문제를 작은 단위로 쪼갠다.
  •  이때의 작은 단위는 본 문제와 같지만 입력 값이 작은 문제를 뜻한다 

#Conquer

• 1번에서 나눈 작은 당위들을 recursivley 하게 해결한다
  •   분할이 가능하면 다시 devide를 수행한다. 그렇지 않으면 문제 solve

 

#Combine

• conquer한 문제들을 통합하여 단위들의 답을 적절하게 조합 해서 본 문제의 답을 제시한다.

 

경진대회에서 divide and conquer는 대부분 binary search를 이용하는 문제에 국한되어있다. : 탐색, 함수의 해 구하기 등.

 

 

응용

- 병합 정렬  | 거듭제곱