[종만북] 행렬의 거듭제곱

 

우리가 보통 행렬의 곱셈을 구현하기 위해서는 n x n 행렬이 A, B가 있을 때

주어진 행렬의 모든 원소(n^2 가지)에 대해 A행렬의 가로, B행렬의 세로를 곱해줘야 하기 때문에 O(n^3) 번의 연산이 필요하게 된다.

 

이렇게 되면 n이 조금만 커져도, 또는 거듭제곱의 수가 조금만 커져도 필요한 연산의 수가 매우 크게 증가하기 때문에

연산의 수를 줄이는 알고리즘이 필요하다.

 

우리는 이 문제를 분할 정복(divide & conquer)로 해결할 수 있는데

예를 들어 행렬 A를 m번 거듭 제곱한다 하면, A^(m) = A^(m/2) * A^(m/2)로 나눌 수 있다는 점을 이용한다.

(행렬의 곱셈법칙에 따라서)

 

만약 A^8 를 구하기 위해 곧이곧대로 A를 7번 곱하게 되면 연산은 총 7 * n^3번 해야 하지만 분할 정복을 이용 시

 

A^8 = A^4 * A^4 = (A^2)^4

이처럼 중복되는 행렬이 반복되어 나타나기 때문에 행렬 연산을 계속해서 절반으로 줄일 수 있다.

 

 

예시 문제

백준 10830번 행렬 제곱 : https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

소스 코드

 

#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<int>> matrix;
matrix operator * (const matrix &a, const matrix &b) {
    int n = a.size();
    matrix c(n, vector<int>(n));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
            c[i][j] %= 1000;
        }
    }
    return c;
}
int main() {
    int n;
    long long b;
 
    cin >> n >> b;
 
    matrix ans(n, vector<int>(n));
    matrix a(n, vector<int>(n));
 
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> a[i][j];
        }
        ans[i][i] = 1;
    }
 
    while (b > 0) {
        if (b % 2 == 1) {
            ans = ans * a;
        }
        a = a * a;
        b /= 2;
    }
    
    for (int i=0; i<ans.size(); i++) {
        for (int j=0; j<ans[i].size(); j++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }
 
    return 0;
}