동적 계획법 (3) - 퀵정렬 & 최장 경로

Dynamic Programming (3)

 

동적 계획법

- 일반적으로는 최적화 문제(촤대값 & 최소값, Optimisation Problem) 혹은 카운팅(Counting) 문제에 주로 적용된다.

- 주어진 문제에 대한 순환식(Recurrence Equation)을 정의한다.

- 정의한 순환식을 Memorization 혹은 Bottom-Up방식으로 변환한다.

- Sub Problem들을 풀어 원래의 문제를 푸는 방식이다. 그러한 의미에서 본다면 분할 정복법과도 공통점을 찾을 수 있다.

- 분할 정복법에서는 분할된 문제들이 서로 Disjoint하지만, 동적계획법은 그렇지 않다.

- 서로 Overlapping하는 sub problem들을 해결함으로 원래의 문제를 해결하게 된다.

분할 정복법 vs 동적 계획법

- quick sort의 경우

pivot을 기준으로 분할된 두 subproblem은 서로 disjoint하다고 할 수 있다.

- 행렬 경로 문제의 경우

 

Optimal Substructure

- 어떠한 문제의 최적 해가 그 문제의 subproblem들의 최적 해로부터 효율적으로 구해질 수 있다고 할 때 그 문제는 곧 optimal substructure를 가진다고 한다.

- 분할 정복법, 탐욕적 기법, 동적 계획법은 모두 문제가 가진 위의 특성을 이용한 풀이법이다.

 

Optimal Substructure를 확인하는 법

- 최적 해의 일부가 여전히 그 부분에 대한 최적 해인지의 여부 파악

- 최단 경로 문제

- 순환식은 optimall substructure로 표현한다.

- 최장 경로(Longest-Path) 문제

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

optimal substructure를 가지는가?

-> 아래의 예시를 보듯이 3까지 갈 때 4를 거쳐 가는 것이 가장 긴 경로이지만 이는 1~4까지 가는 최장경로를 지날 때 지날 수 없는 경우의 수이기 때문에 최적 해의 일부분이 여전히 그 부분의 최적 해인가에 대한 답을 줄 수 없게 된다.

-> 하지만 optimal substructure을 갖지 않는것이 아닌 조금 더 복잡한 형태를 띄고 있어 여전히 동적 계획법을 이용하여 문제를 해결할 수 있다.