Algorithm 8 - Dynamic Programming & Greedy Algorithm

 이전 rod cutting의 dynamic programming에서는 최종 결과만 알 수 있고, 어디를 잘라야 하는지는 알 수 없었다. 따라서 q를 선택할 때 해당 i 값을 또 다른 table에 저장하여 어디를 잘라야 하는지 까지 표현하도록 바꿀 수 있다.

Matrix - chain multiplication
여러 매트릭스를 연속으로 production 할 때 가장 효율적으로 할 수 있는 방법을 찾는 문제.(computational cost를 최소화)
 
A(p*q) x B(q*r) = C(p*r) 일 때, 계산에 필요한 scalar multiplication은 p*q*r 만큼 필요하다. (C의 한 원소를 계산하기 위해 p*q를 하고, 이를 r 번 반복하므로)

만약 매트릭스가 3개 이상 있다면, 이들의 계산 순서에 따라 필요한 multiplication의 수가 달라진다. (order of multiplication = parenthesization, fully parenthesized = 전체를 괄호로 구분)
결국 이들을 어떻게 괄호로 구분하여 계산순서를 결정하는 것이 문제가 된다.
앞서 merge sort와 동일하게 (물론 연관되어있다는 점에서 조금 다르지만) 어떤 문제 하나를 두 개의 sub problem으로 분리하고, 이들을 다시 합치는 cost를 고려하여 최소 값을 구하면 된다.

이를 계산해보면 time complexity는 O(n3)이 된다. total number of subproblem이 O(n2)가 되고, 각 subproblem에 대해 O(n)이 필요하다.
그리고 minimum과 split table을 저장하기 위해 O(n2)의 space complexity가 필요하다.

Longest common subsequence(LCS problem)
주어진 두 개의 sequence에 대해 같은 순서의 sub sequence가 여럿 존재하는데, 이 들 중 가장 긴 길이를 가지는 subsequence를 찾는 문제. 이 때 순서만 같으면 각 문자는 떨어져 있어도 된다. (ABDC, ADCD에서 ADC가 LCS이다. ) 이 문제는 DNA sequence 비교 과정에서 similarity를 측정하는 등에 사용될 수 있다.

이는 ith prefix로 각 sequence를 분해하여 sub problem으로 분리하고 dynamic programming 방법을 적용하는 것으로 해결할 수 있다.
이 때 두 input sequence(X, Y)에서 가장 뒤의 공통된 문자부터 확인하여 LCS(Z)에 포함시킬 수 있다. 그러면 해당 공통된 가장 긴 문자를 제외하고, 남은 것들을 또 확인하는 문제로 변환될 수 있다. (한 단계 낮춰짐. 이는 compiler에서 LRparsing으로 뒤에서부터 읽어서 해석하는 것과 비슷하다.)
만약 맨 마지막 문자가 같지 않다면 각 sequence를 하나씩 줄여나가면서 (m, n)을 (m-1, n)과 (m, n-1)의 sub problem으로 분해하여 나타낼 수 있다.

따라서 종합하면 (m, n)의 두 input sequence에 대해 (m-1, n-1) / (m-1, n) / (m, n-1) 의 sub problem 3개로 분해할 수 있다.
따라서 case를 분해하여 만약 첫번째 케이스라면 해당 문제의 길이에 +1을, 만약 2, 3번째라면 둘 중의 max 값을 반환하면 LCS를 찾을 수 있게 된다.

이 방법을 사용하면 time complexity는 O(mn)가 되며 (for문 두개가 각각 input sequence길이만큼 반복되어 m*n table 형성) space complexity도 O(mn)이 된다. (저장 table)

rod cutting, MCM, LCS 는 각각 분해되는 문제 개수가 다르다. (1개, 2개, 조건따라 1 또는 2개)
종합하면, 우리가 dynamic programming을 선택하는 조건에는 problem이 optimal substructure(작은 것들의 최적을 합칠 때 큰 문제에서도 최적이 되는 것)를 가지며 overlapping subproblem(recursive로 같은 problem을 반복적으로 연산하는 경우)으로 구성되어야 한다.
optimal substructure이 아닌 경우로는 longest simple path가 예가 되며 이는 노드 수가 늘어난다고 이전의 경로를 합쳐 솔루션을 만들고 이를 따라가면 더 안좋은 결과가 나온다. (노드 수에 따라 최적 경로를 설정하는 방법이 달라진다)

overlapping의 특성상 같은 문제들이 반복되므로 input size가 그리 크지 않아야 하고 한 번 연산한 결과를 반복적으로 사용할 수 있어야 한다. 예를 들어 merge sort의 경우 비슷하게 생각되지만, 각 sub problem을 sort하는 과정은 매번 새로운 값이므로 저장했다가 반복적으로 사용할 수 없다. (overlapping 불가)

dynamic programming의 time complexity를 계산하기 위해서는 subproblem의 개수와 각 subproblem의 choice 개수를 곱하여 계산할 수 있다. 

Greedy Algorithm
Dynamic programming은 subproblem을 모두 해결하여 최적의 결과를 도출해낸다. 그러나 모든 subproblem을 해결하는 것은 optimization problem에서 필요하지 않은 경우도 많다. (unnecessary - overkill) 이를 해결하는 방법이 greedy approach이다. 지금 현재의 상태를 보고, 가장 최적인 선택을 내리는 것이 이 방법이다. locally optimal choice를 내리고, 이 선택들이 global optimal로 이어지기를 바라는 것이다. 반드시 이런 최적 결과를 낼 수 있는 것은 아니지만, 대부분의 최적화 문제는 이 방법으로 해결가능하다. 따라서 subproblem을 풀기 전에 choice를 먼저 내린다는 점이 DP랑 가장 큰 차이점이다.

activity selection problem : 빈 강의실에 강의들을 겹치지 않게 배정하는 문제 형식. 각 강의의 길이가 겹치지 않으면서 가장 많은 강의를 배정해야 한다. 앞서 여러 문제들을 해결한 것 처럼 dynamic programming을 이용하여 이를 해결할 수도 있지만 이것이 이 문제를 해결하는 최적의 방법은 아니다. 이를 이용하려면 table의 모든 경우의 수를 다 고려하기 때문에 필요 없는 것들까지 계산하게 되기 때문이다. (O(n3)의 지나치게 큰 time complexity를 가진다)

이를 해결하는 것이 Greedy algorithm을 이용한 approach이다. 가장 빠른 finish time을 가지는 강의를 하나씩 선택하면, 가장 많은 강의를 선택하여 배정할 수 있다. 주어진 상황에서 가장 이득인 선택을 내리는 것이다. 그리고 이 문제에 대해서는 greedy approach로 optimal solution을 얻을 수 있다. (왜냐하면 가장 빨리 끝나는 finish time을 가지는 강의는 어떤 optimal solution에는 포함되어 있을 것이기 때문)

이 방법은 time complexity가 O(n)으로 줄어든다. 단, activity들이 finish time의 order에 따라 sort 되어 있지 않다면 O(nlogn)이 필요하다.

greedy algorithm을 사용할 때는 어떤 subproblem에서 greedy choice을 선택했을 때 각 step의 subproblem이 하나로 줄어들고, 해당 상황에서 내린 greedy choice가 optimal solution에 포함된다는 보장이 있어야 한다. 이를 정리하면 아래와 같이 두 가지 key ingredient로 표현할 수 있다.

- Greedy-choice property : local optimal choice를 결합하여 global optimal solution으로 도달할 수 있어야 한다.
- Optimal substructure : dynamic programming에서와 동일하게, subproblem에서 optimal solution을 내리고 이들을 결합하면, 전체 문제에서도 optimal solution을 얻을 수 있어야 한다는 것이다.

Greedy approach는 subproblem이 해결되기 전에 이들을 고려하지 않고 가장 좋아보이는 것을 선택한다. 따라서 매 스텝마다 하나의 subproblem만 생성되므로 implement 하는데 훨씬 빠르고 간단하다. 그리고 subproblem에 대한 solution을 재사용하지 않는다.
DP는 subproblem이 해결된 뒤에 선택을 하므로 전체 subproblem을 해결해야 최적의 선택을 내릴 수 있다. 그리고 매 단계마다 여러 개의 subproblem이 형성될 수 있기 때문에 구현하기 복잡하고 느리다. 그러나 subproblem에 대한 solution을 reuse 하기 때문에 효율적이고, global optimal에 반드시 도달할 수 있다.

따라서 문제에 따라 적절한 것을 선택하여 사용할 수 있어야 한다. 일반적으로 간단한 문제는 DP보다는 greedy를 사용하면 더 쉽게 해결할 수 있다.