개발 공부 - [동적계획법 (Dynamic Programming)] Dynamic Programming - 3

Optimal Substructure

동적계획법

1. 일반적으로 최적화문제(optimisation problem) 혹은 카운팅(counting)

문제에 적용됨

2. 주어진 문제에 대한 순환식(recurrence equation)을 정의한다.

3. 순환식을 memoization 혹은 bottom-up 방식으로 푼다.

동적계획법

subproblem들을 풀어서 원래 문제를 푸는 방식. 그런 의미에서 분할정복법

과 공통성이 있음

분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는

그렇지 않음

즉 서로 overlapping하는 subproblem들을 해결함으로써 원래 문제를 해결

분할정복법 vs. 동적계획법

quicksort의 경우

pivot을 기준으로 분할된

두 subproblem은 서로 disjoint하다.

: 각각 따로 데이터를 정렬하는 방법 (pivot 기준 앞/뒤)

Optimal Substructure

어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로

구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말한다. (A

problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.)

분할정복법, 탐욕적기법, 동적계획법은 모두 문제가 가진 이런 특성을 이용

한다.

Optimal Substructure를 확인하는 질문

“최적해의 일부분이 그부분에 대한 최적해인가?”

최단경로(shortest-path) 문제

순환식은 optimal substructure를 표현한다.

Optimal Substructure를 확인하는 질문

최장경로(Longest-Path) 문제

노드를 중복 방문하지 않고 가는 가장 긴 경로

optimal substructure를 가지는가?