[ 알고리즘 ] 4. Dynamic Programming

https://min-h-study-review.tistory.com/266

Dynamic Programming

알고리즘X

디자인 패러다임이다.

 

● 언제 사용되느냐?

  : Optimization 문제에서 사용된다.

 

ex) Minimization / Max..~

  → 최단 경로 찾기,Job scheduling 과 같이

       선택해야 하는 문제에 쓰인다. 

 

 

● 방법

하나의 큰 문제를 Dynamic한 여러 작은 문제로 나누어서 푼다.

S라는 큰 문제 하나를 S1,S2,S3...Sm으로 나눈 뒤, 그들을 합한다.

 

이러면 Divide and Conquer 랑 다를 게 없어보이는데, 

차이점으로는 DP는 가장 작은 케이스에서부터 시작한다는 것이다.

 

- 공통점 : 작은 문제를 통해 큰 결과를 구한다.

- 차이점 : 시작하는 곳이 위냐 밑이냐 

 

 

● Divide and Conquer 방식

1. n번 문제를 풀어야 한다.

   → n-1 , n-2 를 풀어야한다.

2-1). n-1번 문제를 풀어야 한다.

   → n-2 , n-3 를 풀어야한다.

 

2-2). n-2번 문제를 풀어야 한다.

   → n-3 , n-4 를 풀어야한다.

 

...이렇게 쭉 내려갔다가 그 값들을 합하면서 다시 올라온다.

= 출발은 Top이다.

 

---

● Dynamic Programming 방식

1. 0,1 (가장 아래(작은)케이스 ) 에서 시작한다.

2. 2의 값은 0,1을 더한 것 → 현재 계산한 2를 배열에 추가한다.

 

 

이렇게 하면, Recursion에서는 엄청 많이 불렸던 애들이 2번 넘게 불리는 일이 없다.

Recursion에는 DP처럼 하나의 값을 기억하고 저장하는 기능이 없다.

 

 

---

 

DP : Matrix - Chain Multiplication

 

 

행렬 A1 ,A2 ... An가 있을 때 이들의 곱을 구하려고 할 때

 

순서를 나누는 방법이 아주 많다.

행렬에서는 곱하기의 순서에 따라 결과가 달라질 수 있다.

이렇게 했을 때 곱셈을 수행하는 양은 p * q * r 이다.

 

 

● 풀이:

 

숫자를 넣어서 해보면 간단히 해결된다.

 

 

문제1)

답 보지말고 해보기

 

 

● n개의 행렬이 있을 때, 그것들을 곱하는 방법의 수

 

 

Pn = (P1 * Pn-1) + (P2 * Pn-2) + (P3 * Pn-3) ... + (Pn-1 * P1)

 

- 의미:  (A1을 두고, A2~An-1까지 곱하는 수) + (A1,A2를 곱하고, A3~An-1까지 곱하는 수) + ...

 

- 전개를 하여 성능을 분석해보자.

 

 

Pn = (P1 * Pn-1) + (P2 * Pn-2) + (P3 * Pn-3) ... + (Pn-1 * P1)
   = 양 끝 두 개를 가져오면 2(P1 + Pn-1)이 된다.
Pn >= 2(P1 * Pn-1)   << 1. 양 끝 이외에 추가되는 게 많으니 Pn이 더 크다.
                     << 2. P1 =1 이라고 정의되어 있으니 1로 바꾼다.

Pn >= 2*Pn-1

Pn >= 2*Pn-1 >= 2^2 * Pn-2 >= 2^3*Pn-3 ... >= 2^(n-1) p1 = 2^(n-1) 

So, Pn >= 2^(n-1)  = 1/2 2^n
Pn >= c 2^n
Pn >= 오메가 (2^n)

 

근데 이렇게 하면 너무 오래 걸린다.

최적화된 방법 하나만 찾아야 하는데, 그렇지 않은 방법들까지 다 들어갔다 오기 때문

 

예를 들어, 어느 길로 가야 빠른지 찾기 위해서 모든 길로 다 가보느라 시간을 다 쓰는 경우와 같다.

 

 

이런 방법으로 하면 Recalculation이 일어나는 경우가 많이 생긴다.

이와 같은 것들 때문에 오메가(2^n)만큼 시간이 많이 걸린다.

 

해결법은 Memorized Dynamic Programing이다.

 

A1부터 A5까지의 행렬곱셈에서 A1*(A2*A3) (A4*A5) 가 Optimal cost라고 할 때

A1,A2,A3 를 계산하는 방법은 2가지가 있지만, 그 중에서 A1 * (A2*A3)가 Optimal이라고 할 수 있다.

 

 

i~ j까지의 cost를 구할 때, i~k , k+1~j 구간을 나누고, 그것들을 합하는 계산을 한다고 했을 때,

cost[i,k] 보다 더 cost가 낮은 cost2 [i,k]가 나오면 cost [i,k] 는 optimal하지 않다고 할 수 있다.

 

반대로 현재 cost [i,j] 식이 Optimal하다면, 그 안에 구성하고있는 SubProblem 의 cost도 optimal하다고 할 수 있다.

 

'큰 Problem에 대한 Optimal Solution'은

그 Problem 이루고 있는 '작은 Problem들에 대한 Soulution도 Optimal하다' 할 수 있다.

 

 

 

Memorized Dynamic Programming을 사용하면

Top - down 식의 접근법도 가능하다!

 

 

(출처)

한동대학교 용환기교수님 - 알고리즘