파이썬과 익숙해질 겸, 비지니스 로직 속에 빠져있는 나에게 기본을 잊지말자란 채찍질을 할 겸 뭔가를 시작해보았다

보통 피보나치는 재귀로 구현하는데, n 이 조금만 커져도 시간이 어마어마하게 증가한다 f(n-2) + f(n-1)의 반복이니 기존 값을 저장해뒀다가 쓰면 되어 배열로 처리한다는 걸 생각해 볼 수 있을 것이다

먼저 코드를 보자

배열

fibonacci.py

def fibonacci(num):
    fibos = [0, 1]

    # 2 <= i < num + 1 까지 돌린다
    for i in range(2, num + 1):
        fibos.append(fibos[i-2] + fibos[i-1])

    # 마지막 데이터가 구하려는 데이터가 된다
    return fibos[num]

테스트해보면 재귀보다 엄청나게 빨라진 속도를 피부로 느낄 수 있다 뭐 여기까진 다들 생각해봤고 구현할 수 있을 것 같다

배열에 append하는 것 보다 미리 크기가 num만큼 정의된 배열에 i로 접근해 넣으면 더 빠른 속도가 날 것 같았다

하지만... python 엔 배열을 정해진 크기만큼 초기화할 방법이 없더라 [0] * num이라는 방법 뿐

배열을 안 쓰는 방법이 있을까? 한참을 고민하다가 다른 솔루션을 찾아봤다

재할당

멋진 방법이 있었다

fibonacci.py

def fibonacci(num):
    a = 0
    b = 1

    # 0 <= i < num
    for i in range(num):
        temp = a
        a = b
        b += temp
    return a

a 엔 b 값을 주고, b 에는 기존의 a 값을 계속 더해준다 이 짓을 num - 1만큼 반복한다

배열을 안 쓰니 절반정도의 시간이 더 줄어들었다

공식

이마저도 조금 아쉬움이 있었다, 피보나치는 수열이고 수열은 공식이 있기 마련이다 위키피디아엔 이미 그 공식이 있었다 수학의 힘을 빌려보자

fibonacci.py

from decimal import Decimal
# fibonacci의 85번 째부터 Double 값을 넘어가기에 Decimal 기능을 써야한다
sqrt5 = Decimal(5).sqrt()

def fibonacci(n):
    return ((1 + sqrt5) ** n - (1 - sqrt5) ** n) / (2 ** n * sqrt5)

20 만번 째도 0.2 초만에 구해진다

여담

• 피보나치의 데이터를 도식화하면 힙 모양이 되는데 아주 큰 값을 구하는 거라면 피보 힙이 제일 빠르지 않을까?
• 수학의 정석 심화편이 생각나는 건 왜일까?