Review 11 - Dynamic Programming

https://eglife.tistory.com/123

Review 10 - Single-Source-Shortest Path in C++

 

프로그래밍 최악의 손님 DP다.

 

재귀적으로 진행되는 코딩은 솔루션을 펼쳐놓고 봐도 뭔 소린지 모를 때가 많다..

 

내 생각엔, 여기서 이걸 한 번에 탁 탁 이해하는 사람이 소위 알고리즘 천재라고 불리는 사람들이고,

 

여기서 많은 사람들이 벽을 느낀다. 물론 필자를 포함해서..ㅠㅠ

 

Recursive는 어지간하면 최후의 수단으로 사용하려 하고, 자유자재로 다루기엔 대단한 내공이 필요한 영역이다.

 

 

1. Divide and Conquer

 

사실, DP를 개념을 몰라서 문제를 못 푸는 사람은 없을 것이다.

 

다만, 어떻게 특정 문제를 DP로 전개해 나가는지 각이 안 잡힐 뿐이지..

 

어쨌든, 이 Divide and conquer는 merge sort, quick sort, binary search 등 다양한 파트에 쓰인다.

 

주로 Base Case와 Recursive Case로 나뉜다.

위는 대표적인 Divide & Conquer의 예시이며 보통 Recursive Case이고 Exponential time complexity가 소요된다.

즉, 식은 간단한데 시간소요가 꽤 큰 것

 

그래서 이를 보완하고자 나온 개념이 DP이다.

 

지금껏 Divide & Conquer = Dynamic Programming으로 알고 있었는데 차이점이 있었네

 

 

2. Dynamic Programming

DP의 가장 큰 특징은,

 

subproblem을 풀 때, 그 결과를 저장해두어서 계산의 중복을 막는다.

 

즉 Memory를 사용해서 Time을 줄이는 Trade off 방식을 사용한단 것이다.

 

DP는 문제의 최적화에 초점을 맞추며, 주로 여러 Solution 중에 최소/최대의 무언가를 구하는 문제에 많이 쓰인다. 대표적으로 이 전 시간에 다루었던 Bellman Ford 알고리즘의 경우도 최소 path를 구하는 문제라 DP에 적합하다.

 

DP의 경우, subproblem의 output이 많아야 유리하다.

 

 

3. 4 steps of DP

 

- 문제에 Optimal Solution이 있는지 check를 한다. 문제에 overlapping 되는 subproblme이 있어야 하고 , 작은 사이즈의 subproblem이 있어야 한다.

- Recursive하게 Optimal Solution의 값을 정해야하 한다.

- Top-down 또는 Bottom-up 방식으로 Optimal Solution의 값을 계산해야 한다. ex: shortest path weight

- 위에 계산된 결과로 Optimal solution을 만들어야 한다. ex: shorted path predecessor

결론적으로 이 전에 구했던 값을 계속 꺼내서 사용하면 DP라는 것이다.

 

Bellman Ford를 예로 한 번 들어보면,

Bellman Ford는 일단, 최대 1개의 edge로 갈 수 있는(from source) shortest path를 구하고, 그것을 저장한다.

 

다음으로 최대 2개의 edge로 갈 수 있는 path를 구하고 그것 또한 저장한다.

 

이 저장해놨던 데이터들이 나중에도 계속 사용되고 업데이트되며, Iteration이 V-1번 돌면 계산을 멈춘다.

 

 

4. Elements of DP

 

- Optimal Sub-Structure:

특정 문제가 작은 sub - problems로 쪼개질 수 있어야 한다. ex: Bellman ford : v_i+1.d = min(v_i.d,min(u_i.d+w(u,v)))

 

- Overlapping subproblems:

subproblem 끼리 겹치는 부분이 있어야 한다. Bellman ford 같은 경우도, V_K.d가 V_K+1.d, V_K+2.d 등을 구할 때 계속 쓰인다.

 

 

DP의 문제해결 Logic이 DAG와 비슷하다는 얘기.

 

대표적인 DP의 예제론 Rod Cutting이 있다.

 

이걸 그냥 Recursive 하게 풀어버리면 function call이 많아져서 시간이 exponential하게 잡힌다.

 

그래서 사용하는게 DP!

 

계산값을 저장해뒀다가 나중에 이 값이 필요하면 꺼내서 써버려 시간을 절약하는 것이다.

 

 

Memoization으로 r[n] 값을 계속 저장해서, 나중에 이 값을 쓸 일이 있을 때 꺼내어 쓰게 한다.

 

즉, r[n]은 이제 최초 1회만 계산될 수 있다.

 

이것이 Top-down Dynamic Programming의 위력이다.

 

이번엔 Bottom Up을 한 번 살펴보자. 대표적으로 Bellman Ford가 이 방식의 DP를 사용한다.

 

Bottom - up은 Recursive 하지 않다!

Recursive 하지 않기 때문에 불필요한 시간소모가 없고, 코드 이해가 빠르다.

 

다만 Subproblem끼리 많이 겹치면 Top-down이 더 빠를 수 있다.

 

그리고 Bottom - up은 Recursive하지 않은 대신, 보통 For문 중첩을 사용한다.

 

Bottom up -> overhead가 적다는 장점 / Top down -> sub problem끼리 많이 겹칠때 시간소모가 적다는 장점 有!

 

그렇다면 DP와 Greedy 알고리즘의 차이는 뭘까?

 

이 전 시간에 다루었던 Minimal spannig tree, Dijkstra모두 Greedy 알고리즘이고 Bellman ford만 DP 알고리즘을 이용해서 풀었다.

Greedy 알고리즘이 Optimal substructure가 있으면 DP라고 볼 수 있다. Greedy 알고리즘은 optiaml solution 같은 거 찾지 않고 그냥 현 시점에서 최고 좋은 선택만 이어간다.

 

그리고 DP의 경우 Local에서 선택한 최적의 choice가 globally하게도 최적의 선택이다.

Greedy는 위의 경우를 보장하지 않는다. 현 시점에서 최고만 따지지, 미래까지 생각해서 따지질 않는 다는 것

 

DP -> 예제, Longest Common Subsequence, Knapsack Problem, Optimal binary Search Tree 등 관련 문제가 많다.

DP 는 Optimal Substructure!(n 번째에쇠 최적화 하는 것) Overlapping subproblem!(n+1 번째 구할 때 n번째까지 구한 것이 overlap 되어서 사용되는지?) 이 두 개가 꼭 필요하니 기억하자.

 

흠.. 그냥 Recursive로 문제를 푸는데, subproblem에서 푼 것들을 따로 memoization을 하면 Top-down DP이고,

Recursive하게 안 푸는 데 위와 같이 memoization을 쓰면 Bottom-up DP라고 생각해도 된다!

 

 

- E. O. D -