bottom-up vs top-down

동적 계획법, DP(Dynamic Programming) c++

동적 계획법( 다이나밍 프로그래밍 ) 이란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 먼저 입력 크기가 작은 부분 문제들(subproblems)을 모두 해결한 후, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 동적 계획법, 다이나믹 프로그래밍, DP 모두 같은 말이므로 쉽게 DP라고 통일하겠습니다! DP는 이전 부분 문제의 최적해를 기록해놓으므로 완전 탐색 알고리즘보다 빠릅니다. 하지만 해당하는 문제가 최적 부분 구조를 가져야만 DP 알고리즘을 적용할 수 있습니다. 최적 부분 구조는 무엇일까요? 최적 부분 구조(optimal substructure)란 다음과 같습니다. 큰 문제의 최적해에 작은 문제의 최적해가 포함 순환..