[algorithm] Dynamic Programming
개요 Dynamic programming(이하 DP)은 알고리즘 문제를 풀기 위한 디자인 패러다임 중 하나이다. DP는 최적화(optimization)문제에 사용되는데, 참고로 greedy 알고리즘 또한 최적화 문제를 위한 알고리즘이다. 여기서 optimization이란 최적의 값을 찾는 과정으로, minimization과 maximization의 두 종류가 있다. 정의 DP는 해당 문제에 대해 더 작은, 간단한 문제들로 구성하여 해답을 찾아 나가는 전략이다. 즉, 해당 문제 S에 대해서 아래처럼 표현할 수 있다. S=combine(S1,S2,...,Sm ) optimal substructure DP는 optimal substructure를 가진다고 정의된다. 증명을 통해 이해할 수 있겠지만, 생각보다 ..
algorithm
2023. 6. 26. 20:35