이번에 살펴볼 개념은 분할정복에 관한 내용입니다.
분할 정복
분할 정복이란, 해결할 문제를 여러 개의 작은 부분으로 나누고(divde), 나눈 작은 문제를 해결(Conquer)하여, 필요하다면 그 해를 통합(Combine)하는 형식의 문제 풀이를 말합니다.
예: 거듭제곱 알고리즘
2의 n제곱을 계산하려 할 때 (분할정복 X)
- 2 자신을 n번 곱해야 하므로 O(n)의 시간이 걸린다.
2의 n제곱을 분할정복을 사용해 계산할 때
- 예를 들어 2의 8제곱은 2의 제곱을 3번 곱하면 되므로 연산의 횟수가 8번에서 3번으로 줄어든다.
- \[C^n = C^{(n/2)}*C^{(n/2)} (n이 짝수일 때)\]
- \[C^n = C^{(n-1)/2}*C^{(n-1)/2}*C (n이 홀수일 때)\]
예: 퀵 정렬과 병합 정렬
(0)