다이나믹 프로그래밍

 

 

Dynamic Programming, 동적계획법

• DP란 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어질 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법
• 분할정복은 문제를 위에서 아래로 쪼개지만 (top-down), DP는 작은 부분 문제부터 상위에 있는 문제로 풀어 올라간다(bottom-up).
• 분할정복의 쪼갠 문제는 완전히 독립적인 하나의 새로운 문제이지만, DP는 각 단계의 부분 문제들이 이전 단계에 있는 문제들의 답에 의존한다. => DP는 한번 푼 적이 있는 부분 문제의 답은 다시 푸는 일이 없도록 테이블에 저장하여 재활용
• 메모이제이션 (memoization) : 결과를 저장하는 장소를 마련해 두고, 한번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법.
• 메모이제이션 구현 패턴
  1. 항상 기저 사례를 제일 먼저 처리하고 테이블에 저장
  2. 점진적으로 상위 부분 문제를 풀때 해당 답을 구한 적이 있으면 테이블에서 곧장 반환
  3. 구한적이 없으면 답을 계산하고 테이블에 저장
• 다이나믹 프로그래밍 동작 방식
  1. 문제를 부분 문제들로 나눈다
  2. 가장 작은 부분 문제(base case)부터 해를 구한 뒤 테이블에 저장한다
  3. 상위 부분 문제의 해를 구하는데 해당 답을 구한적이 있으면 테이블에서 곧장 반환
  4. 구한적이 없으면 답을 계산하고 테이블에 저장
  5. 위와 같이 테이블을 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.
• 타일링 문제 : boj.kr/11726
  • base case : n==1 -> return 1 ;
  • base case : n==2 -> return2 ;
  • 규칙을 찾아 점화식을 정의 D[n] = D[n-2] + D[n-1]