📖 동적 계획법(Dynamic Programming)

---

• 완전검색을 스마트하게 하는 방법
• 재귀 + 메모이제이션 이라고 할 수 있음
• 점화식으로 표현 가능

💬 메모이제이션

---

• 컴퓨터 프로그램을 실행할 때 이전 계산 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하는 것
• 전체적인 실행 속도를 빠르게 하는 기술
• 동적 계획법의 핵심 기술

문제점

• 추가적인 메모리 공간이 필요
• 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우 발생 가능
  • 반복문으로 가능하면 반복문으로 수행

💬 동적 계획 알고리즘

---

• 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
• 최적화 문제 : 최적(최대값이나 최소값 같은)값을 구하는 문제
  • 해당 문제에 여러 해가 있을 수 있음
  • The 최적해가 아니라 an 최적해 구하는 것
• 먼제 작은 부분 문제들의 해를 구하고 이들을 이용해 보다 큰 크기의 부분 문제들을 해결해, 최종적으로 원래 주어진 문제를 해결하는 알고리즘

◾ 동적 계획법의 적용 요건

최적 부분문제 구조(Optimal substructure)

• 어떤 문제가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함
• 동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적 해들을 이용하여 구하기 때문에 만약 큰 문제의 최적 해를 작은 문제들의 최적화의 해들로 구성되지 않으면 적용 불가

중복 부분문제 구조(Overlapping subproblems)

• DP는 큰 문제를 이루는 작은 문제들을 먼저 해결 후 작은 문제들의 최적 해를 이용해 순환적으로 큰 문제 해결
  • 순환적인 관계를 표현하기 위해 동적 계획법에서는 일반적으로 점화식 사용
• 순환적인 성질 때문에 이전에 계산되었던 작은 문제의 해가 필요하게 되는데, 이를 위해 DP에서는 이미 해결된 작은 문제의 해를 저장 공간에 저장하게 됨
• 이 저장된 해들을 저장 공간(table)의 참조를 통해서 중복된 계산 피할 수 있음

💬 DP 적용 접근 방법

---

• 최적해 구조의 특성 파악
  • 문제를 부분 문제로 나눔
• 최적해의 값을 재귀적으로 정의
  • 부분 문제의 최적해 값에 기반해 문제의 최적해 값 정의
• 상향식 방법으로 최적해의 값 계산
  • 가장 작은 부분 문제부터 해를 구하고 테이블 저장
  • 테이블에 저장되있는 부분 문제의 해를 이용해서 점차적으로 상위 부분 문제의 최적해 구함 (상향식 방법)

💬 분할 정복과 동적 계획법 비교

---

분할 정복

• 연관 없는 부분 문제로 분할
• 부분 문제를 독립, 재귀적으로 해결
• 부분 문제의 해를 결합
  • 병합정렬, 퀵정렬
• 하향식 방법으로 접근

DP

• 부분 문제들이 연관이 없으면 적용 불가능
  • 즉, 부분 문제들은 더 작은 부분 문제들을 공유
• 모든 부분 문제를 한번만 계산하고 결과를 저장 후 재사용
  • 분할 정복은 같은 부분 문제가 나타날 경우 다시 계산
• 상향식 방법으로 접근