[알고리즘 공부] 실전 알고리즘 16강-다이나믹 프로그래밍

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

알고리즘 설명

dp(동적 계획법)은 큰문제를 작은 문제로 나누어서 푸는 방식이다.
여러개의 하위 문제를 먼저 푼 후에 그 결과를 쌓아올려서 주어진 문제를 해결하는 알고리즘이다.

dp를 푸는 과정은 다음과 같다.

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

메모이제이션(Memoization) : 이미 찾은 값을 배열에 저장해서 필요할 때 사용하는 것을 말한다.

동적 계획법의 구현 방식에는 두 가지 방법이 있다.

1. Top-down : 큰 문제를 작은 문제로 쪼개면서 푸는 방식이며 재귀로 구현한다. 메모리 및 시간 소모가 크지만 점화식을 직관적으로 파악할 수 있다.
2. Bottom-up : 작은 문제부터 차례대로 푸는 방식이며 반복문으로 구현한다. 메모리 및 시간을 절약할 수 있다.