📝 분할 정복이란?
여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하는 방식이다.
🎯 분할 정복 특징
- 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄여가는 방식이다.
- 분할된 문제는 서로 독립적이다.
- 분할된 하위 문제는 상위 문제와 성격이 동일하다.
- 적용 예시) 정렬문제 / 큰 숫자 곱하기 / 이진 탐색 등
분할 정복 과정
- 분할 : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
- 정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다.
- 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
📈 분할 정복의 장점
- 문제를 더 작고 쉬운 문제로 분할하여 해결하므로 해결 과정이 간단해지고 대규모 문제를 해결하기 용이하다.
- 부분 문제들이 독립적이기 때문에 병렬적으로 문제를 해결한다.
📉 분할 정복의 단점
- 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한
오버헤드가 발생한다.
✔ 오버헤드란 프로그램의 실행 흐름에서 나타나는 현상으로 예를 들어, 프로그램의 실행 흐름 도중에 동떨어진 위치의 코드를 실행시켜야 할 때 , 추가적으로 시간, 메모리, 자원이 사용되는 현상이다. - 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 된다.
❗ 분할 정복과 동적 프로그래밍의 차이
- 동적 프로그래밍(Dynamic Programming)과 분할 정복(Divide and Conquer)은 서로 비슷한 알고리즘 기법이지만 ‘목적’과 '적용 대상’이 다르다.
- 분할정복의 경우는 큰 문제를 작은 문제들로 나누어서 해결해 나아가면서 큰 수의 곱셈, 퀵 정렬 등과 같은 문제를 해결한다.
- 동적 프로그래밍의 경우, 작은 문제들을 풀면서 그 결과를 저장해 나가고 전체 문제를 해결해 나가면서 최적화 문제나 최단 경로 문제 등의 문제를 해결한다.
참고자료
도라에몽 암기빵