동적 계획법 동적 계획법 (Dynamic Programming)이란 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법을 말한다. 부분 문제가 반복(Overlapping Subproblem)되거나 최적 부분 구조 (Optimal Substructure)를 가진 알고리즘을 효율적으로 해결할 때 사용한다. 최적 부분 구조 (Optimal Substructure) 답을 구하기 위해 수행한 계산을 반복해야 하는 문제의 구조 동적 계획법은 알고리즘이라기보다는 어떤 문제를 풀 때 그 문제를 더 작은 문제의 연장선으로 생각하고 기존에 구한 해를 활용하는 방법을 총칭한다고 이해하는 편이 좋다. 접근 방식 1. 큰 문제를 작은 문제로 표현할 수 있다. 예로 들어 피보나치는 아래와 같이 표현할 수 있다. $$ \begin..