Dynamic Programming

Dynamic Programming 

 한국어로는 동적계획법이라 하며 Divide & Conquer와 같은 패러다임의 일종이다.예를 들어보면 다음과 같다.

Ways to Climb1

이 계단을 다 오르기 전 단계는 무조건 3가지 경우중 하나가 된다.

Ways to Climb2

얼핏보면 다음과 같이 재귀트리를 표현할 수 있다.

Ways to Climb3

얼핏보면 Divide & Conquer과 비슷하다.실제로 접근법 자체는 크게 다르지 않다.이후 더 깊이 재귀 절차를 보면 다음과 같다.

Recursive Process

 여기서 DP의 핵심은 반복되는 요소들이다.ways(n-2)는 2번 반복되는데 둘다 동일한 값이고 나머지 요소도 그렇다.즉,DP의 핵심은 이러한 반복되는 요소들을 저장해놓고 다시 계산하지 않고 불러서 사용하는 것 이다.중복되는 값을 저장하고 사용함으로써 선형 시간 복잡도를 갖는다.만일 저 문제를 DP로 해결하지 않는다면 시간복잡도는 $3^{n}$이 될것이다.

이제 제대로된 DP정의는 문제를 더 작은 하위 문제로 나누고, 동일한 하위 문제를 여러 번 푸는 것을 피하기 위해 각 하위 문제의 결과를 저장하여 문제를 해결하는 알고리즘 기법이다.

Properties of DP Problems

  동적 계획법을 적용할 수 있는 문제들이 가지고 있는 두 가지 중요한 성질은 다음과 같다.

1. Optimal Substructure(최적 부분 구조):문제의 최적 해답을 그 하위 문제들의 최적 해답을 통해 구할 수 있을 때 이 성질을 가지고 있다고 한다.즉,더 큰 문제를 작은 문제로 나누고,그 작은 문제들의 최적 결과를 이용해 큰 문제의 최적해를 도출하는 구조다.
2. Overlapping Subproblems(중복되는 부분 문제):동적 계획법에서 하위 문제들은 여러 번 반복해서 등장한다.이러한 중복되는 하위 문제를 다시 계산하지 않고,한 번 계산한 결과를 저장하여 호율적으로 문제를 해결한다.

 

Properties of DP

따라서 Optimal Substructure를 수행하면 점화식을 유도할 수 있다.위의 계단 오르기에서 도출되는 Optimal Substructure는 다음과 같다.

Example-Optimal Substructure

DP Approaches

 DP를 사용할때 두가지의 접근 방식이 존재한다.Top-down(하향식),Bottom-up(상향식)으로 나뉜다.

 

DP Approaches

  Top-down Approach는 하향식 접근으로 역추론과 비슷한 매커니즘이다.계단 오르기에서의 하향식 접근의 파이썬 코드는 다음과 같다.

Top-down Approach

이미 중복된 하위 문제가 memo에 기록되어 있으면 다시 풀지 않고 조회 테이블(memo)에서 그 결과를 반환한다.구현된 식을 살펴보면 점화관계를 알아내면 구현자체는 어렵지 않다.

반면 상향식 접근의 코드는 다음과 같다.

Bottom-up Approach

상향식 접근은 가장 작은 소문제부터 풀기 시작한다.그리고 공간 복잡도는 dp의 배열 만큼 차지하기에 O(n)이다.하지만 더 개선을 할 수 있다.배열을 사용하지 않고 고정된 상수를 통해 O(1)로 줄일 수 있다.

Improvement in Space Complexity

상향식 접근과 하향식 접근의 차이는 다음과 같이 정리할 수 있다.

Comparison of Memorization and Tabulation

Longest Common Subsequence(LCS)

  Longest Common Subsequence는 한국말로는 최장 공통 부분 수열로 두 수열 x[1...m],y[1...n]에서 가장 긴 공통의 수열을 찾으면 되는 것이다.당연히 길이가 같은 서로 다른 수열을 찾을수 도 있는데 그 중 하나만 구하면 된다.예를 들어 x: A B C B D A B,y:B D C A B A이면 LCS는 BCBA가 된다.일단 처음 이 문제를 맞닥뜨리면 아마 x의 모든 부분 수열을 y와 모두 대조해보는 Brute-force 알고리즘으로 접근할 것이다.하지만 이는 굉장히 비효율적이다.우선 x의 모든 부분 수열의 개수는 $2^{m}$이다.이는 각각의 원소가 골라지는이 안골라지는지 2개의 케이스로 나뉘기에 2 * 2 * 2..로 유도된다.그리고 y의 배열과 비교하는데 $O(n)$만큼 걸리기에 브루탈포스 알고리즘에서 최악의 경우 시간복잡도는 $O(n2^{m})$이다.이를 DP로 접근해보면 다음과 같다.

1. 우선 LCS의 길이를 먼저 구한다.
2. LCS를 back-tracking같은 알고리즘으로 찾는다.

LCS의 길이를 구하기 위해서는 x,y의 접두사(Prefix)를 고려해본다.

Strategy

즉,부분 수열의 LCS를 찾는것이 전체 수열의 LCS를 찾는데 도움이 된다.이를 앞에서 최적 부분 구조라 했다.따라서 다음과 같은 식이 도출된다.

Theorem

부분 수열의 LCS에서 다음 수가 공통된다면 +1을 하면되는 것이고 아니면 이떄는 부분 수열의 LCS중 더 긴 것을 선택해야한다.이를 증명하는건 수학적 귀류법으로 증명할 수 있다.