백준 11444: 피보나치 수 6

Gold II 난이도의 이 문제는 C++ 언어를 사용하여 풀이되었습니다. 주어진 큰 수 n에 대한 피보나치 수를 행렬 거듭제곱을 이용해 효율적으로 계산하는 문제입니다.

문제 소개

• 문제 번호: 11444
• 문제명: 피보나치 수 6
• 난이도: Gold II
• 사용 언어: C++
• 실행 시간: 0 ms
• 메모리: 2048 KB
• 문제 요약: n이 주어졌을 때, n번째 피보나치 수를 1,000,000,007로 나눈 나머지를 구해야 합니다. n은 매우 큰 정수일 수 있습니다.

접근 방법

이 문제는 일반적인 반복문이나 재귀 함수로 피보나치 수를 계산하면 시간 초과가 발생할 가능성이 높습니다. n이 매우 큰 경우, 피보나치 수를 계산하는 데 O(n)의 시간 복잡도는 비효율적입니다.

이를 해결하기 위해 행렬 거듭제곱(Matrix Exponentiation) 기법을 사용했습니다. 피보나치 수열은 다음과 같은 행렬 관계로 표현될 수 있습니다.

$$\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]$$

이것을 n번 반복하면 다음과 같은 식을 얻을 수 있습니다.

$$\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n$$

따라서, 기저 행렬 $\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$을 n번 거듭제곱하면, 결과 행렬의 [0][1] 또는 [1][0] 위치에 $F_n$ 값을 얻을 수 있습니다. 행렬 거듭제곱은 분할 정복(Divide and Conquer) 방식을 이용하여 O(log n)의 시간 복잡도로 계산할 수 있습니다. 모든 계산은 모듈러 연산(1,000,000,007)을 적용하여 오버플로우를 방지합니다.

풀이 과정

1. 기저 행렬 정의: 피보나치 수열의 점화식을 나타내는 2x2 행렬 $M=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$을 정의합니다.
2. 행렬 곱셈 함수 구현: 두 개의 2x2 행렬을 입력받아 곱한 결과를 반환하는 함수 mat_mul을 구현합니다. 이때, 각 덧셈 및 곱셈 연산 결과에 대해 모듈러 연산(MOD = 1,000,000,007)을 적용합니다.
3. 행렬 거듭제곱 함수 구현: 분할 정복 방식을 사용하여 행렬 A를 B번 거듭제곱하는 함수 mat_exp를 구현합니다.
   • B가 0이면 단위 행렬을 반환합니다.
   • B가 짝수이면, mat_exp(A, B/2)를 계산하고 그 결과를 두 번 곱합니다.
   • B가 홀수이면, mat_exp(A, B/2)를 계산하고, 그 결과를 두 번 곱한 후 다시 A를 곱합니다.
   • 이 과정에서도 모듈러 연산을 적용합니다.
4. 메인 함수:
   • 입력 n을 받습니다.
   • 기저 행렬 M을 정의합니다.
   • mat_exp(M, n)을 호출하여 $M^n$을 계산합니다.
   • 결과 행렬 R의 R[0][1] (또는 R[1][0]) 값을 출력합니다.

코드 설명

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

//  [F(n+1) F(n)
//   F(n)   F(n−1)] = [1 1
//                     1 0]^n

using ll = long long;
const ll MOD = 1000000007;
const int N = 2; // 2x2 고정

// 두 개의 2x2 행렬 X와 Y를 곱하는 함수
vector<vector<ll>> mat_mul(const vector<vector<ll>>& X,
                           const vector<vector<ll>>& Y){
    vector<vector<ll>> Z(N, vector<ll>(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]) % MOD
                // 각 연산마다 모듈러 연산을 적용하여 오버플로우 방지
                Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % MOD;
            }
        }
    }
    return Z;
}

// 행렬 A를 B번 거듭제곱하는 함수 (분할 정복 이용)
vector<vector<ll>> mat_exp(vector<vector<ll>> A, ll B){
    if(B == 0){
        // B가 0이면 단위 행렬 반환
        vector<vector<ll>> I(N, vector<ll>(N, 0));
        for(int i = 0; i < N; i++) I[i][i] = 1;
        return I;
    }
    
    // A^(B/2) 계산
    auto half = mat_exp(A, B/2);
    // (A^(B/2)) * (A^(B/2)) = A^B (B가 짝수일 때)
    auto res = mat_mul(half, half);
    
    if(B % 2 == 1)
        // B가 홀수이면 A^(B-1) * A = A^B
        res = mat_mul(res, A);
    
    return res;
}

int main(){
    ios::sync_with_stdio(false); // C++ 표준 스트림과 C 표준 스트림 동기화 해제
    cin.tie(nullptr); // cin의 tie를 nullptr로 설정하여 입력 속도 향상

    ll n;
    cin >> n; // n 입력 받기

    // 피보나치 수열을 위한 기저 행렬 M
    vector<vector<ll>> M = {
        {1, 1},
        {1, 0}
    };

    // M^n 계산
    auto R = mat_exp(M, n);

    // F(n)은 결과 행렬 R의 R[0][1] 또는 R[1][0]에 해당
    cout << R[0][1] << '\n';
}

복잡도 분석

• 시간 복잡도: 행렬 거듭제곱은 분할 정복을 사용하므로 O(log n)입니다. 각 단계에서 행렬 곱셈(2x2 행렬)이 수행되는데, 이는 상수 시간 O(N^3) = O(2^3) = O(1)이 걸립니다. 따라서 전체 시간 복잡도는 O(log n)입니다.
• 공간 복잡도: 재귀 호출 스택의 깊이가 O(log n)이고, 각 호출마다 2x2 행렬을 저장하므로 공간 복잡도는 O(log n)입니다.

배운 점

이 문제를 풀면서 행렬 거듭제곱이라는 강력한 알고리즘을 배우게 되었습니다. 피보나치 수열처럼 선형 점화식을 가지는 문제에서, 일반적인 O(n) 방식보다 훨씬 빠르게 (O(log n)) 답을 구할 수 있음을 알게 되었습니다. 특히, n이 매우 큰 경우에 이 기법의 효율성이 두드러집니다.

이러한 행렬 거듭제곱 기법은 피보나치 수열뿐만 아니라, 다양한 선형 점화식을 가지는 다른 문제들에도 응용될 수 있습니다. 핵심은 문제의 점화식을 행렬 형태로 표현하고, 행렬의 거듭제곱을 효율적으로 계산하는 방법을 이해하는 것입니다. 모듈러 연산을 잊지 않고 적용하는 것도 중요합니다.