알고리즘 - 피보나치
· 약 4분
파이썬과 익숙해질 겸, 비지니스 로직 속에 빠져있는 나에게 기본을 잊지말자란 채찍질을 할 겸 뭔가를 시작해보았다
보통 피보나치는 재귀로 구현하는데, 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]