다이나믹 프로그래밍

다이나믹 프로그래밍

• 다이나믹 프로그래밍(동적 계획법) : 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해(메모리 저장)를 활용하는 알고리즘
• 다이나믹 프로그래밍의 조건
  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 다이나믹 프로그래밍 2가지 종류

1. 탑다운 방식(재귀함수) : 큰 문제를 해결하기 위해 작은 문제를 호출

   • 메모이제이션 기법 : 한 번 구한 결과를 메모해두고 호출해서 그대로 가져오는 방식

     d = [0] * 1000
     def fibo(x):
         if x == 1 or x == 2:
             return 1
         if d[x] != 0:
             return d[x]
         d[x] = fibo(x-1) + fibo(x-2)
         return d[x]
     print('탑 다운 방식 결과:', fibo(99))

2. 보텀업 방식(반복문) : DP테이블(결과 저장용 리스트)를 이용, 작은 문제부터 차근차근 답을 도출함

   t = [0] * 1000
   t[1] = 1
   t[2] = 1
   n = 99
   
   for i in range(3, n+1):
       t[i] = t[i-1] + t[i-2]
   print('보텀 업 방식 결과:', t[n])

다이나믹 프로그래밍 문제를 푸는 방법

1. 다이나믹 프로그래밍 유형임을 파악하기
   • 완전 탐색 알고리즘으로 접근했을 때, 시간이 오래 걸린다면
2. 탑다운 방식보다는 보텀업 방식으로 구현하기
   • recursion depth오류가 발생하면 setrecursionlimit()함수 호출하기
3. 점화식 만들어보기, 그림 그려보기