파이썬 피보나치 알고리즘 구현 방법 (6가지)

python 피보나치 수열

파이썬 피보나치 알고리즘 구현

피보나치 코드

 

 

피보나치수열 (fibonacci numbers)

 

첫째 항과 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

 

$ 1, 1, 2, 3, 5, 8, 13, 21 ... $

 

 

다음과 같은 점화식으로 표현할 수 있으며

(수학에서 엄밀하게 정의할 때, 0번째 항을 0으로 둠)

 

$ F_0 = 0, F_1 = 1, $

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

 

 

아래와 같은 점화식으로도 표현할 수 있음

 

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

 

---

 

 

파이썬 코드를 통한 피보나치 구현

 

 

$ 1, 1, 2, 3, 5, 8, 13, 21 ... $ 에서

6번째 항인 $8$을 출력해보자

 

---

 

 

첫 번째 방법, for 반복문

 

while 반복문

def fibo_while (n) :
    result = []
    a, b = 1, 1
    while a < n:
        a, b = b, a + b
        result.append(a)  
    return a

fibo_while(6)
8

for 반복문

def fibo_for(n):
    result = []
    a, b = 1, 1
    for i in range(n):
        result.append(a)
        a, b = b, a + b
    return result[-1]

fibo_for(6)
8

 

---

 

 

두 번째 방법, 재귀함수

 

가장 느린 방법, 재귀함수를 배운다는 것에 중점을 둘 것

def fibo_recur(n):
    result = []
    if n <= 2:
        number = 1
    else:
       number = fibo_recur(n-1) + fibo_recur(n-2)
    return number

fibo_recur(6)
8

 

---

 

 

세 번째 방법, 메모이제이션(Memoization)

 

memory = {1: 1, 2: 1}

def fibo_memoization(n):
    if n in memory:
        number = memory[n]
    else:
       number = fibo_memoization(n-1) + fibo_memoization(n-2)
       memory[n] = number
    return number

fibo_memoization(6)
8

 

---

 

 

네 번째 방법, 제너레이터(Generator)

 

두 번째로 빠른 방법

def fibo_generator(n):
    a, b = 1, 1
    for i in range(n):
        yield a
        a, b = b, a + b
    return a

for x in fibo_generator(6):
    print(x, end=' ')
1 1 2 3 5 8

 

---

 

 

다섯 번째 방법, 고유값(Eigenvalue solution)

 

1475번째 항부터는 오류 발생

$ n > 1474 $

import numpy as np

def eigen_fib(n):
    F1 = np.array([[1, 1], [1, 0]])
    eigenvalues, eigenvectors = np.linalg.eig(F1)
    Fn = eigenvectors @ np.diag(eigenvalues ** n) @ eigenvectors.T
    return int(np.rint(Fn[0, 1]))
eigen_fib(6)
8

 

---

 

 

여섯 번째 방법, 행렬 지수(Matrix Exponentiation)

 

가장 빠른 방법이지만, 행렬 지수에 대한 이해가 필요

def multiply(a, b, x, y):
    return x*(a+b) + a*y, a*x + b*y

def square(a, b):
    a2 = a * a
    b2 = b * b
    ab = a * b
    return a2 + (ab << 1), a2 + b2

def power(a, b, m):
    if m == 0:
        return (0, 1)
    elif m == 1:
        return (a, b)
    else:
        x, y = a, b
        n = 2
        while n <= m:
            # repeated square until n = 2^q > m
            x, y = square(x, y)
            n = n*2
        # add on the remainder
        a, b = power(a, b, m-n//2)
        return multiply(x, y, a, b)

def implicit_fib(n):
    a, b = power(1, 0, n)
    return a

implicit_fib(6)
8

 

---

행렬 지수 방법과 제네레이터 방법의 소요 시간 비교

 

100만번째 행의 수를 계산하는데 소요되는 시간을 비교해봄

import time

start_t = time.time()

implicit_fib(1000000)
end_t = time.time()
print('total time = ', end_t - start_t)
total time =  0.15467619895935059


start_t = time.time()
for i in fibo_generator(1000000):
    pass

end_t = time.time()
print('total time = ', end_t - start_t)
total time =  10.629846811294556

 

행렬 지수 방법 : 0.1초

제네레이터 방법 : 10초

 

 

행렬 지수 방법이 월등히 빠르다!!

참고로 100만번째 행의 수는 어마어마하게 크다.

 

 

결론 : 초고속의, 최고 효율의 알고리즘으로 다다르기 위해서는 결국 수학을 알아야한다.

 

---

 

 

Reference

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

피보나치 수 - 위키백과, 우리 모두의 백과사전

2. https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4

피보나치 수열 - 나무위키

3. https://www.youtube.com/watch?v=NjKqcQ_eIpA

4. http://www.oranlooney.com/post/fibonacci/

A Fairly Fast Fibonacci Function - OranLooney.com