[알고리즘] 분할 정복 (Divide & Conquer)

분할 정복 (Divide & Conquer)

 

: 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고,

각 부분 문제의 답으로부터 전체 문제의 답을 계산해 냄

 

* 일반적인 재귀 호출과 다른 점은 문제를 거의 같은 크기의 부분 문제로 나눈다는 것!

 

 

1. 문제를 더 작은 문제로 분할하는 과정 (divide)

2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge)

3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

 

 

 

* 1부터 n까지의 합을 구하는 분할 정복 알고리즘: 1 + 2 + ... + n

 

fastSum() = 1 + 2 + ... + n

        = (1 + 2 + ... + n/2) + ((n/2 + 1) + ... + n)

 

(n/2 + 1) + ... + n)

= (n/2 + 1) + (n/2 + 2) + ... + (n/2 + n/2))

= (n/2) * (n/2) + (1 + 2 + ... + n/2)

= (n/2) * (n/2) + fastSum(n/2)

 

fastSum(n) = 2*fastSum(n/2) + (n^2/4) (n이 짝수일 때)

 

int fastsum(int n) {
	if (n==1) return 1;
	if (n%2 == 1) return fastSum(n-1) + n;
	return 2*fastsum(n/2) + (n/2)*(n/2);
}

 

 

 

* 행렬의 거듭제곱을 구하는 분할 정복 알고리즘

class SquareMatrix;
SquareMatrix identity(int n); // 크기가 n*n인 항등행렬을 반환하는 함수

// A^m을 반환
SquareMatrix pow(const SquareMatrix& A, int m) {
	if (m==0) return identity(A.size());
	if (m%2 > 0) return pow(A, m-1) * A;
	// A^m = (A^(m/2)) * (A^(m/2))
	SquareMatrix half = pow(A, m/2);
    
	return half*half;