DP optimization: Alien's trick
이 주제를 다루고 있는 문서가 몇 있지만, 개인적으로 이해하는데 애를 먹어서 정리해둔다. 내용의 전개는 구사과님 블로그와 같다.
다음과 같은 문제가 있다고 하자.
양의 정수로 이루어진 수열 $v[i]$ ($1\leq i \leq n$)을 연속된 항들을 포함하는 여러 개의 구간으로 나눈다. $i$ 번째 부터 $j$번째 항을 포함하는 구간의 비용이 $c[i][j]$ 라고 할 때 전체 수열을 $m$개의 구간으로 나누는 최소 비용은 얼마인가? (단, $c$는 monge array이며, 모든 $c[i][j]$는 정수이다.)
수열의 $j$번째 항 까지를 $i$개의 구간으로 나누는 최소 비용을 $dp[i][j]$ 으로 나타내자. 이때 점화식은 다음과 같다.
$$dp[i][j]=\min_{k<j}(dp[i-1][k]+c[k+1][j])$$
이 때 답은 $dp[m][n]$이다. Naive하게 구현할 경우 시간복잡도는 $O(mn^2)$이다. Alien's trick은 이러한 형태의 점화식을 $O(n^2\log X)$ 시간복잡도로 최적화하는 기법이다. 또한 monotone queue optimization이라는 또다른 최적화 기법을 통해 $O(n\log n\log X)$까지 최적화가 가능하다. 이 글에서는 alien's trick까지만 다루겠다.
Alien's trick
어떤 음이 아닌 실수 $\lambda$에 대해 다음과 같은 새로운 점화식을 생각해 보자.
$$
\begin{matrix}
dp_{\lambda}[i]=\min_{j<i}(dp_{\lambda}[j]+c[j+1][i]+\lambda) & dp_{\lambda}[0]=0
\end{matrix}
$$
위 식은 수열이 몇 개로 나눠지는지를 $\lambda$ 값을 통해 간접적으로 제어할 수 있다는 점에서 착안한 것이다.
$cnt[i]$를 $\lambda$에 따라 $v$의 1번째 항부터 $i$번째 항 까지가 몇 개의 구간으로 나눠지는지 나타내는 수열이라고 하자. $cnt[i]$는 다음과 같이 구할 수 있다.
$$
\begin{matrix}
cnt[i]=cnt[\arg\min_{j<i}(dp_{\lambda}[j]+c[j+1][i]+\lambda)]+1 & cnt[0]=0
\end{matrix}
$$
$\lambda$가 커지면 각 구간을 나눌 때 비용이 커지므로 $cnt[n]$은 작아진다. 반대로 $\lambda$가 작아지면, $cnt[n]$은 커진다. 따라서 $cnt[n]$은 $\lambda$에 대한 함수이다. 이 관계를 $h(\lambda)=cnt[n]$으로 나타내자. 한편 정의에 의해 원래 문제의 점화식 $dp$와 새로 정의한 $dp_{\lambda}$의 관계는
$$dp_{\lambda}[n]=dp[h(\lambda)][n]+\lambda h(\lambda)$$
임을 알 수 있다.
여기서 $f(i)=dp[i][n]$ (전체 수열을 $i$개의 구간으로 나눌 때의 최소비용)으로 정의하자.
$$dp_{\lambda}[n]=f(h(\lambda))+\lambda h(\lambda)$$
$c$가 monge array일 때 $f(i)$는 볼록하다는 사실을 증명할 수 있다. (증명은 구사과님 블로그에 있다.)
따라서 $f(i)+\lambda i$또한 볼록함수이다. 한편 정의역이 자연수(의 부분집합)인 볼록한 함수는 아래 그림처럼 부분 선형함수에서 정의역이 자연수(의 부분집합)인 것으로 생각할 수 있다. 이제 $m$이 어느 직선의 정의역에 포함되어 있는지를 찾으면 답을 구할 수 있다.
$O(n^2)$에 $dp_\lambda[n]=f(h(\lambda))+\lambda h(\lambda)$와 $h(\lambda)$를 계산할 수 있다.
$f(i)+\lambda i$는 각 선형함수의 기울기를 $\lambda$만큼 증가시킨 것이고, 이때 각 직선의 정의역은 변하지 않는다. 두 직선 $y=m_{1}x+b_{1}$, $y=m_{2}x+b_{2}$가 있을 때, 두 직선의 기울기를 $\lambda$만큼 증가시켜도 교점은 변하지 않기 때문이다.
$$\frac{b_2-b_1}{(m_1+\lambda)-(m_2+\lambda)}=\frac{b_2-b_1}{m_1-m_2}$$
따라서 $dp_\lambda[n]=f(h(\lambda))+\lambda h(\lambda)$을 구하면서 같이 계산한 $h(\lambda)$를 사용해서 $m$이 어느 직선에 포함되었는지를 판단해도 된다.
볼록함수의 성질을 유지하면서 $f(0)=f(n+1)=\infty$라고 하자. 그리고 왼쪽에서부터 $k$번째 선형함수를 $l_k=a_k i+b_k$, 정의역은 $s_k\leq i < e_k$이라고 하자. ($a_0=-\infty, a_{n+1}=\infty$)
실수 범위에서 $\lambda$를 탐색하는 것은 계산적으로 좋지 않다. 그렇다면 정수 범위에서 찾을 수 있을까?
$m$이 어느 직선의 정의역에 포함되었는지를 알기 위해서는 $h(\lambda^*)\leq m<h(\lambda^*-1)$인 정수 $\lambda^*$를 찾으면 된다.
$\lambda=-a_k$일 때 $k$번째 직선에 포함된 $i$값 중 하나가 $h(\lambda)$에 대응된다. 위 그림의 $3\leq i < 5$ 범위처럼 2개 이상의 $i$가 직선의 정의역에 포함되는 경우에 어떤 $i$값이 $h(\lambda)$에 대응될지 알 수 없기 때문에 정수 범위에서 $\lambda$를 탐색해서는 $\lambda^*$를 찾을 수 없다.
해결책은 $\lambda$를 $n+\frac{1}{2}$꼴의 반정수에서 탐색하는 것이다.
$\lambda=-a_k+\frac{1}{2}$일 때 $h(\lambda)=s_k$임을 알 수 있다. 따라서 $s_k\leq m <e_k=s_{k+1}$인 직선에 대해 $\lambda=-a_k+\frac{1}{2}$를 이분 탐색으로 찾을 수 있다. 이렇게 찾은 $a_k$에 대해 $\lambda^*=-a_k$이면, $m$과 $h(\lambda^*)$은 같은 직선의 정의역에 속한다.
이때 답은 다음과 같다.
$$
\begin{align}
dp[m][n] & = f(m) \cr
& = f(h(\lambda^*))-\lambda^*(m-h(\lambda^*)) \cr
& = dp_{\lambda^*}[n]-\lambda^*h(\lambda^*)-\lambda^*(m-h(\lambda^*) \cr
& = dp_{\lambda^*}[n]-\lambda^*m
\end{align}
$$
실제 구현할 때는 반정수를 구현하는 대신 $c$ 배열의 값을 2배로 하면 된다. 이때 $f(i)$도 2배가 되기 때문에 기울기가 2배가 된다. 홀수 범위에서 $\lambda=-2a_k+1$을 찾고, $\lambda^*=-2a_k$으로 계산한 후 최종 답을 2로 나눠주면 반정수를 구현하는 것과 동일하다.
이분 탐색의 시간 복잡도는 절대값이 가장 큰 기울기에 의해 결정된다. $f(i)$는 볼록함수이므로 $X=\left\vert f(2)-f(1)\right\vert$ 가 가장 절대값이 큰 기울기이다. 각 $\lambda$에 대해 $dp_\lambda[n]$을 구하는 것은 $O(n^2)$이므로 전체 시간 복잡도는 $O(n^2\log X)$이다.
Reference
https://koosaga.com/243?category=554431
http://serbanology.com/show_article.php?art=The%20Trick%20From%20Aliens%5D