백준 알고리즘 파이썬(Python) 2747번 피보나치 수

---

만약 이를 재귀 함수로만 문제를 풀게 된다면 아래 그림과 같이 재귀 함수가 n을 인자로 호출되면 그 함수는

n-1과 n-2를 인자로 함수를 호출하고, 호출된 각 함수가 계속해서 함수를 두 개씩 호출하게 되므로 

만약 n이 100이라면 이 구조의 기반한 문제풀이라면 컴퓨터가 1초에 1억 번의 계산을 수행한다 해도 수백억 년이 걸린다.

이러한 문제를 다이나믹 프로그래밍(DP)을 이용하여 간단하게 해결할 수 있다.

 

다이나믹 프로그래밍이란 간단히 말해서 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

 

 

n = int(input())
d = [0] * (n+1) #단순히 재귀적으로 풀 때 과도한 시간이 걸리는 것을 방지하기 위해 dp로 풀어준다.

if n == 1:
    d[1] = 1
    print(d[1])
elif n == 2:
    d[2] = 1
    print(d[2])
else:
    d[1] = 1 #인덱스 에러를 해결하기 위해 이렇게 써주어야 한다.
    d[2] = 1
    for i in range(3,n+1):
        d[i] = d[i-1] + d[i-2] # 재귀함수를 이용해 풀이
    print(d[n])

위와 같은 문제풀이 방식을 보텀업 방식 즉 상향식 방법이라고 한다. 이는 다이나믹 프로그래밍의 전형적인 방법이다.

보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블' 이라고 부른다. (위 코드에서는 d가 DP 테이블)