** Dynamic Programming

Dynamic Programming

동적계획법은 재귀 함수의 단점을 보완할 수 있는 방법이다.
재귀 함수는 결과를 구할때 구했던 값을 또 구하기 위해 같은 과정을 반복한다.
예를들어 피보나치 함수를 생각해보자.
fibo(1) = 1
fibo(2) = 1
이다.
fibo(3) = fibo(1) + fibo(2) 이다.
fibo(4) = fibo(3) + fibo(2) 이다.
이는 즉, fibo(1) + fibo(2) + fibo(2) 이다.
하지만 위에서 fibo(3)은 2라고 구했는데, fibo(4)를 구할때 한 번 더 구하고 있다.
이런 과정이 만약 fibo(100)까지 간다면...? 매우 비효율적이다.
그래서 fibo(3)은 2 라고 기록을 해두는것이다.
그럼 fibo(4)는 2 + 1이라고 한 연산에 값을 구할 수 있다.

• 각 연산값을 저장해둘 수 있는 딕셔너리를 하나 준비해야 한다.

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
  1: 1,
  2: 1
}

def fibo_dynamic_programming(n, fibo_memo):
  if n in fibo_memo:
    return fibo_memo[n]
    
  nth_fibo = fibo_dynamic_programming(n-1, fibo_memo) + fibo_dynamic_programming(n-2, fibo_memo)
  fibo_memo[n] = nth_fibo
  return nth_fibo

print(fibo_dynamic_programming(input, memo))

• 참고 자료