mondegreen

동적계획법의 개념 그리지 알고리즘과 같이 최적화 문제를 해결하는 방법으로서 먼저 작은 부분의 문제들의 해를 구하고 이들을 이용하여 보다 큰 부분 문제를 해결한다. 이러한 방식으로 최종적으로 원래 주어진 문제를 해결하는 방법 동적계획법의 특징 1) 상향식 방법으로 접근한다. 2) (중복 부분문제 구조) 부분 문제 간 연관이 있어야만 적용 가능하다. 3) (중복 부분문제 구조) 모든 부분 문제는 한번만 계산한 뒤 결과를 저장하여 그 결과값만 재사용한다. (재계산 아님) 4) (최적화의 원칙) 전체 문제의 해가 최적이려면 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다. 5) 수행 속도가 빠름 => 재귀와 달리 중복 계산이 없고, 반복문 사용으로 함수 호출없다. => 이 '중복 부분문제 구조 Over..