[Algorithm] 분할정복법(Divide and Conquer algorithm)

[분할 정복 알고리즘(Divide and conquer algorithm)]

-  그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법(알고리즘)

-  즉, 한번에 해결하기 어려운 문제를 작은 단위의 문제들로 나누어 해결하는 방법이다.

-  정복(conquer)이 들어가는 이유는 재밌게도 나폴레옹과 관련이 있다.1805년 12월 2일 아우스터리츠 

   전투에서 프랑스의 황제(皇帝) 나폴레옹은 숫자면에서 우세했던 연합군을 물리치기 위해서 나폴레옹은 

   연합군의 중앙으로 쳐들어가 그들의 병력을 둘로 갈라 놓았고, 둘로 나누어진 병력은 개별적으로는 

   나폴레옹의 군대보다 숫자가 적었기 때문에 전투는 나폴레옹의 승리로 끝나게 되었다. 분할정복법은 위와 

   같은 사례를 프로그램에 이용한 것이다.

분할정복법을 구현하기 위한 순서는 다음과 같다.

1. 분할(Divide) : 분할이 가능한 경우, 큰 문제를 하나 이상의 작은 문제로 분할한다.
2. 정복(Conquer) : 분할이 가능하다면 계속 분할한다. 분할이 불가능하다면 나눈 작은 문제를 각각 해결한다.
3. 결합(Combine) : 정복된(해결된) 해답을 모아 큰 문제의 답이 되도록 결합(병합)한다.

분할 정복 알고리즘은 문제를 쪼개는 과정이 가장 핵심적인 기능이며 효율적인 분할을 하는 것이 중요하다.

문제 분할만 잘해도 그것을 해결(정복)한 뒤 병합하는 과정은 간단하기 때문이다. 하지만, 분할정복법의 경우 

대다수가 재귀호출을 통해 구현되기 때문에 그만큼 많은 부담을 갖게 된다.

 

[분할 정복 알고리즘을 이용한 대표적인 알고리즘]

• 퀵 정렬 (Quick Sort)
• 병합 정렬 (Merge Sort)
• 피보나치 수열 (Fibonacci Sequence)
• 거듭 제곱 (Exponentiation)
• 고속 푸리에 변환 (Fast Fourier Transform, FFT)

참고 블로그 

http://debugnote.com/algorithm/2015/07/06/quick-sort/