행렬 멱법을 이용한 피보나치 값 구하기

행렬 멱법이 무엇인지 모르신다면 여기로

이번 포스팅에서는 행렬 멱법을 이용해 $n$ 번째 피보나치 값을 구하는 방법에 대해 말해보고자 합니다.

피보나치 숫자

피보나치 숫자들은 다들 아시다시피 다음과 같은 정수 나열이죠.

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dotsc $$

수식으로 적자면 $F_n$ 는 $n$ 번째 피보나치 숫자라고 정의하겠습니다. 그렇다면,

$$F_n = F_{n-1} + F_{n-2}$$

이 되고, 초기값은

$$F_0 = 0, F_1 = 1$$

으로 정합니다.

숫자 $n$ 이 정해지면 $n$번째 피보나치 숫자를 출력합니다.

    입력값  : n = 2
    출력값 : 1

    입력값  : n = 9
    출력값 : 34

어떤 방법들이 있을까요?

총 4개의 방법이 있습니다.

첫번째로는 단순 접근 방법은 위 수식을 활용한 재귀 함수를 작성하는 것입니다. 지수 형태의 시간복잡도가 걸립니다.

두번째로는 동적 계획법을 이용하는 방법이 있습니다. 이 방법은 $O(n)$의 시간복잡도가 필요합니다.

여기서는 세번째와 네번째 방법에 집중하려 합니다.

세번째 방법은 행렬 {{1,1},{1,0}} 의 멱수를 이용하는 것입니다. 다시 말해서 행렬 멱법을 사용하는 것입니다. $F_n$ 이 $n$ 번째 피보나치 숫자라고 한다면,

$$ {\begin {bmatrix} 1 & 1 \cr 1 & 0 \end {bmatrix}}^{n} = \begin {bmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \end {bmatrix}$$

가 성립합니다. 다음은 위 수식을 이용한 코드 입니다.

    #include <stdio.h>

    void multiply(int F[2][2], int M[2][2]);

    void power(int F[2][2], int n);

    /* n 번째 피보나치 숫자를 반환하는 함수 */
    int fib(int n)
    {
      int F[2][2] = {{1,1},{1,0}};
      if (n == 0)
        return 0;
      power(F, n-1);
      return F[0][0];

    }

    /* 행렬의 멱수를 취하는 함수, 최적화 시킴 */
    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);

    }

    /* 행렬의 곱을 계산하는 함수, 결과값은 다시 F 에 저장됩니다. */
    void multiply(int F[2][2], int M[2][2])
    {
      int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
      int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
      int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];

    int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

      F[0][0] = x;
      F[0][1] = y;
      F[1][0] = z;
      F[1][1] = w;

    }

    /* 테스트를 위한 드라이버 프로그램 */
    int main()
    {
      int n = 9;
      printf("%d", fib(9));
      getchar();
      return 0;
    }

위의 행렬의 멱수를 구하는 함수는 n 이 짝수냐 홀수냐에 따라서 행렬 멱수의 계산방법이 조금 다릅니다. 단순히 행렬 F 를 n승 하는것보다 훨씬 최적화된 방법입니다. 왜냐하면 시간복잡도가 크게 줄어들기 때문입니다. $O(n)$ 에서 $O(log(n))$ 으로요.

네번째 방법은 세번째 방법의 응용이지만 더 유용하게 쓰일 수 있습니다. 일단 이 수식으로 부터 시작하겠습니다.

$$ {\begin{bmatrix} 1 & 1 \cr 1 & 0 \end{bmatrix}}^{n} = \begin {bmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \end{bmatrix}$$

양쪽에 있는 행렬의 determinant(행렬식)을 구합니다. 그러면, $$ (-1)^n = F_{n+1}F_{n-1} - F_{n}^{2}$$ 가 됩니다.

사각 행렬 $A$ 가 존재한다면, $A^nA^m = A^{n+m}$ 으로 계산될 수 있기에,

$$ {\begin{bmatrix} 1 & 1 \cr 1 & 0 \end{bmatrix}}^n \times {\begin{bmatrix} 1 & 1 \cr 1 & 0 \end{bmatrix}}^m = \begin{bmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \end{bmatrix} \times \begin{bmatrix} F_{m+1} & F_{m} \cr F_{m} & F_{m-1} \end{bmatrix} $$

왼쪽의 {{1,1},{1,0}} 행렬은 다음과 같이 합쳐집니다.

$$ {\begin{bmatrix} 1 & 1 \cr 1 & 0 \end{bmatrix}}^{n+m} = \begin{bmatrix} F_{n+m+1} & F_{n+m} \cr F_{n+m} & F_{n+m-1} \end{bmatrix} = \begin{bmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \end{bmatrix} \times \begin{bmatrix} F_{m+1} & F_{m} \cr F_{m} & F_{m-1} \end{bmatrix} $$

위의 수식은 다음과 같이 분기될 수 있습니다.

이제, $F_{n+m-1}$ 를 활용해 보도록 하겠습니다.

$$ F_mF_n +F_{m-1}F_{n-1} = F_{m+n-1} \cdots (1)$$

여기서 $n = n+1$ 를 하면,

$$ F_mF_{n+1} +F_{m-1}F_{n} = F_{m+n} \cdots (2)$$

이 됩니다.
다시 $(1), (2) $ 에 $m = n$ 를 해보겠습니다.

$$ F_{2n-1} = F_{n}^{2} + F_{n-1}^{2}$$

$$ F_{2n} = (F_{n-1} + F_{n+1})F_{n} = (2F_{n-1} + F_{n})F_{n} \qquad \because F_{n+1} = F_{n} + F_{n-1}$$

이 됩니다.

이제는 따로 행렬을 계산할 필요 없이, 위의 수식만을 가지고, $n$ 이 짝수이냐 홀수이냐에 따라서 피보나치 $n$ 값을 정할 수 있게되었습니다.
예를 들어 $n$ 이 $5$ 이면, $ k = 2n-1$ 자리에다가 $n = 3 = (5 +1) /2 $ 를 넣어주면 $k = 5$ 가 나옵니다.
같은 방법으로 $n$ 이 $4$ 이면, $ k = 2n$ 자리에다가 $n = 2= 4 /2 $ 를 넣어주면 $k = 4$ 가 나옵니다.
그러므로 아래와 같은 방법을 따라 적절한 $k$ 를 찾고 위의 수식에 대입만 하면 될거 같습니다.

$n$ 이 짝수면, $k = n/2$
$n$ 이 홀수면, $k = (n+1)/2$

# n 번째 피보나치 숫자를 찾기 위한 python 3 프로그램
# O (Log n) 의 시간 복잡도를 가지고 있음.
MAX = 1000
 
# memoization 을 위한 배열 생성
f = [0] * MAX
 
# f 배열을 이용해 n 번째 피보나치 숫자를 반환하는 함수
def fib(n) :
    # Base cases
    if (n == 0) :
        return 0
    if (n == 1 or n == 2) :
        f[n] = 1
        return (f[n])
 
    # 이미 fib(n) 이 계산 되있다면 그 값을 반환
    if (f[n]) :
        return f[n]
 
    if( n & 1) :
        k = (n + 1) // 2
    else : 
        k = n // 2
 
    # 위에서 논의한 수식을 적용합니다 .
    # 참고로 n & 1 의 값이 1일땐 n 이 짝수란 의미
    # n 이 0 이면 n 은 홀수
    if((n & 1) ) :
        f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
    else :
        f[n] = (2*fib(k-1) + fib(k))*fib(k)
 
    return f[n]
 
 
# 드라이버 코드
n = 9
print(fib(n))
 
# 이 코드는 Nikita Tiwari 에 의해 작성되었습니다.

이 수식을 이용한 피보나치 값을 구하는 솔루션의 시간복잡도는 $O(log(n))$ 입니다.
행렬 멱법을 이용한 솔루션과 시간이 같네요. 하지만 중요한 점은 프로그래밍 문제를 풀때는 네번째 방법이 굉장히 유용하게 작용됩니다. 왜냐하면 행렬 멱법은 power(F, n) 함수를 이용하는데, 이는 재귀적 성질을 가지고 있어서 n 이 큰값이 나오게 된다면 (약 $10^{18}$ 정도?), 무자비하게 자기 자신의 함수를 불러내고 또 불러낼것입니다. 이렇게 되면 메모리상에 스택이 꽉 차게 되서 stack overflow error 를 불러 일으키거나 아니면 재귀를 거치는 과정에서 마저 시간이 소요되기 때문에 시간 초과 에러 (TLE) 가 나타날 수 있습니다. 네번째 방식 역시 재귀적 방식을 사용했지만, tabulation 을 이용하기 때문에 함수 호출양을 절반으로 줄였으니 시간적, 공간적으로 큰 절약을 가져옵니다.

---

사실 이것은 DP 문제를 풀기위해서 공부하다보니 이 정보까지 포스팅.. 이럴수가