728x90
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 $F_n=F_{n-1}+F_{n-2}$가 된다.
재귀 함수를 이용
n = int(input())
def fib(n):
if n <= 1:
return n
else:
return (fib(n-1) + fib(n-2))
print(fib(n))반복문을 이용
n = int(input())
f1 = 0
f2 = 1
for _ in range(n):
f1, f2 = f2, f1+f2
print(f1)피보나치 수를 구하기 위해서는 처음의 두 항 0과 1이 필요하기 때문에 반복문을 이용하는 경우 0과 1을 변수로 선언 해 주어야만 한다.
메모이제이션을 이용
from functools import lru_cache
n = int(input())
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
else:
return (fib(n - 1) + fib(n - 2))
print(fib(n))메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. — 위키피디아 —
메모이제이션은 이전의 계산 결과들을 저장해 놓는다. 나중에 더 큰 값을 계산해야 할 때 저장해 놓은 값을 불러오고 그 이후부터 계산하기 때문에 다양한 이점을 갖는다. 큰 피보나치 수를 재귀함수로 계산 하는 것은 현실적으로 불가능 한데, 메모이제이션을 사용하면 빠르게 결과를 얻을 수 있다.
파이썬에서 메모이제이션은 from functools import lru_cache 과 @lru_cache 데코레이터를 이용하면 된다.
백준에서 세 방법 모두 사용이 가능하다.
반복문이 제일 빠르다.
728x90
