[알고리즘][동적계획법] 동적계획법 #3 Optimal Substructure

학습목표
1. Optimal Substructure에 대해서 학습
2. Optimal Substructure를 가지는 최단경로(Shortest-Path)에 대해서 학습
3. Optimal Substructure를 가지지 않는 최장경로(Longest-Path)에 대해서 학습

 

1. 동적계획법 수행과정

일반적으로 동적계획법 문제를 해결하기 위한 수행과정은 다음과 같습니다.

1. 동적계획법 문제는 최적화문제(optimisation problem, 최솟값 혹은 최댓값 탐색) 혹은 카운팅(counting) 문제에 적용됨
2. 주어진 문제에 대한 순환식(recurrence equation)을 정의함
3. 정의된 순환식을 기반으로 memoization 혹은 bottom-up 방식으로 해결함

 

2. 동적계획법 특징

동적계획법의 특징은 다음과 같습니다.

• 부분문제(subproblem)들을 해결하여 원래 문제를 해결하는 방식. 그런 의미에서 분할정복법(divide and conquer)과 공통성이 있습니다.
• 분할정복법에서는 분할된 문제들이 서로 영향을 주지 않는다. (disjoint)
• 동적 계획법의 부분문제들은 서로 결과에 영향을 줍니다. 즉, 동적계획법은 서로 겹치는 부분문제들을 해결함으로써 원래 문제를 해결합니다.

분할정복법의 대표적인 예시로는 퀵정렬(QuickSort)가 있습니다.

퀵 정렬은 pivot을 기준으로 왼쪽과 오른쪽으로 부분문제들로 나누고 정렬하는 정렬 알고리즘입니다. 이때 왼쪽 부분문제의 결과는 오른쪽 부분문제의 결과에 영향을 미치지 않는다는 특징이 있습니다. 이것을 disjoint한다고 말할 수 있습니다.

 

퀵 정렬과 같이 분할정복법은 동적계획법과 같이 하나의 큰 문제를 여러개의 부분문제들로 쪼개어 해결하는 방식이지만 동적계획법과는 달리 분할정복법은 부분문제들이 다른 부분문제들에 영향을 주지는 않습니다.

 

동적계획법의 대표적인 예시로는 행렬경로(Matrix-Path)가 있습니다.

위 그림에서 파란색 박스와 빨간색 박스는 서로 다른 부분문제이지만 목표 좌표 (n-1,n-1)의 값을 계산하기 위해서 서로 겹치는 부분이 존재합니다. 이는 한 부분문제가 다른 부분문제의 결과에 영향을 준다는 의미입니다. 이것을 disjoint하지 않다고 말할 수 있습니다.

 

정리하면 동적계획법의 부분문제들은 서로 다른 부분문제의 결과에 영향을 줄 수 있습니다.

 

3. Optimal Substructure란 무엇인가?

Optimal Substructure란 어떤 문제의 최적해가 그것의 부분문제(subproblem)들의 최적해로부터 효율적으로 구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말할 수 있습니다. 분할정복법, 탐욕적기법, 동적계획법은 모두 문제가 가진 이런 특성을 이용합니다.

 

Optimal Substructure를 가지는 최단경로(shortest-path) 문제

위 그림에서 시작 노드 s에서 중간 노드 v까지의 경로들중 빨간선이 최단 경로라면 빨간석은 s에서 v까지의 최단경로입니다. 만약 빨간선이 아닌 s에서 v까지가는 다른 최단 경로가 있다면 빨간선이 아닌 다른 선이 최단 경로가 될 것입니다. 

 

위 그림에 대한 순환식을 정의하면 아래와 같을 것입니다.

• d[u] : 목적지 노드 u까지 가는 최단 경로의 길이
• min v adjacent to u : u에 인접한 노드 v 중 최소
• d[v] + w(v,u) : 노드 v까지 가는 최단 경로 길이 + v에서 u까지 가는 가중치

위 순환식을 정리하면 시작노드 s에서 u까지 가는 최단 경로의 길이는 u에 인접한 노드 v까지의 최단 경로와 노드 v에서 노드 u까지 가는 가중치의 합중에서 최소인 값을 의미합니다.

 

Optimal Substructure를 가지지 않는 최장경로(Longest-Path) 문제

위의 Optimal Substurcture를 가지는 최단경로와는 반대로 최장경로 문제는 Optimal Substructure를 가지지 않습니다. 최장 경로 문제는 어떤 노드에서 출발하여 도착노드까지 도달하는데 가장 긴 경로 값을 계산하는 문제입니다. 단, 노드를 중복방문하면 안됩니다. 

 

최장 경로를 계산하기 위해서 생각해볼 수 있는 방법은 최단 경로에서 처럼 도착 노드의 인접 노드까지의 최장 경로를 구하고 인접노드에서 도착노드까지의 가중치 중 최대값을 선택하면 최장 경로를 계산해볼 수 있을 것입니다. 하지만 시작 노드 1에서 도착 노드 4까지의 최장 경로는 (1,2,3,4)인데 반해 1에서 3까지의 최장 경로는 (1,4,2,3)인 것을 볼 수 있습니다. 이 의미는 중간 노드까지의 최장 경로가 전체적인 최장 경로 해의 일부분이 아니라는 의미입니다.

위의 그림을 정리하면 u까지 가는 최장경로가 v를 지난다고 하더라도 그 경로상에서 v까지 가는 경로가 반드시 v까지 가는 최장 경로가 아닐수도 있으므로 이런 순환식은 성립하지 않습니다. 

 

그렇다면 최장경로 문제는 Optimal Substructure를 갖지 않는 것인가? => NO

 

최장 경로의 순환식은 다음과 같이 정의할 수 있습니다.

• d(v, A) : 시작 노드 s에서 집합 A에 속한 어떤 노드도 지나지 않고 u까지 가는 경로들 중에서 최장 경로의 길이를 의미합니다.
• 만약 노드 v가 집합 A에 속한다면 최장 경로는 존재하지 않습니다.
• 만약 노드 v가 시작 노드 s라면 v까지의 최장 경로는 0입니다.
• 그 외의 경우에는 v와 인접한 u까지의 최장 경로는 집합 A와 v가 속한 어떤 노드도 거치지 않고 v까지 가는 최장 경로 길이 + u에서 v까지 가는 가중치의 합계중에서 최대값을 의미합니다.

위 순환식을 통해서 최장 경로 문제는 다른 형태의 optimal substructure를 가지는 것일뿐 optimal substructure를 가지지 않는다고 말할 수 없습니다.

 

References

[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌