출처: 백준 24416번 알고리즘 수업 - 피보나치 수 1
동적 계획법(Dynamic Programming)
은 반복되는 값을 잘 저장해두었다가 사용하는 memoization
이 핵심이다. 다른 분들의 설명에서도 볼 수 있었지만, 동적 계획법이라는 말은 잘 안 어울리는 듯하다.
이번 문제는 이전에 재귀적 방법으로 피보나치 수를 구했던 것과 DP를 통해서 구할 때 어떤 차이가 있는지 확인하는 것이다.
DP를 통해서 구할 때에는, 피보나치 수를 작은 것부터 list에 쭉 저장하는 형식으로 구현하면 된다.
num = int(input())
#DFS
count_dfs = 0
def dfs(n):
global count_dfs
if n==1 or n==2:
count_dfs += 1
return 1
else:
return dfs(n-1)+dfs(n-2)
#DP
count_dp = 0
memo = [0,1,1]+[0]*(num-2)
def dp(n):
global count_dp
if n == 1 or n == 2:
return memo[n]
else:
for i in range(3,n+1):
count_dp += 1
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
dfs(num)
dp(num)
print(count_dfs, count_dp)
드디어 동적 계획법(Dynamic Programming) 단계에 들어왔다.
이전에 재귀 방법으로 풀었던 피보나치 문제도 링크로 걸어둔다.