반응형
Optional Substructure [최적 하위 구조]
: 하위 문제의 최적 솔루션을 사용하여 문제를 최적으로 해결할 수 있는 경우 주어진 문제에 최적 하위 구조 속성이 있는 것.
동적 프로그래밍 기술은 이 속성을 활용하여 문제를 더 작은 하위 문제로 분할하고 대신 해결하는 기술입니다.
하위 솔루션 -> 상위 문제 해결 -> 최종 결과 도달
ex) 최단 경로 알고리즘(Shortest Path Problem)
Source node (u) -> Destination node (v)까지의 최단 경로를 찾아야 하는 방법
x : u에서 v까지의 최단 경로에 있는 정점
u -> x : u->x 까지의 최단 경로
x -> v : x->v 까지의 최단 경로
하위 문제의 최적 솔루션을 사용하여 상위 문제 해결 (최적으로 해결)
ex2) All Pair Shortest Path
Floyd-Warshall, Bellman-Ford Algorithm
<참고 자료>
https://www.youtube.com/watch?v=JWTqsNvtwP4&list=PLqM7alHXFySGbXhWx7sBJEwY2DnhDjmxm&index=4
반응형
'PS > 동적 계획 알고리즘[DP]' 카테고리의 다른 글
| 백준 2775 부녀회장이 될테야(c++) (0) | 2023.01.19 |
|---|---|
| [DP] Longest Increasing Subsequence(가장 긴 증가하는 부분 수열), Longest Common Subsequence(최장 공통 부분 수열) (0) | 2023.01.16 |
| [DP] Dynamic Programming에 대해서 (1) | 2023.01.16 |
| 백준 2579 계단 오르기(c++) (0) | 2022.08.23 |
| 백준 2294 동전 2(c++) (0) | 2022.07.29 |