동적 계획법(Dynamic Progamming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는 알고리즘 설계 기법이다. 각 하위 문제를 먼저 해결하고 저장하기 때문에 같은 하위 문제가 나왔을 경우 저장한 값을 이용하여 간단하게 해결할 수 있다. 이를 통해 계산 횟수를 줄이기 때문에 하위 문제의 수가 기하 급수적으로 증가할 때 유용하다. 사용 용도 최단 경로 문제 행렬의 제곱 문제 최적화 문제 ex) 문제의 숫자 범위가 크고, 경우의 수가 많은 경우 사용 조건 - 아래 두 조건이 만족하는 경우 다이나믹 프로그래밍을 이용하여 문제를 해결하는데 유용하다. 부분 중복(반복) 문제 - 이미 진행했던 연산임에도 불구하고 재귀되며 반복적으로 연산되는 문제 최적..