알고리즘 이론 15강. 동적 프로그래밍(Dynamic Programming)

아직 최적화가 덜된 게시글입니다.

[동적 프로그래밍의 특징]

: 주어진 조건에서 최적의 값(최솟값 or 최댓값)을 찾는 작업을 위해 설계된 알고리즘.

: 분할 정복 알고리즘의 비효율성(동일한 재귀호출 생성)을 개선한 알고리즘

  - 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결.

  - 분할정복 기법과 달리 부분 문제들이 독립적이지 않다.

: 다음과 같은 방법으로 계산량을 줄인다.

  - 부분 문제를 바텀-업 방식으로 해결

  - 부분 문제의 해결값을 처음에 해결시에 저장

  - 동일한 부분 문제가 재발생시, 저장해놓은 해결값을 본다

: 부분문제을 한번만 해결한 후 테이블에 저장해놔 미래의 사용에 대비한다.

 

 

 

[DP로 해결하는 문제들 특징]

: DP는 다음과 같은 특징을 가지고 있는 문제들을 해결되는데 사용된다.

  - 간단한 부분 문제 : 원본 문제를 같은 형태의 더 작은 부분문제로 쪼갤수 있어야한다.

  - 문제의 최적 부분구조 : 문제의 최적 해결방법이 해당 문제의 부분문제의 최적 해결방법에 포함된다.

  - 중복된 부분 문제 : 동일한 부분 문제를 풀어야 하는 시점이 존재한다.

 

 

 

[동적 프로그래밍 알고리즘 개발 순서]

: 동적 프로그래밍 알고리즘 개발시에 4단계를 따른다.

1. 최적해의 구조의 특징을 찾는다

2. 최적해의 값을 재귀적으로 정의한다

3. 최적해의 값을 일반적으로 상향식(바텀-업) 방법으로 계산한다

4. 계산된 정보들로부터 최적해룰 구성한다 (선택)

 

 

 

[동적 프로그래밍 예시1 - 피보나치 수열]

# 재귀를 이용해 피보나치 수열을 해결하는 방법 : 분할정복, 너무 느리다..

# DP를 이용해 피보나치 수열을 해결하는 방법

Fibo(n):   f0 = 0   f1 = 1   for i <- 2 to n do     fi = fi-1 + fi-2

: 바텀 업 방식, 이미 푼 부분 문제의 결과를 기억하는 방식으로 O(n) 선형시간만에 해결 = DP

[동적 프로그래밍 예시2 - 조립 라인 스케쥴링(Assembly Line Scheduling)]

- 자동화 공장이 두 조립 라인을 가지고 있는 상태

조립 라인 스케쥴링 개요도

( S : 각 라인이 가지고 있는 역번호 / e : 입장 시간 / x : 퇴장 시간 )

( t : 다른 라인으로 이동하는 시간)

 

Q. 

이때 한 대의 자동차를 위한 공정 총 시간을 최소화하기위해 조립라인 1, 2에서 어떤 역번호를 선택해야 하는가?

 

A. 

Solution 1. 브루트 포스

: 모든 가능한 경우의 수를 계산해보는 방식

브루트 포스 방식

: n번째 S에서 라인 1을 선택하면 '1', 라인 2를 선택하면 '0'을 넣어 모든 가능한 경우에 대해서 계산

: O(2^n). n값이 클수록 기하급수적으로 시간복잡도 증가..

 

 

Solution2. 다이나믹 프로그래밍

step1) 최적해의 구조를 파악(공장을 통과하는 가장 빠른 경로의 구조)

  : 우선 특정 역 (S1,j)으로 갈 수있는 모든 가능한 방법을 고려해본다.

  # j = 1일때, 한가지 경로밖에 없다.

  # j = 2, 3 ... 일때, 두가지 선택의 경우가 생기게 된다.

  1) 역 (S1,j-1) 까지 가장 빠르게 온후 곧바로 역 (S1,j)로 오는 방법

  2) 역 (S2,j-1) 까지 가장 빠르게 온후 라인 2에서 1로 옮겨서 역 (S1,j)로 오는 방법

  => 이중 더 빠른 경로를 선택해야 한다.

 

  : 이제 각각의 부분문제에 대한 최적해를 만들어나가며 재귀적인 방법을 이용해 전체에 대한 최적해를 구할 수 있다.

step2) 재귀적인 풀이법

  : 위에서 본 부분 문제에 대한 최적해를 구하는 방식을 전체 조립라인에 대한 재귀 함수로 만든다.

 f* : 전체 공정에서의 최소시간 / fi[j] : 시작지점에서 Si,j까지 가는 최소 시간

# 베이스 케이스

  : 역 (S1,1)과 역 (S2,1)로 가는 경로는 각각 한가지 밖에 없다

  - S1,1 까지 가는 경로 = 라인1 입장 비용 + S1,1에서 출발비용

  - S2,1 까지 가는 경로 = 라인2 입장 비용 + S2,1에서 출발비용

 

# 일반적인 케이스 (j =2,3,...n and i = 1, 2)

ex) S 1,2 까지 가는 경로 = min (라인1 입장 비용 + S 1,1에서 출발비용 + S 1,2에서 출발비용 or (라인2 입장비용 + S 2,1에서 출발비용 + 라인바꾸는비용(2->1) + S 1,2에서출발비용) = min ( S1,1에서출발까지의비용 + S1,2에서 출발비용 or S2,1에서출발까지의비용 + t비용(라인바꾸는비용2->1)+ S1,2에서 출발비용)

=> 일반화되면 다음과 같은 식이 나온다. (t : 라인 이동 비용)

라인1의 역에 도달하는 최소식에 대한 재귀식

결론적으로 얻게되는 재귀적 식

 

step3) 가장 빠른 시간 계산하기

: 위의 재귀적인 계산법 그대로 사용은 비효율(재귀의 문제) = 탑다운 방식

: 탑다운 방식을 바텀업 방식으로 바꾸어주는 과정

기존 재귀 방식 풀이

: 2이상의 j에서, 각fi[j]는  f1[j-1]과 f2[j-1]의 값들에만 의존적임을 알수 있다.

: 이 사실을 이용해 j값이 증가하는 방식으로 fi[j]값을 계산하는 방식을 유도해볼 수 있다.

주어진 문제에 따른 fi[j] 각 비용

ex) f2[3] : 22 ( S 2,3갈수 있는 방법들중, 2 + 7 + 2 + 5 + 6(기본값) 의 방법이 최선의 방법)

 

: 이러한 사실을 이용해 식 만들수 있다. (O(n))

# FASTEST-WAY(a,t,e,x,n) 생략.

 

step4) 최적 해결책 구조

: 최적 해결책에 해당되는 경로의 Station 번호들 출력하는 코드

PRINT-STATIONS(l,n)   i = l*   print("line", i, "station", n)   for j <- n downto 2     do i <- li[j]     print("line", i, "station", j-1)

# 출력 결과 line 1, station 6 line 2, station 5 line 2, station 4 line 1 station 3 line 2, station 2 line 1, station 1

 

[동적 프로그래밍 예시3 - 행렬 체인 곱(Matrix-Multiplication)]

: 행렬 곱 문제를 해결하는 알고리즘 (이러한 행렬의 곱은 서로 호환성이 있어야만 가능하다, 교환법칙 성립 X)

 

# 일반적인 행렬의 곱셈 문제와 일반적인 해결법

MATRIX-MULTIPLY(A,B)   if columns[A] != rows[B]     then error "incompatible dimensions"     else for i <- 1 to rows[A]             do for j <- 1 to columns[B]                    do C[i,j] <- 0   //C 초기화                        for k <- 1 to columns[A]                            do C[i,j] <- C[i,j] + A[i,k] * B[k.j]

 

 

# 여러개의 행렬의 곱

 : 행렬간에 괄호 붙여줘서 어떤 순서대로(교환법칙은 X) 곱연산 먼저 계산하냐에 따라 계산해야하는 횟수의 양이 기하급수적으로 바뀐다

A1*A2*A3 일때, ((A1*A2)*A3) 과 (A1*(A2*A3))의 각 총 계산횟수가 다르다

: 그러면 행렬이 A1...An의 곱을 구할때, 가장 효율적인 괄호의 위치를 구해야 한다. 

 

 

 

# 행렬들의 곱연산의 단순한 풀이 - 브루노 포스

: 일일히 모든 가능한 괄호의 상황을 계산하는 방법 => 낮은 효율성 (Ω(4^n / n^(3/2)))

 

 

# 행렬 곱연산의 효율적인 풀이

step1) 최적괄호 묶기의 구조

  : 여러개의 행렬들의 곱연산 Ai * A(i+1) * ... Aj 라 가정할때, 이 행렬의 곱의 횟수가 최소화 되는 지점 k가 존재한다 가정

A(i...j) = A(i...k) * A(k+1...j)       // i<= k < j

: 이때 A(i...k)와 A(k+1...j)또한 최적 괄호 묶기 방법이여야 한다 ( 아니면 모순발생.. 더 적은 비용 가지는 괄호묶기 존재해버림)

 

step2) 재귀적 해

: 위에서 본것처럼 부분 행렬 곱들에 대해서도 최적 괄호 묶기가 성립 되어야 한다.

# 점화식 도출 (m[i,j] = A(i...j)를 계산하기 위한 곱 횟수)

전체적 문제 : A(i...n) : m[1,n] 부분 문제 : A(i...k) * A(k+1...j) : m[i,k] + m[k+1,j] + p(i-1)*p(k)*p(j)    // p(i-1)*p(k)*p(j)  : 각 행렬 Ai가 p(i-1)*pi 일때, 이 식을 계산하기 위해 필요한 곱의 횟수

# 재귀식 도출

행렬곱연산의 재귀식

 

step3) 최적 비용 계산

: 지금까지 최소비용 m[1,n]을 계산하기 위한 점화식을 이용해 재귀적 알고리즘을 만들었다.

: 하지만 여기의 부분문제들을 보면 서로 독립적인 부분 문제들이 매우 적은 것을 알수 있다. (각 i, j에 대해 O(n^2)의 부분문제 개수)

=> 이러한 중복되는 부분문제는 동적 프로그래밍의 적용을 보증하는 특징중 하나이다.(탑다운 방식)

: 이제 이러한 식을 상향식(바텀업 방식)과 테이블을 사용해 최적의 비용을 계산하려 한다.

 

# 과정.. 생략... ㅂㄷ

 

# 바텀업 방식위해 i,j = 2,5일때 최적해 찾는 방법 예시

m[2,5] = min ( m[2,2] + m[3,5] + p1p2p5        k = 2일때                     m[2,3] + m[4,5] + p1p3p5        k = 3일때                     m[2,4] + m[5,5] + p1p4p5        k = 4일때

: m[i,j]은 오직 이전 계산 결과에만 의존한다는 것을 알 수 있다. (이 결과를 일반화에서 아래 식 도출)

 

# 바텀업 방식으로 작성한 식

MATRIX-CHAIN-ORDER(p)      // 생략. O(n^3)의 수행시간 필요 (효율)

 

step4) 최적해 구성하기

: 위 바텀업 방식의 함수는 행렬 곱 계산하는데 필요한 곱의 최적 수를 결정하지만, 어떻게 곱해야하는지를 직접적으로 안보여준다.

 

# 생략... ㅂㄷ

 

# 최적 괄호 묶는 방법 출력 함수

PRINT-OPTIMAL-PARENS(s,i,j) if i == j   then "A"ㅑ   else print "("         PRINT-OPTIMAL-PARENS(s,i,s[i,j])         PRINT-OPTIMAL-PARENS(s,s[i,j]+1, j)         print ")"

 

# 행렬들간의 곱 요약 정리

  : DP와 메모화 방법으로 이 문제를 O(n^3) 시간에 해결할 수 있다.

  : 두 방법다 중복되는 부분집합에 대해서 장점을 가진다.

  : 실제로는 Θ(n^2)의 서로다른 부분문제만 존재한다. (한번만 계산하게 끔 하는 풀이가 최종 풀이)

  : 메모화 없이 재귀 알고리즘 사용은 시간 매우 많이 소비...

 

 

 

[Memoization(메모화)]

: 지금까지 본 동적 프로그래밍은 우선 탑-다운 방식(재귀)으로 해결한뒤 바텀-탑(반복)으로 개선하는 형태였다.

: 하지만 탑-다운 방식을 유지하며 동적 프로그래밍 방식을 유지 하는 방법이 있는데 바로 memorizaion 방법이다.

: 부분문제가 처음으로 해결되면 그 해결값을 테이블의 해당 위치에 저장해둔다.

: 이후 동일한 부분문제가 실행되면 저장되어있는 부분문제를 호출하는 개념.

# 예제 코드 생략

  : 그냥 나올수 있는 모든 범위만큼의 배열을 만든뒤, 부분문제의 index에 해당되는 위치에 저장.

  : 그이전에 해당 배열의 위치의 값을 확인해보고 비어있으면 부분문제를 해결하는 방식.

 

 

 

[동적 프로그래밍 Vs 메모화]

- 동적 프로그래밍의 장점

  : 재귀로 인한 오버헤드 없음

  : 시공간적 이득

- 메모화의 장점

  : 특정 부분문제들은 해결할 필요 없음

 

 

[중복되는 부분문제]

: 동적 프로그램을 적용하기 위해 최적화 문제가 가져야할 두번째 요소는 부분문제의 범위가 작아야 한다.

: 하지만 재귀 알고리즘을 사용하면 동일한 부분문제를 반복해서 풀게되고 이를 의미한다.

: 즉, 테이블을 만들어 처음 해결한 부분문제의 답을 저장해, 이후 동일한 부분문제 실행시, 테이블에서 해당 답을 호출한다.(메모화)

 

 

 

[동적 프로그래밍 예시4 - 최장 공통 부분 시퀀스]

: 생물체 DNA에서 공통되는 가장 긴 부분(부분 시퀀스)을 발견하는 문제

 

# 부분 시퀀스 : 시퀀스의 부분이지만, 연속적일 필요는 없다! 

시퀀스 : ABCDEFGHIJK 일때, 부분시퀀스 1 : ACEGIJK 부분시퀀스 2 : DFGHK 부분시퀀스 X : DAGH  (연속적일 필요는 없지만 순서는 유지되어야 한다)

 

# 브루노 포스 해결법 : Θ(n*2^m)의 시간 복잡도 ( n : 각 서브시퀀스 탐색 시간, 2^m : 서브시퀀스의 개수)

# 동적 프로그래밍 해결법(생략)

1. 최장 공통 부분 시퀀스 특성 파악하기   2. 재귀해   3. LCS 길이 계산   4. LCS 구성하기   5. 코드 항상 시키기