Dynamic programming은 문제를 subproblems로 쪼개서 문제를 푸는 방식이다.
subproblem들이 독립적이면 divide-and-conquer 방식으로 풀 수 있고
독립적이지 않으면 dynamic programming을 한다.
독립적이지 않은 것의 의미는 sub problems가 subsub problems를 공유하는 것이다.
dynamic programming 알고리즘은 같은문제를 또 풀지 않기 위해서 subproblem을 한번만 풀고, 그 결과를 table에 저장한다. 그리고 나중에 필요할 때, 테이블을 참조해서 값을 가져온다.
Dynamic programming은 최적화 문제(optimization problems)를 푸는데 이용된다.
솔루션은 여러개이지만 그중에 최적화 된 값(최소값 or 최대값)을 가진 솔루션은 하나다. Dynamic programming으로 그 솔루션을 찾는다.
문제 푸는 4가지 단계
1. optimal substructure를 구한다.
2. recursive solution을 구한다.
3. optimal solution의 값을 bottom-up 방식으로 계산한다.
4. 계산된 정보로 optimal solution을 구한다.
optimal solution의 sub solution도 optimal solution이다.
overlapping subproblems
순환적인 알고리즘이 같은 문제를 계속 반복하여 방문할 때.
참고
subproblem들이 독립적이면 divide-and-conquer 방식으로 풀 수 있고
독립적이지 않으면 dynamic programming을 한다.
독립적이지 않은 것의 의미는 sub problems가 subsub problems를 공유하는 것이다.
dynamic programming 알고리즘은 같은문제를 또 풀지 않기 위해서 subproblem을 한번만 풀고, 그 결과를 table에 저장한다. 그리고 나중에 필요할 때, 테이블을 참조해서 값을 가져온다.
Dynamic programming은 최적화 문제(optimization problems)를 푸는데 이용된다.
솔루션은 여러개이지만 그중에 최적화 된 값(최소값 or 최대값)을 가진 솔루션은 하나다. Dynamic programming으로 그 솔루션을 찾는다.
문제 푸는 4가지 단계
1. optimal substructure를 구한다.
2. recursive solution을 구한다.
3. optimal solution의 값을 bottom-up 방식으로 계산한다.
4. 계산된 정보로 optimal solution을 구한다.
optimal solution의 sub solution도 optimal solution이다.
overlapping subproblems
순환적인 알고리즘이 같은 문제를 계속 반복하여 방문할 때.
참고
cs.kangwon.ac.kr/~ysmoon/courses/2011_1/alg/06.pdf
'공부 > 알고리즘' 카테고리의 다른 글
Data Structures for Disjoint Sets (0) | 2011.07.11 |
---|---|
Greedy Algorithms (0) | 2011.07.11 |
11장 Hash Table (0) | 2011.07.08 |
8장 Sorting in Linear Time (0) | 2011.07.03 |
7장 Quicksort (0) | 2011.07.03 |