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

in Algorithm

분할정복 알고리즘에 대한 설명입니다.

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

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

  • 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 있음.

설계 방법

1) Divide

∙  원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다.

2) Conquer

∙  각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다.

3) Combine

∙  Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.

🖋 Divide를 제대로 나누면 Conquer과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요!

🖋 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다.

특징 및 장단점

∙  분할된 작은 문제는 원래 문제와 성격이 동일하다  -> 입력 크기만 작아짐

∙  분할된 문제는 서로 독립적이다(중복 제거 X) -> 순환적 분할  및 결과 결합 가능

∙  분할정복은 Top-down방식으로 재귀 호출의 장단점과 똑같다고 보면 된다.

장점단점
∙  Top-down 재귀방식으로 구현하기 때문에 코드가 직관적이다.∙  재귀함수 호출로 오버헤드가 발생할 수 있다
∙  문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결할 수 있다.∙  스택에 다량의 데이터가 보관되는 경우 오버플로우가 발생할 수 있다.