알고리즘 - 피보나치
파이썬과 익숙해질 겸, 비지니스 로직 속에 빠져있는 나에게 기본을 잊지말자란 채찍질을 할 겸 뭔가를 시작해보았다
보통 피보나치는 재귀로 구현하는데, n 이 조금만 커져도 시간이 어마어마하게 증가한다
f(n-2) + f(n-1)
의 반복이니 기존 값을 저장해뒀다가 쓰면 되어 배열로 처리한다는 걸 생각해 볼 수 있을 것이다
먼저 코드를 보자
해답
배열
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
이라는 방법 뿐
배열을 안 쓰는 방법이 있을까? 한참을 고민하다가 다른 솔루션을 찾아봤다
재할당
멋진 방법이 있었다
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
만큼 반복한다
배열을 안 쓰니 절반정도의 시간이 더 줄어들었다
공식
이마저도 조금 아쉬움이 있었다, 피보나치는 수열이고 수열은 공식이 있기 마련이다 위키피디아엔 이미 그 공식이 있었다 수학의 힘을 빌려보자
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 초만에 구해진다
여담
- 피보나치의 데이터를 도식화하면 힙 모양이 되는데 아주 큰 값을 구하는 거라면 피보 힙이 제일 빠르지 않을까?
- 수학의 정석 심화편이 생각나는 건 왜일까?