분할 정복(Divide and Conquer) 이란?
문제를 작은 하위 문제로 나누어 각각을 해결 한 후, 이들을 합쳐 전체 문제의 해결책을 얻는 알고리즘 설계 비법.
- 분할(Divide) : 문제를 더 작은 하위 문제로 나눔
- 정복(Conquer) : 각 하위 문제를 재귀적으로 해결
- 결합(Combine) : 하위 문제의 해를 합쳐 원래 문자의 해를 구함
분할 정복 알고리즘은 특히 정렬, 검색, 곱셈 등의 문제에서 효율적으로 사용
분할 정복의 시간복잡도
- 병합 정렬(Merge Sort)
-분할 : 배열을 절반으로 나눔 시간복잡도는 O(n log n)
-정복 : 각각의 하위 배열을 재귀적으로 정렬
-결합 : 정렬된 두 하위 배열을 하나의 정렬된 배열로 합침 O(n)
따라서 전체 시간 복잡도는 O(n log n)
- 퀵 정렬(Quick Sort)
-분할 : 피벗(pivot)을 선택하여 배열을 피벗을 기준으로 사용한 정렬 알고리즘
-정복 : 각 부분을 재귀적으로 정렬
-결합 : 각 부분이 정렬되어 있으므로 결합 단계는 필요 없음
평균 시간 복잡도는 O(n log n) 이며, 매번 피벗이 최소값이나 최대값을 선택할 경우 최악의 시간 복잡도는 O(n^2)
- 최대 최소 문제 (주어진 배열에서 최대값과 최소값을 찾는 문제)
-분할 : 배열을 두 부분으로 나눔 시간복잡도는 O(log n)
-정복 : 각각의 부분에서 최대값과 최소값을 찾음 O(n)의 시간이 걸림
-결합 : 두 부분의 최대값 중에서 더 큰 값이 전체 최대값이 되고, 최소값 중에서 더 작은 값이 전체 최소값이 됨
따라서 전체 시간 복잡도는 O(n)
분할 정복 알고리즘의 응용
- 이진 검색(Binary Search)
정렬된 배열에서 원하는 값을 찾는 알고리즘. O(log n) 의 시간 복잡도를 가짐 - 스트라센 행렬 곱셈(Strassen`s Matrix Multiplication)
행렬 곱셈을 효율적으로 수행. O(n^2.81) 의 시간복잡도를 가짐 - FFT(Fast Fourier Transform)
신호 처리에서 주파수 분석을 빠르게 수행. O(n lon n) 의 시간 복잡도를 가짐
분할 정복의 장단점
장점
-
문제 해결의 단순화
큰 문제를 작은 하위 문제로 나누기 때문에 문제 해결이 더 단순해짐. 각 하위 문제는 더 쉽게 해결할 수 있으며, 이를 결합하여 원래 문제의 해를 얻을 수 있음 -
병렬 처리 가능
각 하위 문제는 독립적으로 해결되기 때문에 병렬 처리가 가능. 멀티코어 프로세서나 분산 시스템에서 성능 향상을 도모할 수 있음 -
효율적인 시간 복잡도
많은 경우, 분할 정복 알고리즘은 효율적인 시간 복잡도를 가짐. 예를들어, 병합 정렬과 퀵 정렬은 평균적으로 O(n log n)의 시간복잡도를 가짐 -
메모리 활용의 최적화
일부 분할 정복 알고리즘은 메모리 사용을 최적화 할 수 있음. 예를들어, 퀵 정렬은 제자리 정렬(in - place sort) 이므로 추가적인 메모리 공간이 거의 필요 없음
단점
-
재귀호출의 오버헤드
재귀적으로 호출되므로 함수 호출에 따른 오버헤드가 발생. 재귀 깊이가 깊어질 경우, 스택 오버플로우(Stack Overflow) 가 발생할 수 있음 -
병합 단계의 비용
병합 정렬과 같은 알고리즘에서는 병합 단계에서 추가적인 시간과 공간 복잡도가 발생. 이는 특히 대규모 데이터 셋에서 병목 현상이 될 수 있음 -
최악의 경우 시간 복잡도
퀵 정렬의 경우, 피벗 선택이 항상 최악일 경우, (이미 정렬된 배열에서 첫 번째 또는 마지막 원소를 피벗으로 선택할때) O(n^2) 의 시간 복잡도가 발생할 수 있음 -
추가 메모리 사용
일부 분할 정복 알고리즘은 추가적인 메모리를 요구 예를들어, 병합정렬은 O(n)의 추가 메모리를 필요로 함. 이는 메모리 사용량이 중요한 환경에서는 단점이 될 수 있음.
요약
병합정렬 (Merge Sort)
-장점 : 안정적인 O(n log n) 시간복잡도, 병렬 처리에 적합
-단점 : O(n) 추가 메모리 필요, 병합 단계의 비용
퀵 정렬 (Quick Sort)
-장점 : 평균 O(n log n) 시간복잡도, 제자리 정렬(in - place sort)로 메모리 효율적
-단점 : 최악의 경우 O(n^2) 시간복잡도, 재귀 호출에 따른 스택 오버플로우 가능성
