-
[자료구조] 분할 정복(divide and conquer)알고리즘Algorithm/자료구조 2024. 5. 10. 18:31
분할 정복 알고리즘
한 번에 해결할 수 없는 큰 문제를 작은 문제들로 분할하여 작은 문제들 부터 문제를 해결하는 방법이다.
분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현한다.
분할 정복 동작과정
- Divide
원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눈다.
- Conquer
각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위라면 탈출 조건을 설정하고 해결한다.
- Combine
Conpuer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.
장점
- Top-dwon 재귀방식으로 구현하기 때문에 코드가 직관적이다.
- 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결할 수 있다.
단점
- 분할 정복 알고리즘은 최소한 두 개의 하위 문제를 생성하기 때문에 재귀 호출을 여러 번 실행한다.
- 재귀 호출을 사용한 함수는 함수 호출 오버헤드 때문에 실행 속도가 느려진다.
- 스택에 다량의 데이터가 보관되는 경우 오버플로우가 발생할 수 있다.
분할 정복 알고리즘은 중복이 제거되지 않다는 점에서 동적계획법과 대비된다.
'Algorithm > 자료구조' 카테고리의 다른 글
[자료구조] 완전 탐색 : 브루트 포스 알고리즘 (0) 2024.05.14 [자료구조] 메모이제이션(Memoization) (0) 2024.05.09 [자료구조] 동적계획법(dynamic programming, DP) (0) 2024.05.09