Algorithm | 피보나치 수

# 첫 시도: 재귀를 이용 def fibonacci(n): if n == 0: return 0 if n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) 위 코드의 경우 $n$이 크지 않은 경우 잘 작동하지만, $n$이 30을 넘어가면 시간이 매우 오래 걸린다. 이는 구조상 내부에서 함수를 매우매우매우 많이 반복해야하기 때문이다. # 메모이제이션 def fibonacci(n): numbers = [0, 1] # 처음 두 개의 피보나치 수 for i in range(1, n): numbers.append(numbers[i] + numbers[i-1]) return numbers[n] 위 코드의 경우 피보나치 수를 원소로 하는 리스트를 생성한 후 계속..

2021.01.04