동적프로그래밍 (Dynamic Programming)에 대하여

❓ 동적 프로그래밍이란

• 동적 프로그래밍(이하 DP)는 컴퓨터 프로그래밍이 아니라 테이블을 만드는 것이다.
• 또한 전혀 다이나믹하지 않아 기억하기 프로그래밍이라고도 불린다.
• 반복적으로 계산되는 것들을 저장해두었다가 사용하는 메모이제이션 방법이 DP의 한 방법이다.
• 알고리즘을 짤 때 Divide and Conquer 방법을 많이 사용하는데 이 때 한 문제를 여러 개의 작은 문제로 나누어 풀게되어 같은 문제를 반복해서 푸는 경우가 발생한다. 이를 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 DP이다.
• 즉, 작은 문제들은 한 번만 풀어서 계산한 값을 저장해두어야한다. (Memoization)

📌 Bottom Up & Top Down

• Bottom Up : 작은 문제부터 하나하나 해결해나가는 방법.

def fibo_bottom_up(n) :
   if n <= 1:
       return n

   fir = 0
   sec = 1
   for i in range(0, n - 1) :
       next = fir + sec
       fir = sec
       sec = next
   return next

• Top Down : 재귀함수로 대부분 구현, 큰 문제를 풀 때 작은 문제가 풀리지 않았다면 그제서야 해결하게된다.

def fibo_top_down(n) :
   if memo[n] > 0 :
       return memo[n]

   if n <= 1:
       memo[n] = n
       return memo[n]

   else :
       memo[n] = fibo_top_down(n - 1) + fibo_top_down(n - 2)
       return memo[n]

🙋‍♂️ 정리

• 큰 문제를 풀 때 작은 문제부터 하나하나 해결하다보면 규칙을 발견할 수 있게된다.
• dp[0], dp[1], dp[2], dp[3]를 해결하다보면 규칙을 발견하고 dp[4]를 해결할 때 쯤 이전에 구해놓은 작은 문제들로부터 점화식을 구할 수 있게된다.

👀 출처

이곳과 이곳을 많이 참고했습니다.