[종만북] 문제: GENIUS
문제
곡의 수 $n(1 \leq n \leq 50)$, 실행시간(분) $k(1 \leq k \leq 1000000)$, 좋아하는 곡 개수 $m(1 \leq m \leq 10)$
각 곡의 길이 $Length[0…n-1], Length_i(1 \leq Length_i \leq 4 , Length_i \text{는 정수})$
곡 재생이 끝난 후 다음 곡이 재생 될 확률 $Transition[0…n-1][0…n-1]$이 주어집니다.
좋아하는 곡의 번호들 $m$개가 주어지면 그 번호들이 $k$분 30초에 재생되고 있을 확률을 구하시오.
서론
선형 변환(linear transform) 형태의 점화식이 주어진다면, 행렬을 통해 빠르게 풀 수 있습니다.
이를 반복적 동적 계획법을 이용해 구현합니다.
알아둬야 할 것
선형 변환 형태의 점화식?
선형 변환 형태의 점화식은 재귀 관계를 선형 변환(행렬 곱셈)으로 표현한 것입니다.
일반적인 선형 점화식의 형태는 이렇습니다.
$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$
이 점화식을 선형 변환 형태로 변환하려면, 상태 벡터(State Vector)를 정의하고 이를 행렬과의 곱으로 표현해야 합니다. 이를 통해 점화식을 행렬 거듭제곱형태로 만들 수 있습니다.
상태 벡터와 변환 행렬 찾기
상태 벡터란, 점화식의 현재 상태를 표현하고, 다음 상태로 변환하기 위한 모든 필요한 정보를 포함하는 열 벡터입니다.
상태 벡터를 정의하는 절차를 피보나치 수열을 예시로 설명하겠습니다.
- 점화식을 확인합니다. $fib(n) = fib(n-1) + fib(n-2)$
- 점화식을 이용해 열 벡터 형태로 정의합니다.
$\mathbf{v}_{n+1}$ 또한 이렇게 정의할 수 있겠죠.
\[\mathbf{v}_{n+1} = \begin{pmatrix} fib(n+1) \\ fib(n) \end{pmatrix}\]이후에 변환 행렬 $A$를 찾습니다. 변환 행렬 $A$는 다음 조건을 만족합니다. $\mathbf{v}_{n+1} = A \cdot \mathbf{v}_n$
\[\mathbf{v}_{n+1} = \begin{pmatrix} fib(n) + fib(n-1) \\ fib(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \mathbf{v}_n\]$\mathbf{v}_{n}$을 다음과 같이 쓸 수 있습니다.
\[\mathbf{v}_{n} = A^{n-1} \cdot \mathbf{v}_{1}\]무슨 효과를 얻을 수 있는가?
$m \times m$ 크기 행렬 $A^{n-1}$를 구하는 시간 복잡도는 $O(m^3 log n)$입니다.
이 시간 복잡도가 나오는 이유는
- 행렬의 곱셈은 각 항목에 대해 $m$개의 곱셈과 $m-1$개의 덧셈을 해야합니다. 따라서 연산하는 $O(m)$시간이 걸립니다.
- 각 항목은 $m^2$개입니다. 따라서 행렬을 곱하는 시간은 $O(m^3)$시간입니다.
- $A^n = (A^{n/2}) \cdot (A^{n/2})$이므로, 분할정복을 이용해 거듭제곱을 행렬을 곱하는 총 횟수를 $\log n$번으로 줄입니다.
따라서 최종 행렬을 연산하는 시간 복잡도는 $O(m^3 log n)$입니다.
일반적인 Dynamic Programming을 사용한다면, $O(nm)$개의 값을 각각 $O(m)$시간이 걸려서 계산해 $O(nm^2)$이 걸립니다.
$m$이 아주 작고, $n$이 아주 클 경우(ex: 피보나치 수열)같은 한정적인 상황에 적용해 알고리즘을 개선시킬 수 있습니다.
알고리즘 구상
마르코프 연쇄 문제
이 문제는 $Transition[0…n][0…n-1]$상태 간 전이 확률이 현재에만 의존한다고 볼 수 있습니다.
또한, 상태와 전이 확률의 명확한 정의가 필요한데, 이 문제에서는 상태는 플레이하고 있는 곡이라고 볼 수 있고, 전이 확률은 2차원 배열로 주어집니다.
따라서 마르코프 연쇄를 적용해서 문제를 풀 수 있습니다.
Subproblem의 정의 & 점화식 & 의존성
$start(time, song) =$ 재생을 시작한지, $time$분 30초에 $song$번 노래가 재생할 확률
$start(time, song) = \sum_{0 \leq prev \leq n-1}(start(time-length[prev], prev) \cdot Transition[prev][song])$로 표현가능합니다.
$start(time, song)$는 $start(time-length[prev], prev)$에 의존합니다.
여기서 $length_i$는 1부터 4까지의 자연수이므로 반복적 동적 계획법을 이용해 공간 복잡도를 줄일 수 있습니다.
행렬 거듭제곱 형태로 표현
Subproblem의 의존성을 이용해 점화식을 상태 벡터(열 벡터)로 나타내봅시다.
\[\mathbf{v}_{t} = \begin{bmatrix} \mathbf{Start}(t-3) \\ \mathbf{Start}(t-2) \\ \mathbf{Start}(t-1) \\ \mathbf{Start}(t) \end{bmatrix} = \begin{bmatrix} \text{start}(\text{time} - 3, 0) \\ \vdots \\ \text{start}(\text{time} - 3, n-1) \\ \text{start}(\text{time} - 2, 0) \\ \vdots \\ \text{start}(\text{time} - 2, n-1) \\ \text{start}(\text{time} - 1, 0) \\ \vdots \\ \text{start}(\text{time} - 1, n-1) \\ \text{start}(\text{time}, 0) \\ \vdots \\ \text{start}(\text{time}, n-1) \end{bmatrix}\] \[\mathbf{Start}(t) = \begin{bmatrix} \text{start}(\text{time}, 0) \\ \text{start}(\text{time}, 1) \\ \vdots \\ \text{start}(\text{time}, n-1) \end{bmatrix}\]로 볼 수 있습니다.
$\mathbf{v}_{time}$은 정답을 구하기 위해 필요한 계산 값입니다.
\(\mathbf{v}_{time+1} = A \cdot \mathbf{v}_{time}\) 이므로,
\(\mathbf{v}_{time} = A^{time} \cdot \mathbf{v}_{0}\) 를 만들 수 있습니다.
변환 행렬 $A$는 다음과 같습니다.
\[A = \begin{bmatrix} 0 & I_n & 0 & 0 \\ 0 & 0 & I_n & 0 \\ 0 & 0 & 0 & I_n \\ S_4 & S_3 & S_2 & S_1 \end{bmatrix}\] \[S_i = \bigl[s_i(j, k)\bigr]_{j, k = 0}^{n-1} \quad (n \times n \text{ 행렬}),\] \[s_i(j, k) = \begin{cases} \text{Transition}[k][j], & \text{if } length[k] = i, \\ 0, & \text{otherwise}. \end{cases}\]알고리즘 구현
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<double> function3() {
SquareMatrix W(4 * n);
for (int i = 0; i < 3 * n; i++) {
W[i][i + n] = 1.0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
W[3 * n + i][(4 - length[j]) * n + j] = next_song[j][i];
}
}
SquareMatrix Wk = W.pow(k);
vector<double> ret(n);
for (int song = 0; song < n; song++) {
for (int start = 0; start < length[song]; start++) {
ret[song] += Wk[(3 - start) * n + song][3 * n + 0];
}
}
return ret;
}
위에서 구한 행렬을 구현한 코드입니다.
1
2
3
4
5
6
7
8
for (int i = 0; i < 3 * n; i++) {
W[i][i + n] = 1.0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
W[3 * n + i][(4 - length[j]) * n + j] = next_song[j][i];
}
}
변환 행렬 $A$를 구하는 코드입니다.
1
2
3
4
5
6
vector<double> ret(n);
for (int song = 0; song < n; song++) {
for (int start = 0; start < length[song]; start++) {
ret[song] += Wk[(3 - start) * n + song][3 * n + 0];
}
}
암묵적으로 $\mathbf{v}_{0}$을 구하는 코드입니다.
최종 코드
여기에서 확인하세요!