동적 계획법 DP 최적화 문제를 해결하는 알고리즘 최대, 최소, 경우의 수 작은 부분 문제부터 해결하고 이들을 이용해서 보다 큰 크기의 부분 문제를 해결하여 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법 recursive하게 일어나는 점화식을 유도해내는 것이 관건 점화식 : 각각 항들의 관계를 나타낸 식 필요 요건 중복 부분 문제 구조 작은 부분으로 쪼개서 해당 부분의 결과가 다른 부분의 결과를 도출하는데 사용 작은 문제 먼저 해결 → 작은 문제의 최적해를 이용하여 순환적으로 큰 문제 해결 점화식 유도가 가능해야 한다. 순환적인 성질 때문에 이전에 계산했던 문제의 해가 다른 곳에서도 필요하게 되는데 이를 위해 DP에서는 저장 공간(table)에 해를 저장하게 된다. 저장된 해들이 다시 필요할..