스택 - DP(Dynamic Programming)

1. DP(Dynamic Programming)

• 동적 계획 (Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘입니다.
• 동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘입니다. 

---

2. 피보나치 수 DP 적용

• 피보나치 수는 부분 문제의 답으로부터본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있습니다.
• 1) 문제를 부분 문제로 분할합다.
  • Fibonacci(n) 함수는 Fibonacci(n-1)과 Fibonacci(n-2)의 합
  • Fibonacci(n-1)은 Fibonacci(n-2)와 Fibonacci(n-3)의 합
  • Fibonacci(2)는 Fibonacci(1)과 Fibonacci(0)의 합
  • Fibonacci(n)은 Fibonacci(n-1), Fibonacci(n-2),..., Fibonacci(2), Fibonacci(1), Fibonacci(0)의 부분집합으로 나뉩니다.
• 2) 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구합니다.
• 3) 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구합니다.

---

# 피보나치 수 DP 적용 알고리즘
def fibo2(n):
    f = [0] * (n+1)
    f[0] = 0
    f[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
        
    return f[n]

---

3. DP의 구현 방식

• recursive 방식 : fib1()
• iterative 방식 : fib2()
• memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한  것이 성능 면에서 보다 효율적입니다.
• 재귀적 구조는 내부에 시스템호출 스택을 사용하는 오버헤드가 발생하기 때문입니다.