[Do it! 알고리즘 코딩테스트 with C++] 9장. 다이나믹 프로그래밍

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 9장. 다이나믹 프로그래밍

9-1. 다이나믹 프로그래밍

---

📌 9-1. 다이나믹 프로그래밍

* 다이나믹 프로그래밍
- 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 알고리즘

* 다이나믹 프로그래밍 특징
- 큰 문제를 작은 문제로 나눈다.
- 작은 문제들이 반복되어 나타나고 사용되며 작은 문제들의 결과는 항상 같다.
- 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하고 추후 테이블을 재사용할 수 있다. = 메모이제이션 기법
- 바텀-업(반복문), 탑-다운(재귀함수)로 구현 가능하다.

* 다이나믹 프로그래밍 동작 원리
1. 다이나믹 프로그래밍에 적합한지 확인
2. 점화식 생성 ex. D[i] = D[i - 1] + D[i -2] - 피보나치
3. 메모이제이션 기법 사용
4. 바텀-업 or 탑-다운 구현

---