다이나믹 프로그래밍 (Dynamic Programming, DP)

겹치는 하위 문제(Subproblem)를 해결하고 그 결과를 저장해 나가는 방식으로 최적화
 

문제들 특징

1. 작은 하위문제들이 반복적으로 발생하며, 이들의 해결 결과가 재활용될 수 있을 때
2. Optimal Substructure(최적부분구조)을 갖춘 문제. 큰 문제의 최적해가 작은 문제의 최적해를 통해 구할 수 있을 때
3. 중복된 계산을 최소화할 수 있는 구조. 같은 하위 문제를 반복해서 해결해야 할 때
 
하위문제가 독립적, 줄여가면서 해결 -> Divide & Conquer
하위문제가 중첩됨, 반복해야 함 -> Dynamic Programming
 

DP로 해결하는 대표적인 문제들

• longest common subsequence
• Knapsack problem
• Rod cutting problem
• shortest common supersequence

 

Top-down vs Bottom-up

1. Top-down 방식 (메모이제이션)

Top-down 방식은 재귀적 구조를 활용하며, 큰 문제를 작은 문제로 나누어 해결.
이 방법은 "메모이제이션"(caching)을 사용하여 이미 계산된 결과를 저장하고, 필요할 때 재사용.

- 특징
  - 재귀적 구조를 사용, 코드가 직관적
  - 필요한 부분만 계산하고, 계산하지 않은 부분은 호출되지 않음
  - 중복 계산을 피하기 위해 메모리에 계산 결과를 저장

- 단점
  - 재귀 호출의 오버헤드가 있어 비효율적일 수 있다
  - 시스템에 따라 재귀 호출 깊이가 제한되어 있어, 매우 깊은 재귀 호출이 필요한 경우 스택 오버플로우를 일으킬 수 있다.
 

2. Bottom-up 방식

Bottom-up 방식은 작은 문제부터 시작하여 점차적으로 큰 문제를 해결해 나가는 방식.
이 방법은 반복문을 사용하여 구현되며, 모든 계산 결과를 테이블(일반적으로 배열)에 저장.


- 특징
  - 반복문을 사용하여 구현되므로, 재귀 호출의 오버헤드가 없다.
  - 문제를 작은 부분부터 차례대로 해결하기 때문에, 모든 중간 결과를 계산하고 저장
  - 테이블을 사용하여 각 단계의 결과를 저장하므로, 재귀적인 메모리 사용보다 일반적으로 메모리 사용량이 더 많을 수 있다

- 단점
  - 모든 중간 결과를 계산하기 때문에 필요하지 않은 계산이 포함될 수 있다
  - 코드가 반복문에 의존하므로, 때로는 구현이 더 복잡하거나 직관적이지 않을 수 있다

비교

- 메모리 사용: Top-down은 필요한 부분만 계산하므로 메모리를 절약할 수 있지만, Bottom-up은 모든 결과를 저장하기 때문에 더 많은 메모리가 필요할 수 있다.
- 성능: Bottom-up은 재귀 호출의 오버헤드가 없어 대체로 더 빠른 성능을 보일 수 있다. Top-down은 메모리를 효율적으로 사용하지만 재귀의 오버헤드로 인해 느릴 수 있다.
- 구현의 복잡성: Top-down은 재귀로 인해 코드가 더 간단하고 직관적일 수 있지만, Bottom-up은 반복문을 사용하여 약간 더 복잡하거나 구현하기 어려울 수 있다.