Notice
Recent Posts
Recent Comments
Link
«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
Tags more
Archives
Today
Total
관리 메뉴

목록동적계획법 (1)

c0smicb0y

[알고리즘] Dynamic Programming (동적 계획법)

동적 계획법 정의 : 어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법 최적 하위구조(Optimal Substructure)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다. 분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할정복은 나눈 문제들을 완전히 새로운 하나의 독립된 새로운 문제로 보지만,..
프로그래밍/알고리즘 2015. 1. 13. 01:22
Prev 1 Next