dynamicprogramming

Dynamic Programming(동적 계획법) 동적 계획법(Dynamic Programming)은 풀고자하는 복잡한문제가 여러단계의 반복되는 부분문제로 이루어졌을 때 각 단계 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 알고리즘 기법이다. 문제를 부분 문제로 단계적으로 나누고, 가장 작은 부분 문제의 답부터 구해 올라오면서 전체 문제의 해를 구하는 것. 계획법(Programming)이란 용어는 코딩(cooding)이 아니라 테이블을 채운다는 문자적 의미(선형 계획법과 유사) 동적 계획법의 특징 작은 하위 문제들의 해결을 통해 전체 문제의 최적해를 구한다. 큰 문제를 작은 문제로 나눌 수 있어야 한다. 모든 하위 문제들의 해결 과정에서 중복되는 계산을 피하기 위해 메모이제이션(memoiza..