분할정복 - 거듭제곱의 해결 ( Divide and Conquer )

분할 정복

: 큰 문제를 작은 문제로 나누어 각각을 해결하고 다시 병합하는 방식으로 문제를 해결하는 방식.

1. DIvide : 큰 문제를 작은 문제들로 나눈다.

2. Conquer : 작은 문제를 더 나눌 수 있으면 더 작은 문제로 나누고, 나눌 수 없으면 문제를 해결한다.

3. Merge : 작은 문제를 합하면서 큰 문제를 해결한다.

 

 

분할 정복의 조건

1. 큰 문제를 작은 문제로 나누어도 큰 문제와 해결 방식이 같아야함. ( 작은 문제로 나누어도 문제의 해결 방식이 동일해야함 )

2. 쪼개진 문제 간의 연관이 없어야함. 작은 문제가 다른 작은 문제에 영향을 미치면 안됨.

 

 

대표적인 예시로 Merge Sort가 있다. 

 

오늘 내가 이 글에서 주목하고자 하는 것은 분할정복을 통한 거듭제곱의 해결이다.

[ 백준 C++ 1629 곱셈, 12850 본대산책2, 11444 피보나치 수6 ] 

 

 

 

1629 곱셈

 

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

 

A, B, C를 입력받고, $A^B \mod C$를 계산한 값을 출력해야한다.

하지만 B의 범위는 int 최대 범위인데 주어진 시간은 0.5초이므로 B번 연산을 진행하면 시간복잡도가 O(B)로 당연히 시간 초과가 날 것이다. 그러므로 분할정복을 사용하여 수행한다.

1. IF B가 짝수라면,

$$A^{B} = A ^{2\times \frac{B}{2}}$$

2. IF B가 홀수라면,

$$A^{B} = A ^{2\times \frac{B-1}{2}}\times A$$

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll a, b, c, tmp;

// a^b = a^(b/2) x a^(b/2)

ll power(ll b) {
	if (b == 0) return 1;
	if (b == 1) return a % c;

	tmp = power(b / 2) % c;
	tmp = tmp * tmp % c;
	if (b % 2 == 0) return tmp;
	return tmp * a % c;
}

/*
ll power(ll x, ll y)
{
	if (y == 0)return 1;
	return power(x * x % c, y / 2) * (y % 2 ? x : 1) % c;
}
*/

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> a >> b >> c;
	cout << power(b);

}

 

 

다음 두번째 문제이다.

 

12850 본대산책2

https://www.acmicpc.net/problem/12850

12850번: 본대 산책2

행렬의 곱. 인접행렬을 통해 해결할 수 있다. 

$$\begin{bmatrix}
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
\end{bmatrix}= A$$라고 하면 $A^D$를 구하면 된다.

이때 $D$번 연산하면 시간초과가 날 것이므로 분할정복을 이용할 것이다.

vector를 이용해 matrix를 만들었고 연산자 오버로딩을 통해 행렬곱을 구현하였다.

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;

ll D;

matrix A = {
        {0, 1, 1, 0, 0, 0, 0, 0},
        {1, 0, 1, 1, 0, 0, 0, 0},
        {1, 1, 0, 1, 1, 0, 0, 0},
        {0, 1, 1, 0, 1, 1, 0, 0},
        {0, 0, 1, 1, 0, 1, 1, 0},
        {0, 0, 0, 1, 1, 0, 0, 1},
        {0, 0, 0, 0, 1, 0, 0, 1},
        {0, 0, 0, 0, 0, 1, 1, 0}
};

matrix ans = {
        {1, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 1}
};


matrix operator * (matrix & a, matrix & b) {
    matrix c(a.size(), vector<ll>(b[0].size()); // 8 x 8 영행렬

    for (ll i = 0; i < a.size(); i++) { // 행렬곱셈
        for (ll j = 0; j < a.size(); j++) {
            for (ll k = 0; k < a.size(); k++) {
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= MOD;
            }
        }
    }

    return c;
}

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> D;

    while (D > 0) {
        if (D % 2) {
            ans = ans * A;
        }

        A = A * A;
        D = D / 2;
    }

    cout << ans[0][0];

}

 

 

세 번째 문제이다.

 

11444 피보나치 수6

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

이 또한 위 문제와 같은 맥락이다. 오히려 더욱 쉽ㄴ다..!

$$\left[ \begin{matrix} F_n \\ F_{n-1} \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} F_{n-1} \\ F_{n-2} \end{matrix} \right] $$ 

즉 2X2 matrix의 거듭제곱만으로 구할 수 있다.

 

#include <bits/stdc++.h>
#define MOD 1000000007;

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;

ll n;

matrix A = {
    {1, 1},
    {1, 0}
};

matrix ans = {
    {1,0},
    {0,1}
};

matrix operator * (matrix& a, matrix& b) {
    matrix c(2, vector<ll>(2));

    for (ll i = 0; i < 2; i++) { // 행렬곱셈
        for (ll j = 0; j < 2; j++) {
            for (ll k = 0; k <2; k++) {
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= MOD;
            }
        }
    }

    return c;
}

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;

    while (n > 0) {
        if (n % 2) {
            ans = ans * A;
        }

        A = A * A;
        n = n / 2;
    }

    cout << ans[0][1];

}