행렬 거듭제곱을 이용해 피보나치 수를 구하는 C++ 프로그램

피보나치 수란 무엇일까요?

피보나치 수(Fibonacci numbers)는 보통 F_n으로 표기하며, 0과 1에서 시작해 각 항이 바로 앞의 두 항의 합이 되는 수열, 즉 피보나치 수열을 이룹니다. 수식으로 나타내면 다음과 같습니다.

F₀ = 0, F₁ = 1
F_n = F_n-1 + F_n-2  (n > 1)

단순 반복문으로 피보나치 수를 구하면 O(n)의 시간이 필요하지만, 행렬 거듭제곱(Matrix Exponentiation) 기법을 활용하면 분할 정복 방식으로 거듭제곱을 빠르게 계산하여 시간 복잡도를 O(log n)까지 줄일 수 있습니다.

핵심 원리

피보나치 수열은 다음과 같이 2×2 행렬의 거듭제곱 형태로 표현할 수 있습니다.

| F(n+1)  F(n)   |       | 1 1 | ^n
| F(n)    F(n-1) |  =    | 1 0 |

따라서 기본 행렬 M = {{1,1},{1,0}}의 (n-1)제곱을 구한 뒤, 결과 행렬의 첫 번째 요소 F[0][0]을 반환하면 n번째 피보나치 수를 얻을 수 있습니다.

알고리즘

시작
   2×2 크기의 배열 두 개를 준비한다
   행렬 곱셈을 수행하는 함수(multiply)를 만든다
   행렬의 거듭제곱을 구하는 함수(power)를 만든다
   피보나치 수를 반환하는 함수(fibonacci_matrix)를 만든다

   multiply(arr1[2][2], arr2[2][2])
      변수 a, b, c, d 넷을 선언하고 다음을 계산한다
      a = arr1[0][0]*arr2[0][0] + arr1[0][1]*arr2[1][0]
      b = arr1[0][0]*arr2[0][1] + arr1[0][1]*arr2[1][1]
      c = arr1[1][0]*arr2[0][0] + arr1[1][1]*arr2[1][0]
      d = arr1[1][0]*arr2[0][1] + arr1[1][1]*arr2[1][1]
      계산 결과를 arr1에 다시 저장한다

   power(arr1[2][2], 정수 n)
      n이 0 또는 1이면 그대로 종료한다
      M = {{1,1},{1,0}}로 초기화한다
      power(arr1, n/2)로 절반씩 재귀 호출한다
      multiply(arr1, arr1)로 스스로를 제곱한다
      n이 홀수이면 multiply(arr1, M)을 한 번 더 수행한다

   fibonacci_matrix(n)
      F = {{1,1},{1,0}}로 초기화한다
      n이 0이면 0을 반환한다
      power(F, n-1)을 호출한다
      F[0][0]을 반환한다
끝

C++ 예제 코드

#include <iostream>
using namespace std;

// 두 2×2 행렬을 곱한 결과를 F에 저장합니다.
void multiply(int F[2][2], int M[2][2]) {
    int a = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int b = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int c = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int d = F[1][0] * M[0][1] + F[1][1] * M[1][1];
    F[0][0] = a;
    F[0][1] = b;
    F[1][0] = c;
    F[1][1] = d;
}

// 분할 정복으로 행렬 F의 n제곱을 구합니다.
void power(int F[2][2], int n) {
    if (n == 0 || n == 1)
        return;
    int M[2][2] = {{1,1},{1,0}};
    power(F, n / 2);
    multiply(F, F);
    if (n % 2 != 0)
        multiply(F, M);
}

int fibonacci_matrix(int n) {
    int F[2][2] = {{1,1},{1,0}};
    if (n == 0)
        return 0;
    power(F, n - 1);
    return F[0][0];
}

int main() {
    int n;
    while (1) {
        cout << "Enter the integer n to find nth fibonacci no. (enter 0 to exit):";
        cin >> n;
        if (n == 0)
            break;
        cout << fibonacci_matrix(n) << endl;
    }
    return 0;
}

실행 결과

Enter the integer n to find nth fibonacci no. (enter 0 to exit): 2
1
Enter the integer n to find nth fibonacci no. (enter 0 to exit): 6
8
Enter the integer n to find nth fibonacci no. (enter 0 to exit): 7
13
Enter the integer n to find nth fibonacci no. (enter 0 to exit): 0

마무리

이 프로그램은 사용자가 0을 입력할 때까지 반복적으로 정수를 입력받아, 해당 번째의 피보나치 수를 화면에 출력합니다. 행렬 거듭제곱 기법 덕분에 n이 커져도 로그 시간 안에 결과를 얻을 수 있어, 지수 시간이 걸리는 단순 재귀 구현이나 O(n)의 반복문 구현보다 훨씬 효율적입니다. 다만 n이 매우 커질 경우 int 타입의 오버플로우가 발생할 수 있으므로, 필요에 따라 long long 같은 더 넓은 범위의 자료형을 사용하는 것이 좋습니다.