728x90
반응형
동적 계획법 dynamic programming
복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결하여 최종적으로 복잡한 문제의 답을 구하는 방법
구현 방법
1. 큰 문제를 작은 문제로 나눌 수 있어야 함
2. 작은 문제들이 반복해서 나타나고 사용되며, 이 작은 문제들의 결과값은 항상 같아야 함
3. 모든 작은 문제들을 한 번만 계산해 dp테이블에 정리
(추후 재사용시 dp 테이블 이용: "memorization")
4. 동적 계획법은 top-down 방식과 bottom-up 방식이 있다.
반응형
