분할 정복(Divide and Conquer)
전체 문제를 부분 문제로 분할(Divide)한 뒤, 부분 문제를 풀고(Conquer), 이를 전체로 병합(Merge)하는 과정을 거쳐 문제를 해결하는 방식
분할 정복과 동적 계획법의 구분(조건)
- 공통점
- 큰 문제를 부분 문제로 나누어 작은 문제를 푼다.
- 최적 부분 구조를 가져야 사용 가능하다.
- 차이점
- 동적 계획법
- 최적 부분 구조, 겹치는 부분 문제 특성을 지닐 때 효과적이다.
- 부분(기저) 문제는 중복되어, 상위 문제 해결 시 재활용된다.
- Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용)
- 분할 정복
- 부분 문제는 서로 중복되지 않음
- Memoization 기법 사용 안함.
- 겹치는 부분 문제 특성이 존재할 때에도 사용하지만, 중복 계산을 피하는 것에는 집중하지 않는다. 따라서 이 경우에는 DP가 더 적합하다.
- 동적 계획법
적용 방식
분할 정복 방식은 재귀 함수를 통해 연산의 단위를 조금씩 줄어가는 방식이다.
프로세스는 대체로 다음과 같다.
1
2
3
4
5
6
7
function F(x):
if 'F(x)가 간단한 형태' then:
return F(x)를 계산한 값
else:
x 를 x1, x2로 분할
F(x1)과 F(x2)를 호출
return F(x1), F(x2)로 F(x)를 구한 값
사용 예시
병합 정렬, 퀵소트 등의 정렬(사진은 병합 정렬의 예시)
[38, 27, 43, 3, 9, 82, 10]인 입력값은[38, 27, 43, 3]과[9, 82, 10]로 두 부분으로 분할, 다시[38, 27],[43, 3],[9, 82],[10]로 네 부분으로 분할 등의 방식으로 각각 더 이상 쪼갤 수 없을 때까지 계속해서 분할(divide)한 후, 분할이 끝나면 병합(merge)하면서 정렬(conquer)해 나간다.분할 정복을 활용한 수(행렬)의 거듭제곱
일상적으로 사용하는 n번의 거듭제곱은 자신을 n번 곱하므로 보통 $O(n)$의 시간이 소요된다.
예를 들어, A라는 수의 8제곱을 계산하기 위해서는 A를 8번 곱해야 한다.
만약 분할 정복을 이용한다면, 다음과 같이 3번만에 계산하여 시간복잡도를 줄일 수 있다.
$A^{8}=(A^{4})^{2}=((A^{2})^{2})^{2}$
즉 시간 복잡도가 $O(\log n)$이 된다.
\[C^n=\begin{cases}C^{\frac{n}{2}}C^\frac{n}{2} & (n이 \,\,짝수)\\ C^{\frac{n-1}{2}}C^\frac{n-1}{2}C & (n이 \,\,홀수)\end{cases}\]이 아이디어를 활용해서 다음과 같은 재귀 함수를 구현할 수 있다.
1 2 3 4 5 6 7 8 9
def power(C, n): if n == 1 : return C else : x = power(C,n//2) if n % 2 == 0: return x*x else : return x*x*C
반복문으로 구현한 함수는 다음과 같다.
1 2 3 4 5 6 7 8
def power(C, n): result = 1 while n: if n % 2 != 0: result *= C C *= C n //= 2 return result
행렬의 경우 x*x를 행렬곱을 하는 부분으로 대체해주면 된다.
추후에 포스팅할 예정이다.
카라추바 알고리즘(빠른 곱셈)
보통의 곱셈 알고리즘의 시간 복잡도가 $O(n^2)$인 데에 반해 카라추바 알고리즘의 시간 복잡도는 $O(n^{1.585})$라고 한다.
원리와 구현 설명은 아직 이해하지 못해서 참고자료로 남긴다.
추후에 정리할 예정이다.