반복적 동적 계획법 (p. 349)

재귀 말고 반복문으로 DP 문제 풀기#

반복적 DP는 재귀적 DP에선 불가능한 2가지 장점이 있다. 하나는 슬라이딩 윈도우 기법을 쓸 수 있는 것이고, 다른 하나는 행렬의 거듭제곱 형태로 나타내어 N번째 항을 $O(logN)$번 연산으로 구할 수 있는 것이다.

1. 슬라이딩 윈도우#

이 기법을 사용하면, 상태공간의 수를 크게 줄일 수 있다.

TRIANGLEPATH (하, p. 226)

위 문제를 보면, $O(N^2)$의 시간/공간 복잡도를 갖는데, 반복문을 사용하게 되면 공간복잡도는 $O(2N)$으로 줄일 수 있다. x번째 가로줄을 계산하려면 x+1번째 가로줄 값만 필요하기 때문에 $N \times N$의 크기가 필요하지 않고, $2 \times N$이면 충분하다.

2. 행렬의 거듭제곱을 이용한 동적 계획법#

동적 계획법(DP)을 선형대수(Linear Algebra)로 재해석 하는 방법을 말하고, 핵심은 다음과 같다.

점화식이 ‘선형(Linear) + 고정 차수(constant order)’ 형태로 표현되는 경우

→ 행렬로 표현 가능.

→ 빠른 거듭제곱(분할정복)으로 $O(logN)$ 시간복잡도를 가짐.

1) 피보나치 수열을 행렬의 거듭제곱으로 나타낼 수 있는 이유#

$$ F_n = F_{n-1} + F_{n-2} $$

이 식이 왜 행렬로 되냐?

  • 선형(linear): 항들의 합으로 이루어짐
  • 고정 차수(constant order): 이전 2개 항만 필요 (고정된 k=2)

이것을 벡터로 만들면 아래와 같다.

$$ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix} $$

→ 이렇게 앞으로 계속 똑같은 행렬을 곱하는 형태가 나오면 승법으로 처리 가능

→ 따라서 제곱/거듭제곱으로 점화식을 해결 가능

“k차 선형 동차 점화식 (Linear Homogeneous Recurrence of order k)”

2) 어떤 점화식이 행렬로 변환 가능한가? (판별 기준)#

아래 3가지를 모두 만족하면 거의 대부분 가능

① 선형(linear)이어야 한다

즉, 항 사이의 관계가 덧셈과 상수배로 구성되면 OK

  • 가능

    dp[i] = 2*dp[i-1] + 3*dp[i-2];
dp[i] = dp[i-1] + dp[i-5];
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

  • 불가능

    dp[i] = dp[i-1]*dp[i-2];       // 곱셈
dp[i] = max(dp[i-1], dp[i-2]); // 비선형

② 차수(order)가 고정

항의 개수가 고정 k개여야 함

  • 가능

    dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k];

  • 불가능

    dp[i] = dp[i-1] + dp[i-2] + ... + dp[1]   // O(n) 항

    이러면 행렬 크기가 i마다 증가해서 “정적 행렬”로 만들 수 없음.

③ 계수가 상수(constant coefficient)

dp가 i에 따라 변하는 경우는 안됨.

  • 가능

    dp[i] = 3*dp[i-1] - 2*dp[i-2];

  • 불가능

    dp[i] = i * dp[i-1];  // 계수가 i에 따라 바뀜

3) 책에서 설명하는 피보나치 수열을 행렬의 거듭제곱식으로 표현하는 방법#

책에서 설명하고 있는 n번째 피보나치 수열을 구하는 방법을 행렬의 거듭제곱식으로 변환하는 과정을 나타내면 다음과 같다.

  • 피보나치 점화식을 적는다: $f(n) = f(n-1) + f(n-2)$

  • 이제 피보나치 점화식을 행렬을 이용한 점화식으로 바꿔본다.

    • i번째 행렬식을 만들고: $C_i = \begin{pmatrix} f(i-1) \\ f(i) \\ \end{pmatrix}$
    • i+1번째 행렬식을 만든 뒤: $C_{i+1} = \begin{pmatrix} f(i) \\ f(i+1) \\ \end{pmatrix} = \begin{pmatrix} f(i) \\ f(i)+f(i-1) \\ \end{pmatrix}$
    • $C_i$와 $C_{i+1}$간의 관계를 점화식으로 표현해보기: $C_{i+1} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} C_i$

    $\Rightarrow C_n = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix}^{n-1} C_1$

  • 이러면 이제 $\begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix}^{n-1}$ 은 분할정복으로 $O(log(n-1))$번만 제곱하면 구할 수 있고, $2 \times 2$ 행렬이므로 $O(4log(n-1) = O(logn)$ 시간이면 피보나치 수열의 $n$번째 항인 $f(n)$을 구할 수 있다.

4) 프로그래밍 문제에서 행렬화 가능한 대표 DP#

  • 피보나치
  • 합을 k개의 고정된 방법을 사용하여 구하기 (ex. 동전 1,3,4로 합 만들기, 주어진 k개의 조각으로 합 만들기)
  • 선형 DP(”다음 상태 = 고정 크기 행렬 * 이전 상태”)
Backward BLOCKGAME (중, p. 344) SUSHI (중, p. 355) Forward