다이나믹 프로그래밍(Dynamic Programming) DP, 동적 계획법 Overlapping Subproblem 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다 문제를 작은 문제로 쪼갤 수 있다 Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법 기본 전략은 문제를 작은 부분 문제로 나누는 것에서 부터 시작한다 작은 부분 문제를 해결한 결과로 큰 문제를 해결할 수 있다 특징은 중복되는 부분 문제들이 있다는 것 적용 방법 문제를 더 작은 부분 문제로 나눈다 중복되는 작은 부분 문제는 한 번만 계산해서 그 결과를 저장 중복되는 작은 부분 문제들은 여러 번 계산하..