[알고리즘] 동적계획법

백준 동적계획법 문제를 풀다가 동적계획법에 대해 잘 정리해놓은 게시물이 있어 공유한다.

 

https://velog.io/@bonjaski0989/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-%EC%A0%95%EB%A6%AC%EA%B8%80Python

동적계획법(Dynamic Programming) 정리글_Python

---

간단히 말해, 동적 계획법은 소문제의 결과를 다른 소문제를 푸는 데에 사용하는 풀이법으로, 동적계획법을 사용하기 위해서는 부분해가 전체 문제의 해를 구하는 데 사용되는 지 여부를 가리키는 최적성의 원리를 만족하는지 우선 판단해야 한다.

점화식을 생각하면 간단하다.

동적 계획법은 항상 최적의 결과를 도출하지만, 탐욕법은 문제에 따라 최적해가 구해지지 않을 수 있다고 한다.

 

---

동적계획법 관련 문제 풀이

https://live-for-myself.tistory.com/223

[CodingTest] 백준 #9184 신나는 함수 실행

memoization(하향식) 풀이방법을 사용했다.