반드시 문제를 풀기 전에 완탐 시간복잡도를 계산해볼 것
N의 max | 빅오 |
---|---|
500 (5백) | O(N³) |
2,000 (2천) | O(N²) |
100,000 (10만) | O(NlogN) |
10,000,000 (천만) | O(N) |
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print('time:', end_time - start_time) # 수행 시간 출력
# 메모이제이션을 하기 위한 리스트 초기화
d = [0] * 100
def fibo(x):
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 100:
return d[x]
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
fibo(99)
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
# 반복문을 이용하여 보텀업 다이나믹 프로그래밍
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])