1. 문제

출처: 백준 24416번 알고리즘 수업 - 피보나치 수 1

2. 풀이

동적 계획법(Dynamic Programming)은 반복되는 값을 잘 저장해두었다가 사용하는 memoization이 핵심이다. 다른 분들의 설명에서도 볼 수 있었지만, 동적 계획법이라는 말은 잘 안 어울리는 듯하다.

이번 문제는 이전에 재귀적 방법으로 피보나치 수를 구했던 것과 DP를 통해서 구할 때 어떤 차이가 있는지 확인하는 것이다.

DP를 통해서 구할 때에는, 피보나치 수를 작은 것부터 list에 쭉 저장하는 형식으로 구현하면 된다.

3. 소스코드

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)

4. 그 외

드디어 동적 계획법(Dynamic Programming) 단계에 들어왔다.

이전에 재귀 방법으로 풀었던 피보나치 문제도 링크로 걸어둔다.

백준 10870번 피보나치 수 5