분할 정복(Divide and Conquer)

큰 문제를 작은 하위 문제로 나누고(Divide), 이 하위 문제를 재귀적으로 해결(Conquer) 한 후, 그 결과를 합쳐서(Combine) 원래 문제의 해답을 얻는 알고리즘 설계 기법입니다.

제곱 분할법(Exponentiation by Squaring)

거듭제곱을 계산할 때 $b^{n}$은 $(b^{(n/2)})^{2}$이 될 수 있음을 이용하여 작은 문제로 나누고, 이 하위 문제를 재귀적으로 해결한 후, 그 결과를 합쳐서 $b^{n}$의 해답을 얻을 수 있습니다.

$2^{10}$을 구해봅시다.

#include <iostream>

using namespace std;

int pow(int base, int exp) {
	if (exp == 0) return 1;

	int half = pow(base, exp / 2);

	return exp % 2 == 0 ? half * half : base * half * half;
}

int main() {
	cout << pow(2, 10);

	return 0;
}

결과

pow(2, 10) = pow(2, 5) * pow(2, 5) --> $2^{10}$ = $(2^{5})^{2}$

pow(2, 5) = 2 * pow(2, 2) * pow(2, 2) --> $2^{5}$ = $2 * (2^{2})^{2}$

pow(2, 2) = pow(2, 1) * pow(2, 1); --> $2^{2}$ = $(2^{1})^{2}$

pow(2, 1) = 2 * pow(2, 0) * pow(2, 0) --> $2^{1}$ = $2* (2^{0})^{2}$

pow(2, 0) = 1
pow(2, 1) = 2 * 1 * 1 = 2
pow(2, 2) = 2 * 2 = 4
pow(2, 5) = 2 * 4 * 4 = 32
pow(2, 10) = 32 * 32 = 1024

피보나치 행렬(Fibonacci matrix)

$F_{i + 1} = F_{i} + F_{i - 1}$
$F_{i} = F_{i} + 0$

이 식을 행렬로 바꿔보면,
$F_{0} = 0$
$F_{1} = 1$

즉,

제곱 분할법과 피보나치 행렬을 이용한 피보나치 수열

#include <iostream>

using namespace std;

const int M[2][2] = { {1, 1}, {1, 0} };

void multiply(int X[2][2], const int Y[2][2]) {
    int a = X[0][0] * Y[0][0] + X[0][1] * Y[1][0];
    int b = X[0][0] * Y[0][1] + X[0][1] * Y[1][1];
    int c = X[1][0] * Y[0][0] + X[1][1] * Y[1][0];
    int d = X[1][0] * Y[0][1] + X[1][1] * Y[1][1];

    X[0][0] = a;
    X[0][1] = b;
    X[1][0] = c;
    X[1][1] = d;
}

void pow(int F[2][2], int n) {
    if (n <= 1) return;

    pow(F, n / 2); 
    multiply(F, F);

    if (n % 2 != 0) multiply(F, M);
}

int fibo(int n) {
	if (n <= 1) return n;

	int F[2][2] = { {1, 1}, {1, 0} };

    pow(F, n - 1);

	return F[0][0];
}

int main() {
	cout << fibo(10);

	return 0;
}

결과