[알고리즘]Dynamic Programming

Recursive Algorithm의 문제점👅

• 함수 호출이 너무 많다
• 동일한 parameter를 갖는 함수 호출이 중복되어 비효율적

DP 💡ideation

• 정보를 미리 저장해두고 작은 문제부터 하나하나씩 해결해가면 어떨까?

2를 8번 더하면 16이다. -> 2를 9번 더할 때는 다시 더하지 말고 2를 8번 더한 것에 2를 더하면 돼!

memoization

[https://hyunlee103.tistory.com/73]

• Recursion : top-down으로 task의 맨 위부터 호출
• DP : sub instance인 F(0)부터 그 결과를 memoization에 저장 (bottom-up)

위 그림을 코드로 구현해 봅시다.

Recursive로 구현

#recursive
def fibonacci(x):
  if x==0:
    return 0
  if x==1:
    return 1
  return fibonacci(x-1)+fibonacci(x-2)
  
  
fibonacci(8)

>>> 21

DP로 구현

#dp
def fibonacci_dp(x):
  dic = {}
  dic[0] = 0
  dic[1] = 1
  for itr in range(2, x+1):
    dic[itr] = dic[itr-2] + dic[itr-1]
  return dic[x]


fibonacci_dp(8)

>>> 21

🧐정리

• dp를 사용하면 recursion과 달리 매 0,1 결과값으로 그 다음 스텝 값을 계속 저장한다.
• 여기서는 memoization table로 dictionary 자료구조를 이용했다.