알고리즘 - 피보나치

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

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

먼저 코드를 보자

해답

배열

fibonacci.py
1
2
3
4
5
6
7
8
9
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
1
2
3
4
5
6
7
8
9
10
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
1
2
3
4
5
6
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 초만에 구해진다

여담

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