정의

**Dynamic Programming(동적 프로그래밍)**은 문제를 작은 하위 문제로 나누어 부분 문제의 결과를 재사용함으로써 효율적으로 문제를 해결하는 기법입니다. 주로 최적화 문제와 결정 문제를 푸는 데 사용됨

특징

1. Overlapping Subproblems (부분 문제의 중복)

• 큰 문제를 작은 하위 문제로 나눌 수 있고, 이 하위 문제들이 여러 번 반복적으로 나타남.
• 예: 피보나치 수열 계산.

2. Optimal Substructure (최적 부분 구조)

• 문제의 최적 해가 그 하위 문제들의 최적 해를 이용해 얻어질 수 있음.
• 예: 최단 경로 문제.

3. Memoization 또는 Tabulation

• Memoization: 재귀를 사용하며, 계산 결과를 메모리에 저장해 필요할 때 바로 가져옴 (Top-Down 방식).
• Tabulation: 반복문을 사용해 값을 순차적으로 채워 넣음 (Bottom-Up 방식).

동작 원리

1. 문제 정의
2. 점화식 작성
3. 초기값 설정
4. 결과 계산

구현 방식

1. Top-Down 방식 (재귀 + 메모이제이션)
   • 큰 문제를 해결하기 위해 재귀적으로 작은 문제를 호출.
   • 이미 계산된 값은 저장해두고, 재사용.
2. Bottom-Up 방식 (반복문)
   • 작은 문제부터 점차적으로 큰 문제를 해결하며, dp 테이블을 채워나감.

유형

1. 최적 경로 문제 : 최소 비용 경로, 최단 경로 (다익스트라, 플로이드 워셜)
2. 배낭 문제 : 정수 배낭 문제, 0/1 배낭 문제