백준 - 행렬 제곱 (C++)

 

---

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

10830번: 행렬 제곱

 

 이번 문제는 행렬의 길어, 제곱할 횟수, N x N 행렬이 주어졌을 때, 제곱의 결과를 출력하는 문제이다. 이 문제를 풀기 위해서는 행렬을 서로 곱하는 방법과 거듭제곱을 분할 정복하는 방법을 알아야 한다. 분할 정복을 알아야 하는 이유는 시간 때문인데, 만약 일일이 행렬을 곱한다면 행렬 곱셈만 최대 100,000,000,000번 해야 한다. 그렇기에 시간을 줄이기 위해서 분할 정복을 이용할 것이다.

 

 우선은 행렬의 곱셈이다. 행렬 곱셈을 하는 방법은 구글링을 하면 자세히 나오니 생략한다. 그리고 행렬 곱셈 개념을 코드로 작성해야 한다.

vector<vector<int>> Multiple(vector<vector<int>> matrix1, vector<vector<int>> matrix2)
{
    vector<vector<int>> result(N, vector<int>(N, 0));
    
    for (int a = 0; a < N; ++a)
    {
        for (int b = 0; b < N; ++b)
        {
            int sum = 0;

            for (int c = 0; c < N; ++c)
                sum += (matrix1[a][c] * matrix2[c][b]);
            
            result[a][b] = sum % MOD;
        }
    }

    return result;
}

허접한 그림이긴 하지만, 대략 이런 식으로 곱이 진행될 것이다. 두 행렬의 곱에서 왼쪽 행렬의 행열은 a, c이고 오른쪽 행렬의 행열은 c, b이다. 그리고 곱의 결과는 (a, b)에 저장될 것이다. 

 

 다음은 제곱을 분할정복하는 방법이다. 이를 위해 제곱의 지수를 이용해야 한다. 지수는 짝수, 홀수 2가지 경우로 나눌 수 있다. 만약 지수가 짝수일 경우를 생각해보자. N^2k = N^k * N^k로 나눌 수 있다. 그리고 지수가 홀수일 경우에는 N^(2k + 1) = N^k * N^k * N^1로 나눌 수 있다. 이를 지수가 10인 경우와 11인 경우에 적용한다면 이렇게 나타낼 수 있다.

지수가 10, 11일 경우

그리고 이를 매끄럽게 코드로 표현하기 위해서 지수가 1인 경우는 따로 처리할 것이다. 이 부분의 코드는 다음과 같다.

 

vector<vector<int>> Square(vector<vector<int>> matrix, long long exponent)
{
    if (exponent == 1)
        return matrix;
   
    vector<vector<int>> half = Square(matrix, exponent / 2);
	
    
    if (exponent % 2 == 0)	// 짝수일 경우
        return Multiple(half, half); // 밑^(지수 / 2) x 밑^(지수 / 2)
    else	// 홀수일 경우
        return Multiple(Multiple(half, half), matrix); // 밑^(지수 / 2) x 밑^(지수 / 2) x 밑^1
}

Square 함수는 위의 제곱을 분할하면서 재귀적으로 처리할 함수이다. 인자인 matrix는 제곱의 밑(행렬)이고 exponent는 지수이다. exponent의 값이 1일 경우는 그냥 밑(matrix)을 반환한다. 그리고 exponent가 짝수냐 홀수냐에 따라 exponent를 2로 나눈 것을 곱할지, 더불어 원래 밑을 한 번 더 곱할지 결정한 후 반환한다.

 

 이것들을 고려한 전체 코드는 다음과 같다.

#include <iostream>
#include <vector>
#pragma warning(disable:4996)
#define LEN 6
#define MOD 1000
using namespace std;

int N;
long long B;

vector<vector<int>> Multiple(vector<vector<int>> matrix1, vector<vector<int>> matrix2)
{
    vector<vector<int>> result(N, vector<int>(N, 0));
    
    for (int a = 0; a < N; ++a)
    {
        for (int b = 0; b < N; ++b)
        {
            int sum = 0;

            for (int c = 0; c < N; ++c)
                sum += (matrix1[a][c] * matrix2[c][b]);
            
            result[a][b] = sum % MOD;
        }
    }

    return result;
}

vector<vector<int>> Square(vector<vector<int>> matrix, long long exponent)
{
    if (exponent == 1)
        return matrix;
   
    vector<vector<int>> half = Square(matrix, exponent / 2);

    if (exponent % 2 == 0)
        return Multiple(half, half);
    else
        return Multiple(Multiple(half, half), matrix);
}

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

    cin >> N >> B;

    vector<vector<int>> matrix;

    for (int r = 0; r < N; ++r)
    {
        vector<int> line;
        int num;

        for (int c = 0; c < N; ++c)
        {
            cin >> num;

            line.push_back(num % MOD);
        }

        matrix.push_back(line);
    }

    vector<vector<int>> answer = Square(matrix, B);

    for (int r = 0; r < N; ++r)
    {
        for (int c = 0; c < N; ++c)
            printf("%d ", answer[r][c]);
        printf("\n");
    }

    return 0;
}

---

• 행렬 곱: https://ko.wikipedia.org/wiki/%ED%96%89%EB%A0%AC_%EA%B3%B1%EC%85%88

행렬 곱셈 - 위키백과, 우리 모두의 백과사전

• 행렬 곱 문제: https://www.acmicpc.net/problem/2740

2740번: 행렬 곱셈