DP 다이나믹 프로그래밍 알고리즘

DP란 다이나믹 프로그래밍(dynamic programming)의 약자로 메모리를 적절히 사용해서 시간을 줄이고 효율성을 향상시키는 방법이다

작은 문제들을 모아서 큰 문제를 해결하는 방식으로 사용한다

 

문제 유형

1. 최적 부분 구조

   최적 부분 구조란 하위 부분 문제해결 방법을 통해 최종 문제를 해결

2. 중복되는 부분 구조

   작은 문제들이 반복되고, 같은 문제를 구할때 마다 정답이 같다

방법

1. 메모제이션(memoization) 방식을 이용해서 이미 계산한 결과들은 저장하여 나중에 다시 계산하지 않고 사용한다 하향식(top-down)방식으로 하위 문제들을 해결 했는지 확인하면서 내려간다 만약 작은 문제들이 해결되지 않았다면 그때 작은 문제 해결

   보통 재귀를 이용해서 해결한다

   # 메모제이션 방법을 이용한 피보나치 수열 계산
   import sys
   input = sys.stdin.readline
      
   def memoziation(n):
       if memo[n]:
           return memo[n]
       memo[n] = memoziation(n-1) + memoziation(n-2)
       return memo[n]
      
   k = int(input())
   memo =[0,1,1] + [0 for _ in range(k-2)]
      
   print(memoziation(k))#5
   print(memo)#[0, 1, 1, 2, 3, 5]
   

 

 

1. 타뷸레이션(tabulation) 방식은 상향식(bottom-up)으로 가장 장은 무제 부터 해결하면서 올라간다

   #타뷸레이션 방법을 이용한 피보나치 수열 계산
   import sys
   input = sys.stdin.readline
      
   def tabulation(n):
       for i in range(3,n+1):
           tabu[i] = tabu[i-1] + tabu[i-2]
       return tabu[n]
      
   k = int(input())
   tabu =[0,1,1] + [0 for _ in range(k-2)]
      
   print(tabulation(k))#5
   print(tabu)#[0, 1, 1, 2, 3, 5]