피보나치 수열을 구하는 알고리즘 - 행렬 제곱

Fibonacci number 

피보나치 수열이란 0번째 항은 0이고,  첫째, 둘째 항이 1이면 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 

ex) 0, 1, 1, 2, 3, 5, 8 ...

 

점화식으로 표현하면 다음과 같다. 

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

 

 

N번째 수 구하기

1. recursion으로 해결하기 

def fibonacci(int n):
	if(n == 0 or n == 1 ):
    	return n 
    else : 
    	return fibonacci(n-1) + fibonacci(n-2)

 

피보나치는 점화식을 참고하여 위와 같이 재귀호출로 간단하게 해결할 수 있다. recursion의 종료조건으로 n이 0일때는 0 n이 1일때는 1을 호출 할 수 있게 했다. 

 

하지만 해당 알고리즘은 시간 복잡도가 좋지 못하다. 

이렇게 똑같은 값을 계속 불러오게 되어 fibonacci(1)은 무려 5회나 호출되게 된다. 

 

2. 행렬로 바꿔서 해결하기 

위와 같이 피보나치 수열을 무작정 재귀함수로 해결하려고 하면 시간복잡도가 안좋기 때문에 피보나치 수열을 행렬을 이용해서 푸러보려고 한다. 

 

먼저, 이 피보나치 점화식을 행렬로 나타내면 아래와 같다.  

 

{fn+1, Fn}=  {{1,1},{1,0}} {fn, fn-1}이  {{1,1},{1,0}} 을 A로 놓고 식의 관계성을 살펴보면 아래의 식으로 나타낼수 있다. 

{fn+1, Fn}은  A{fn, fn-1}이다. 여기서 알 수 있는 점은 {fn, fn-1}에 A를 곱했더니 1항 더 놓은 {fn+1, Fn}을 구했다는 것이다. 그렇다면  {fn, fn-1}은 또 A{fn-1, fn-2}로 나타낼수 있다. 그럼 {fn-1, fn-2}도 A{fn-2, fn-3}으로 나타낼수 있다. 이렇게 쭉----- 다 해보니 {f1, f0}에 A^n을 곱했더니 {fn+1, Fn}이 나온다고 할 수 있다. 

 

그럼 우린 A^n을 구할 수 있으면 피보나실 수열 행렬식의 일반화를 구할 수 있다. 

 

A^n은 행렬의 대각화로 구할 수 있다. 

 

행렬 A 대각화 하기
행렬계산 방법이 궁금하면 동영상 참고( 동영상 )

1) 고유값, 고유벡터 구하기 

2) 각 고윳값에서 고유벡터 하나씩 서택하기

3) 행렬 P와 D만들기 

 

행렬 A를 대각화 하면 A^n을 구한 식이다. 

우리가 구현해야할 부분은 먼저 두 행렬을 곱하는 기능과 A^n을 계산하는 기능이다.

코드로 구현하면 아래와 같다. 

def mul(A, B):
    ret = [[0, 0], [0, 0]]

    ret[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0]
    ret[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1]
    ret[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0]
    ret[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1]

    ret[0][0] %= 1000
    ret[0][1] %= 1000
    ret[1][0] %= 1000
    ret[1][1] %= 1000

    return ret

def matrix_pow(A, power):
    if power == 1:
        return A

    mid = power // 2
    calc = matrix_pow(A, mid)
    ret = mul(calc, calc)

    if power % 2 == 1:
        return mul(ret, A)
    else:
        return ret

def fib(N):
    if N == 0:
        return 0
    fibo_mat = matrix_pow([[1, 1], [1, 0]], N)
    return fibo_mat[0][1]

# 테스트 케이스 실행
T = int(input())
for _ in range(T):
    N = int(input())
    print(fib(N))

 

 

이렇게 행렬을 사용해 피보나치 수열을 계산하게 되면 시간 복잡도가 O(log2n)이기 때문에 더 효율적이다.