쉽게 배우는 알고리즘 8장 요약

Chapter. 8 동적 프로그래밍

1. 어떤 문제를 동적 프로그래밍으로 푸는가

동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 말한다.

다음의 두 성질을 갖고 있는 문제에 대해 동적 프로그래밍이 적합하다.

a. 최적 부분구조를 이룬다.
b. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.

2. 행렬 경로 문제
nxn행렬의 죄상단에서 시작해 한 칸씩 이동해 우하단까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동상의 규칙은 아래와 같다.
- 오른쪽이나 아래쪽으로만 이동할 수 있다.
- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.

c(i,j)를 원소 (i,j)에 이르는 최고점수라하고, m(i,j)는 행렬의 원소(i,j)의 값이라 하면 아래와 같이 문제를 해결할 수 있다.
c(i,j) = m(1,1) if i=j=1
         m(1,j) + c(1,j-1) if i=1, j>1
         m(i,1) + c(i-1,1) if i>1, j=1
         m(i,j) + max(c(i,j-1), c(i-1,j)) if i>1, j>1

3. 조약돌 놓기 문제
3xn 테이블의 각 칸에 숫자가 쓰여 있다. 테이블의 칸들 중 일부에 제한조건을 만족하는 방법으로 조약돌을 놓아 조약돌이 놓인 곳에 있는 수의 합을 최대로 하는 방법을 구하는 문제이다. 제한 조건은 다음과 같다.
- 가로나 세로로 인접한 두 칸에 동시에 조약돌이 놓일 수 없다.
- 각 열에는 하나 이상의 조약돌을 놓는다.

임의의 열에 조약돌을 놓을 수 있는 방법은 총 4가지다 -> 패턴에 대한 내용은 책 확인
이를 기준으로 아래와 같이 문제를 해결할 수 있다.

c(i,p): i열이 패턴p로 놓일 때의 최고 점수
w(ip): i열이 패턴p로 놓일 때 i열에 돌이 놓인 곳의 점수 합
c(i,p) = w(i,p) if i=1
         max(c(i-1,q)) + w(i,p) if i>1, q는 p와 양립하는 패턴

4. 행렬 곱셈 순서 문제
n개의 행렬이 주어지고 이들의 곱을 계산하려 한다. 행렬은 결합법칙이 성립하므로 어떤 순서로 두개씩 짝지어 계산해도 결과는 동일하다.

c(i,j): 행렬 A(i), ..., A(j)의 곱  A(i), ... A(j)를 계산하는 최소 비용
A(i): p(i-1)Xp(i) 행렬

c(i,j) = 0 if i=j
         min(c(i,k) + c(k+1,j) + p(i-1)p(k)p(j)) if i<j, i<=k<=j-1

5. 최장 공통 부분순서(LCS)
두 문자열 X(m)과 Y(n)에 대해 두 문자열에 공통적으로 존재하는 가장 긴 부분순서를 구한다.

c(i,j)를 문자열 X(i)와 Y(i)의 LCS의 길이라 하면 점화식은 다음과 같다.
c(i,j) = 0 if i=0, j=0
         c(i-1,j-1) + 1 if i,j>0 and x(i)=y(j)
         max(c(i-1,j),c(i,j-1)) if i,j>0 and x(i)!=y(j)