[자료구조] 분할 정복(divide and conquer)알고리즘

분할 정복 알고리즘

 

한 번에 해결할 수 없는 큰 문제를 작은 문제들로 분할하여 작은 문제들 부터 문제를 해결하는 방법이다.

분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현한다.

 

 

분할 정복 동작과정

 

• Divide

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

 

• Conquer

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

 

• Combine

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

 

 

장점

• Top-dwon 재귀방식으로 구현하기 때문에 코드가 직관적이다.
• 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결할 수 있다.

 

단점

 

• 분할 정복 알고리즘은 최소한 두 개의 하위 문제를 생성하기 때문에 재귀 호출을 여러 번 실행한다.
• 재귀 호출을 사용한 함수는 함수 호출 오버헤드 때문에 실행 속도가 느려진다.
• 스택에 다량의 데이터가 보관되는 경우 오버플로우가 발생할 수 있다.

 

분할 정복 알고리즘은 중복이 제거되지 않다는 점에서  동적계획법과 대비된다.