Gold_IV 난이도 문제를 C++로 풀이한 내용입니다. 주어진 행렬 A와 정수 B에 대해 A를 B번 곱한 결과를 1000으로 나눈 나머지를 구하는 문제입니다.

백준 10830: 행렬 제곱

Gold_IV 난이도 문제를 C++로 풀이한 내용입니다. 주어진 행렬 A와 정수 B에 대해 A를 B번 곱한 결과를 1000으로 나눈 나머지를 구하는 문제입니다.

문제 소개

문제 번호: 10830
문제명: 행렬 제곱
난이도: Gold_IV
사용 언어: C++
실행 시간: 0 ms
메모리: 2156 KB
문제 요약: 크기가 N x N인 행렬 A와 자연수 B가 주어졌을 때, A를 B번 곱한 행렬을 1000으로 나눈 나머지를 구해야 합니다.

접근 방법

이 문제는 행렬의 거듭제곱을 효율적으로 계산해야 하는 문제입니다. 일반적인 행렬 곱셈을 B번 반복하면 시간 복잡도가 매우 커지므로, 빠른 거듭제곱 알고리즘을 활용해야 합니다.

사용 알고리즘/자료구조

행렬 곱셈: 두 행렬을 곱하는 기본적인 연산입니다.
분할 정복 (Divide and Conquer): 빠른 거듭제곱 알고리즘의 핵심 아이디어입니다.
재귀 함수: 분할 정복을 구현하기 위해 사용됩니다.
std::vector<std::vector<long long>>: 행렬을 표현하기 위한 자료구조로 사용됩니다.

방법 선택 이유

일반적으로 행렬 A를 B번 곱하는 것은 O(N^3 * B)의 시간 복잡도를 가집니다. B가 매우 커질 수 있으므로 이 방법은 비효율적입니다. 반면, 빠른 거듭제곱 알고리즘(Exponentiation by Squaring)은 O(N^3 * logB)의 시간 복잡도를 가지므로 훨씬 효율적입니다. 이 문제는 특히 B가 큰 경우에 해당하므로 빠른 거듭제곱 알고리즘을 선택하는 것이 필수적입니다. 또한, 결과 값이 커질 수 있으므로 각 연산마다 1000으로 나눈 나머지를 취해주어야 합니다.

풀이 과정

입력 처리: 행렬의 크기 N과 거듭제곱 횟수 B를 입력받고, N x N 행렬 A를 입력받습니다.
행렬 곱셈 함수 (mat_mul): 두 N x N 행렬 X와 Y를 곱하여 결과를 반환하는 함수를 구현합니다. 이때, 각 덧셈과 곱셈 연산 후에는 1000으로 나눈 나머지를 취하여 오버플로우를 방지하고 최종 결과 조건을 만족시킵니다.
행렬 거듭제곱 함수 (mat_exp):
- 기저 조건: B가 0이면 단위 행렬(모든 대각선 원소가 1이고 나머지는 0인 행렬)을 반환합니다.
- 재귀 단계:
  - B를 2로 나눈 몫에 대해 mat_exp 함수를 재귀적으로 호출하여 A^(B/2)를 계산합니다.
  - 만약 B가 짝수이면, 계산된 A^(B/2)를 두 번 곱하여 A^B를 얻습니다. (A^(B/2) * A^(B/2))
  - 만약 B가 홀수이면, 계산된 A^(B/2)를 두 번 곱한 후, 원래 행렬 A를 한 번 더 곱하여 A^B를 얻습니다. (A^(B/2) * A^(B/2) * A)
- 각 행렬 곱셈 연산에서는 mat_mul 함수를 사용하여 1000으로 나눈 나머지를 적용합니다.
결과 출력: mat_exp 함수를 호출하여 A^B를 계산한 후, 결과를 N x N 형식으로 출력합니다.

핵심 아이디어

빠른 거듭제곱 (Exponentiation by Squaring): A^B를 A^(B/2) * A^(B/2) 또는 A^(B/2) * A^(B/2) * A 형태로 재귀적으로 분할하여 계산합니다.
모듈러 연산: 모든 중간 계산 결과에 대해 % 1000 연산을 적용하여 결과 범위를 유지합니다.

주의할 점

모듈러 연산 시점: 덧셈과 곱셈 연산이 끝난 직후에 모듈러 연산을 적용해야 합니다.
B=0 경우: B가 0일 때 단위 행렬을 올바르게 반환해야 합니다.
정수 오버플로우: long long 타입을 사용하여 중간 계산 값이 커져도 오버플로우가 발생하지 않도록 해야 합니다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

long long N, B;

// 두 행렬 X와 Y의 곱을 계산하고 1000으로 나눈 나머지를 반환하는 함수
vector<vector<long long>> mat_mul(const vector<vector<long long>>& X,const vector<vector<long long>>& Y){
    vector<vector<long long>> Z(N, vector<long long>(N, 0)); // 결과 행렬 Z 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % 1000; // mod 적용: 덧셈과 곱셈 후 나머지 계산
            }
        }
    }
    return Z;
}

// 행렬 A를 B번 거듭제곱하는 함수 (빠른 거듭제곱 알고리즘)
vector<vector<long long>> mat_exp(vector<vector<long long>> A, long long B){
    if(B == 0){ // 기저 조건: B가 0이면 단위 행렬 반환
        vector<vector<long long>> I(N, vector<long long>(N, 0));
        for (int i = 0; i < N; i++) {
            I[i][i] = 1; // 대각선 원소는 1
        }    
        return I;
    }
    
    vector<vector<long long>> mat(N, vector<long long>(N, 0));
    mat = mat_exp(A, B/2); // A^(B/2)를 재귀적으로 계산
        
    if (B % 2 == 0){ // B가 짝수면
        mat = mat_mul(mat, mat); // A^(B/2) * A^(B/2) = A^B
    }
    else{ // B가 홀수면
        mat = mat_mul(mat, mat); // A^(B/2) * A^(B/2) = A^(B-1)
        mat = mat_mul(mat, A);   // A^(B-1) * A = A^B
    }
    return mat; // A^B 반환
}


int main(){
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(nullptr); // cin과 cout의 tie 해제

    cin >> N >> B; // 행렬 크기 N과 거듭제곱 횟수 B 입력
    
    // 행렬 A 입력
    vector<vector<long long>> A(N, vector<long long>(N));
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> A[i][j];
    
    // 연산부: A를 B번 거듭제곱
    A = mat_exp(A, B);
    
    // 결과 출력
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cout << A[i][j] << " "; // 결과 행렬의 각 원소를 공백으로 구분하여 출력
        }
        cout << "\n"; // 각 행의 끝에 줄바꿈
    }
    return 0;
}

복잡도 분석

시간 복잡도:
- 행렬 곱셈 (mat_mul) 함수는 O(N^3)의 시간 복잡도를 가집니다.
- 행렬 거듭제곱 (mat_exp) 함수는 재귀적으로 B를 2로 나누어 계산하므로, 총 logB번의 행렬 곱셈 연산이 수행됩니다.
- 따라서 전체 시간 복잡도는 O(N^3 * logB)입니다.
공간 복잡도:
- 재귀 호출 스택의 깊이는 O(logB)입니다.
- 행렬을 저장하기 위해 O(N^2)의 공간이 필요합니다.
- 따라서 전체 공간 복잡도는 O(N^2 + logB)입니다. (주로 O(N^2)으로 간주될 수 있습니다.)

배운 점

이 문제를 풀면서 빠른 거듭제곱 알고리즘(Exponentiation by Squaring)을 행렬에 적용하는 방법을 배울 수 있었습니다. 이는 단순히 큰 숫자의 거듭제곱뿐만 아니라, 행렬과 같이 연산이 정의된 구조에서도 지수적인 연산을 효율적으로 처리하는 강력한 기법임을 알게 되었습니다.

또한, 모듈러 연산의 중요성을 다시 한번 느꼈습니다. 중간 계산 결과가 오버플로우되지 않도록 각 연산마다 적절하게 모듈러 연산을 적용하는 것이 핵심임을 배웠습니다.

이 알고리즘은 암호학, 그래프 이론(예: 특정 횟수 이동 후 도달 가능한 경로 수 계산) 등 다양한 분야에서 활용될 수 있습니다. 이 문제를 통해 복잡한 연산을 효율적으로 처리하는 알고리즘 설계 능력을 향상시킬 수 있었습니다.