행렬을 이용한 접근

행렬 곱셈을 통한 경우의 수 구하기

이런 문제를 생각해보자.

인접한 문자의 쌍(즉 연속한 두 문자)으로 가능한 것들이 주어질 때, 길이 L의 모든 가능한 문자열의 가짓수를 구하여라.

즉 c->a, a->t는 되고, a->n은 안 될 때, cat은 '가능한 문자열'이나 'can'은 '가능한 문자열'이 아니다.

이런 점화식을 세워볼 수 있다. (adj의 인덱스 순서는 행렬의 인덱스와 맞추느라, 직관적인 순서와는 반대일 수 있다.)

 
AخA
dp[i][k] = sum(dp[i-1][l]) for all l that adj[k][l]

이 때 답은 sum(dp[L][k]) for all k일 것이다.

그런데 k는 얼마 되지 않는데 L이 매우 커서 DP를 단순히 진행할 수는 없다고 하자.

이 때, dp[n]을 하나의 열벡터 $$v_{n}$$ 으로 생각하고, $$M_{ij}=adj[i][j]$$ 인 정사각행렬 $$M$$ 을 생각할 수 있다. 그러면 잘 생각해보면 점화식에 의해, $$M \cdot v_{n}=v_{n+1}$$ 이다. 그러면 $$v_{1}=\begin{pmatrix} 1 \\ 1\\ \vdots \\ 1\end{pmatrix}$$ 일 때, $$M^{n-1}v_{1} = v_{n}$$ 일 것이다.

어차피 $M^{n-1}$을 계산하는 시간이 오래 걸릴텐데 이게 무슨 의미가 있나 생각할 수도 있다. 하지만 행렬의 곱셈은 결합법칙이 성립하므로, 다음 식

$M^{2k} = (M^{k})^{2},\quad M^{2k+1}=M^{2k} \cdot M$

에 의해서 $$O(\log n)$$ 의 시간복잡도에 $$M^{n-1}$$ 을 계산할 수 있다. 이를 이용하면 답도 구할 수 있다.

최댓값에의 응용

그런데 위의 경우에는 경우의 수를 구하는 연산이었다. 경우의 수는 모두 합하는 것이고 이는 행렬의 연산과 작동 원리가 같다. 행렬을 사용할 수 있는 것은 그때문이다.

그럼 이 문제를 생각해보자.

인접한 문자의 쌍(즉 연속한 두 문자)마다 점수가 주어질 때, 길이 L인 문자열 중 점수가 가장 높은 것은 얼마인가?

aa는 얼마, xy는 얼마, zq는 얼마, 이런 식으로 주어진다는 뜻이다. 사실 방향그래프의 성질을 잘 이용해서 풀 수도 있을 수도 있겠지만 DP로 풀어보자.

이런 점화식을 세워볼 수 있다. (adj의 인덱스 순서는 행렬의 인덱스와 맞추느라, 직관적인 순서와는 반대일 수 있다.)

 
xxxxxxxxxx
dp[i][k] = max(dp[i-1][l] + adj[k][l]) for all l

이것도 역시 위와 같이 행렬을 쓰...고 싶지만, 연산의 종류가 바뀌어있다.

행렬에서 곱셈( $$M_{ij} \cdot v_{j}$$ 시의 곱셈) 자리에 덧셈, 덧셈($\sum_{j} M_{ij}v_{j}$ 시의 $\sum$) 자리에 max가 들어가있기 때문에, 일반적인 행렬 연산과는 달라 보인다.

그런데, 그냥 눈 딱 감고 행렬의 원소의 연산을 다음과 같이 재정의하자.

• 원래의 덧셈 대신 max 사용
• 원래의 곱셈 대신 덧셈 사용
• 원래의 0 (덧셈의 항등원) 대신 $$-\infty$$ 사용. 즉, 어떤 수를 안 쓰고 싶은 경우에 넣자.

그러면 위와 똑같이 일단 이렇게 쓸 수는 있다.

$M \cdot v_{n}=v_{n+1}$이고, $v_{1}=\begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix}$ 일 때 $M^{n-1}v_{1} = v_{n}$.

그럼 여기서 뭐가 문제인가? 경우의 수를 구할 때의 흐름을 찬찬히 따라가보면 한 가지 차이가 있다.

결합법칙이 보장되었는가?

결합법칙이 성립해야 $M^{n-1}$을 빠르게 구할 수 있기 때문이다.

이런 흐름이 늘 그렇듯, 결론은 성립한다. 성립하는지의 여부는 행렬의 $(i, \, j)$ 위치의 원소를 식으로 써보면 쉽게 증명할 수 있다.

이렇게 하는 것을 max-plus algebra라고 한다.

행렬의 응용

행렬으로 접근할 수 있는 다른 예시가 있다. 문제.

일단 간단한 DP를 생각해보자.

 
xxxxxxxxxx
dp[i][k] = 값이 i이고 마지막 글자가 k인 단어의 갯수

i의 차원의 최대 길이가 N이기 때문에 단순히 배열을 사용하는 건 불가능해보인다. 점화식을 세워보자.

 
xxxxxxxxxx
dp[i][k] = sum(dp[i-D[a][k]][a]) for all a

음... D[][]의 범위 때문에 dp[i]가 dp[i-1]부터 dp[i-5]까지 참조가 가능한 것 같다. 만약에 dp[i]가 dp[i-1]만 참조한다면, 위와 같은 행렬 곱셈으로 처리할 수 있다. 그런데, 원래 문제에서는 dp[i-1]부터 dp[i-5]까지 참조해야 한다.

또다시 난관처럼 보이지만, 이건 좀 더 머리를 써서 풀 수 있다.

지금 우리가 이 문제에 접근할 수 있는 방법은 행렬을 통한 접근 뿐이다. 그렇다면... 이들을 다 하나의 행렬과 하나의 열벡터에 넣어서 쓸 수는 없을까?

이건 어떨까?

$v_{i} = \begin{pmatrix} dp[i-4][0] \\ \vdots \\ dp[i-4][25] \\ dp[i-3][0] \\ \vdots \\ dp[i-3][25] \\ \vdots \\ dp[i][25] \end{pmatrix}$

하나의 열벡터가 담고 있는 정보가 굉장히 커졌다는 생각이 들지만, 총 $26 \times 5 = 130$개 뿐이므로, $O(N^{3})$의 행렬 곱셈 정도는 충분하다.

그러면 이 행렬의 점화식 행렬은? 위의 점화식을 잘 만져보면 이런 결론이 난다.

$M = \begin{pmatrix} 0 \quad I_{104} \\ D \end{pmatrix}$

$I$는 항등 행렬이고, $D$의 자리는 문제에서 주어진 D를 이용해서 잘 처리할 수 있다.

아니, 그런데 자세히 보니 이 문제는 $v_{n}$을 구하는 문제가 아니다. $\sum_{i=1}^{n} (dp[i][0] + \cdots + dp[i][25] )$ 를 구해야 한다. 문제가 갑자기 너무 어려워졌다고 생각할 수 있겠지만, 한 번 더 힘써보자.

$v_{i} = \begin{pmatrix} dp[i-4][0] \\ \vdots \\ dp[i-4][25] \\ dp[i-3][0] \\ \vdots \\ dp[i-3][25] \\ \vdots \\ dp[i][25] \\ \sum_{j=1}^{n-1}(dp[j][0]+\cdots+dp[j][25]) \end{pmatrix}$

즉 마지막 항에 그냥 원하는 값을 넣어버렸다. (행렬을 세우다 보면 왜 $n-1$을 쓰게 되었는지 알 수 있다.) 머리를 좀 써보면 점화식을 만족하도록 $M$ 행렬을 조금 더 바꿔주면 될 것이다.