동적 계획법

  다른 뜻에 대해서는 동적 프로그래밍 언어 문서를 참조하십시오.

1 개요

dynamic programming

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

• 의사결정 최적화를 위한 수리적 계획법
• 큰 문제를 하위문제들로 나누고 나중에 재결합

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

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

 

2 같이 보기

• 차원의 저주
• 메모이제이션
• 그리디 알고리즘
• 분할 정복 알고리즘

3 참고

• 위키백과 "동적 계획법"
• 영어 위키백과 "Dynamic programming"
• 다음백과 "동적 계획법"
• 네이버백과 "동적 계획법"