다이나믹프로그래밍1 [코딩테스트/알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. 1940년 Richard Bellman이 처음으로 Dynamic Programming이란 단어를 사용했는데 멋있어 보여서 이름 붙였다고 한다. (궁금해서 찾아보니까 벨만-포드 알고리즘의 그 벨만이 맞았다.) 다이나믹 프로그래밍으로 문제를 풀기 위한 조건 1. Overlapping Subproblem 문제를 작은 문제로 쪼갤 수 있다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. 2. Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 각 문제들은 Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정.. 2022. 8. 29. 이전 1 다음