[알고리즘] 동적 계획법(Dynamic Programming) - 3

동적 계획법(Dynamic Programming) - 3

동적 계획법이라는 것은 순환식과 뗄레야 뗄수 없는 관계이다. 

다시 말해 순환식을 효과적으로 푸는 테크닉이라고 할 수 있다.

따라서 동적 계획법은 다음과 같은 특징을 가지고 있다.

1. 일반적으로 최적화문제 혹은 카운팅 문제에 적용된다.

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

3. 순환식으로 Memoization 또는 Bottom up 으로 푼다.

동적계획법은 subproblem을 풀어서 원래 문제를 푸는 방식이다. 그런 의미에서 분할 정복법과 공통점이 있다.

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

즉 서로 overlapping하는 subproblem들을 해결함으로써 원래의 문제를 해결하는 것이다.

분할 정복법과 동적 계획법의 차이점에 대해서 좀더 자세하게 알아보자

우선 분할 정복법의 대표적인 예인 quicksort이다.

퀵 소트의 경우 피봇을 기준으로 두 부분으로 나뉘며, 오른쪽과 왼쪽이 완전히 disjoint하다.

왜냐하면 오른쪽의 계산 결과가 왼쪽에 전혀 영향을 미치지 않기 때문이다.

이렇게 두개의 subproblem을 해결함으로써 원래 문제가 해결되기 된다.

다음은 동적 계획법의 일반적인 행렬 경로 문제이다.

i,j까지 오는 경로를 구할때 (i-1, j)와 (i, j-1)까지 오는 subproblem들이 구해져야하는데

이들이 서로 disjoint한것이 아니라 영향을 미치기 때문에 분할 정복법과는 다른 모습을 보인다.

어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때,

그 문제는 optimal substructure를 가진다 라고 말한다.

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

따라서 최단 경로문제를 볼 때 어떤 거리까지의 최단 거리의 부분 집합은 항상 최단 거리이기 때문에

결과값을 구하는 순환식은 optimal substructure를 표현하게된다.

순환식을 세운다는 것은 동적 계획법의 핵심이기 때문에 그리 간단하고 쉽지않다.

그러므로 순환식을 세우는것에는 스킬이 필요하다.

동적 계획법에 대한 순환식을 세우기위해서는 우선,

내가 지금 구하자고 하는 최적해에 대해서 그 최적해의 일부분이 그 부분의 최적해인가에 대한 질문을 던져야한다.

최단 거리 알고리즘에서 설명했던 것과 동일한 말이다.

이를 기준으로 세우고 식을 점점 발전 시킨다면 올바른 순환식이 도출되게 된다.

참고가 되는 것이 있다면 고등학교 과정에서 점화식 파트를 보는 것도 도움이 될것이다.

optimal substructure를 설명하기 위해 다른 예를 보자

다음은 최장 경로 알고리즘이며, 최단 경로와 반대된 결과를 찾아야한다.

1에서 4까지의 최장 경로는 (1,2,3,4)이지만 1에서 3까지의 최장경로는 (1,4,2,3)이다.

따라서 '최장 경로의 일 부분이 그 부분에 대한 최적해다' 라는 것이 당연히 성립하지 않는다는 것이다.

따라서 위와 같은 순환식은 세울수가 없다.

그러므로 위와 같이 식이 수정되야한다.

S에서 u 까지 A에 속한 원소들과 v 모두를 지나지 않고 도달하는 것을 찾고 최대값을 구한다.

최장 경로 문제에 대해서는 최적해가 그 부분에 해당하는 최적해다 라는 조건이 성립하지 않지만

이 최장 경로 문제가 optimal substructure가 안되며 동적계획법으로 풀수 없는 것은 아니다.

왜냐하면 위와 같이 복잡한 형태, 다른 형태의 optimal substructure를 가지기 때문이다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘