동적 계획법

1 개요

dynamic programming

동적 프로그래밍, 동적 계획법

• 큰 문제를 하위문제들로 나누고 나중에 재결합

하위문제들이 서로 독립적이지 않은 경우가 있음(분할정복과 다른 점)

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용
• 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달
• 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법

2 같이 보기

• 분할 정복 알고리즘
• 그리디 알고리즘