's profile image

December 18, 2022 00:00

SMAWK algorithm

algorithm

들어가며

SMAWK 알고리즘은 $n \times m$ 크기의 totally monotone한 행렬에서 모든 행마다 최솟값의 위치를 $O(n+m)$ 시간에 구하는 알고리즘이다. 이 글에서는 SMAWK 알고리즘에 대해 소개하고, 이를 통해 해결할 수 있는 문제들에 대해 소개한다.

단조성. $2 \times 2$ 행렬 $\left[ {\begin{array}{ccc}a & b \ c & d \ \end{array}} \right]$ 은 다음 조건이 성립하면 monotone하다고 한다.

  1. $c < d$이면 $a<b$이다.
  2. $c=d$이면 $a\leq b$이다.

$n \times m$ 행렬은 만약 모든 $2 \times 2$ 부분행렬이 monotone하다면 totally monotone하다고 한다.

최솟값의 위치의 단조성. Totally monotone한 행렬 $M$의 $i$번째 행의 최솟값 $Min_i$에 대해, $Min_i=M[i,j]$를 만족하는 가장 작은 $j$를 $X_i$라고 하자. 그러면 $X_1 \leq X_2 \leq \cdots \leq X_n$을 만족한다. 즉, 각 행에서 가장 왼쪽에 위치한 최솟값의 위치가 단조증가한다.

알고리즘

이 알고리즘은 두 가지의 변환을 번갈아 수행하면서 재귀적으로 문제의 크기를 점차 줄여나가며 작동한다. 첫 번째 변환은 INTERPOLATION으로, $n \times m$ 크기의 문제를 $\lfloor{n\over2}\rfloor \times m$ 크기의 문제로 변환하며 $m \leq n$일 때 수행된다. 두 번째 변환은 REDUCE로, $n \times m$ 크기의 문제를 $m’ \leq n$을 만족하는 $n \times m’$ 크기의 문제로 변환하며 $m > n$일 때 수행된다. 먼저 REDUCE가 어떻게 수행되는지 살펴보자.

Reduce

REDUCE에서는 행렬의 단조성을 이용하여 고려할 필요가 없는 열들을 최소 $m-n$개 이상 삭제하는 것이 목표이다. 이를 위해 살아남는 열들의 스택 $S$를 관리하자. 살아남는 열마다 대표 원소를 표시해 줄 것인데, 이 대표 원소보다 위쪽에 위치한 원소들은 더 이상 고려할 필요가 없다는 의미이다. 알고리즘은 다음과 같이 진행된다. 처음에 $S$는 비어 있다.

Totally monotone한 행렬 $M$의 모든 열에 대해서, 왼쪽 열부터 차례대로 처리한다. $j$번째 열 $C_j$를 처리할 때 다음과 같은 과정을 거친다.

  1. 만약 $S$가 비어 있다면 $C_j$를 스택 $S$에 삽입하고 $M[1, j]$를 대표 원소로 표시한다.

  2. 아니라면 다음을 스택 $S$가 비거나 $C_j$가 더 이상 유효하지 않을 때까지 반복한다.

    (a) $C_k$를 $S$에서 가장 위에 위치한 열이라고 하자. 이 때 $M[i, k]$를 $C_k$의 대표 원소라고 하자.

    (b) $M[i, k]$와 $M[i, j]$를 비교한다.

    • $M[i,j] \leq M[i, k]$인 경우, 행렬의 단조성에 의해 $C_k$는 어떠한 행의 최솟값도 될 수 없으므로 스택 $S$에서 삭제한다.

    • $M[i,j] > M[i, k]$이고 $i=n$인 경우 $C_j$는 더 이상 유효하지 않고 행렬의 단조성에 의해 어떠한 행의 최솟값도 될 수 없으므로 그대로 반복문을 종료한다.

    • $M[i,j] > M[i, k]$이고 $i<n$인 경우 $C_j$는 더 이상 유효하지 않으나 살아남는다. $M[i+1, j]$를 대표 원소로 표시하고 스택 $S$에 삽입한 뒤 반복문을 종료한다.

이를 모든 열에 대해 수행하면 스택 $S$에 저장된 살아남은 열들의 대표 원소는 모두 다른 행에 위치하게 되므로 최대 $n$개의 열만 살아남는다. 줄어든 행렬은 원래 행렬의 모든 행들과 살아남은 열들로 구성된 행렬이다. 이제 줄어든 행렬에서 다시 재귀적으로 문제를 해결하면 된다.

Interpolation

INTERPOLATION에서는 먼저 행렬의 크기를 반으로 줄여버린 뒤, 그 행렬에서 구한 답을 이용하여 나머지 행렬의 답을 구하는 방식을 사용한다.

Totally Monotone한 행렬 $M$에 대해, 홀수 번째 행들을 모두 삭제한 행렬 $M’$룰 만들자. $M’$에 대해 재귀적으로 SMAWK 알고리즘을 사용하여 문제를 해결하자. 이제 $M’$의 $i$번째 행에서 가장 왼쪽에 존재하는 최솟값의 위치 $X_i$를 모두 알게 되었다. 이 정보를 이용하여 $M$의 짝수 번째 행들의 답을 구해 보자. 각 짝수 번째 행 $R_i$에 대해서 다음과 같은 과정을 거쳐 답을 구할 수 있다.

  1. 행 $R_{i-1}$에서 가장 왼쪽에 존재하는 최솟값의 위치를 $s$, 행 $R_{i+1}$에서 가장 왼쪽에 존재하는 최솟값의 위치를 $e$라고 하자. 만약 $R_{i-1}$이 존재하지 않는다면 $s=1$, $R_{i+1}$이 존재하지 않는다면 $e=m$이다.
  2. 최솟값의 위치의 단조성에 의해 $s \leq X_i \leq e$를 만족하므로, $s \leq j \leq e$를 만족하는 모든 $j$에 대해 선형적으로 탐색하여 $X_i$를 직접 계산한다.

이 과정을 거치면 짝수 번째 행들의 $X_i$가 단조증가하기 때문에 $O(n+m)$ 시간에 행렬 $M$의 모든 행에 대해 $X_i$를 구할 수 있다.

시간 복잡도를 간단히 분석해 보자면, REDUCE와 INTERPOLATION을 번갈아 사용하면 행렬의 크기 $n, m$이 각각 반 이상 줄어들고, 각 변환 과정은 선형 시간에 이루어지므로 $O(n+m)$ 시간에 전체 문제를 해결할 수 있다.

적용과 구현

SMAWK 알고리즘을 이용하여 백준 온라인 저지의 김치 문제를 해결하여 보자. 문제를 간단히 요약하면 $N, D, T[1..N], V[1..N]$가 주어졌을 때 ($T$는 단조감소)

\[M[i, j] =\begin{cases} (j-i)T[j] + V[i],& \text{if } i \leq j \leq i+D\\ -\inf, & \text{otherwise} \end{cases}\]

라고 하자. 이 때 $M$의 원소 중 최댓값을 찾는 문제이다.

이 때 $-M$은 Monge property를 만족한다. 즉, $1 \leq a < b \leq N$, $1 \leq c < d \leq N$을 만족하는 $a, b, c, d$에 대해 $M[a, c] + M[b, d] \leq M[a, d] + M[b, c]$를 만족한다. $a, b, c, d$가 모두 유효할 때 식을 풀어 써 보면

$M[a, c] + M[b, d] \leq M[a, d] + M[b, c] \iff$

$(a-c)T[c] - V[a] + (b-d)T[d] - V[b] \leq (a-d)T[d] - V[a] + (b-c)T[c] - V[b] \iff$

$0 \leq (b-a)(T[c]-T[d])$

으로 Monge property를 만족함을 알 수 있다. Monge property를 만족하는 행렬은 totally monotone함이 잘 알려져 있다. 그러므로 우리는 $-M$에 SMAWK 알고리즘을 사용하여 문제를 $O(N)$ 시간에 해결할 수 있다. 다음은 김치 문제를 SMAWK 알고리즘으로 해결하는 C++ 코드이다.

#include <bits/stdc++.h>
#define sz(V) ((int)(V).size())
using namespace std;
using ll = long long;
const ll INF = 1LL * 1e18;

int D, T[100009], V[100009], X[100009];

ll f(int x, int y) {
	if(y < x || x+D < y) return -INF;
	return 1LL * (y - x) * T[y] + V[x];
}

void smawk(vector<int> &R, vector<int> &C) {
	int N = sz(R), M = sz(C);
	if(N == 0) return;
	// REDUCE
	vector<int> S;
	for(auto& it: C) {
		if(S.empty()) S.push_back(it);
		else {
			while(S.size()) {
				ll p = f(R[sz(S) - 1], S.back()), q = f(R[sz(S) - 1], it);
				if(p > q) break;
				S.pop_back();
			}
			if(sz(S) < R.size()) S.push_back(it);
		}
	}
	// INTERPOLATION
	vector<int> O;
	for(int i=1; i<R.size(); i+=2) O.push_back(R[i]);
	smawk(O, S);
	for(int i=0, j=0; i<R.size(); i+=2) {
		int s = S[0], e = S.back();
		if(0 < i) s = X[R[i-1]];
		if(i+1 < R.size()) e = X[R[i+1]];
		while(j < sz(S) && S[j] <= e) {
			if(X[R[i]] == 0 || f(R[i], X[R[i]]) < f(R[i], S[j])) X[R[i]] = S[j];
			++j;
		}
		--j;
	}
}

int main() {
	int N; scanf("%d%d", &N, &D);
	for(int i=1; i<=N; i++) scanf("%d", &T[i]);
	for(int i=1; i<=N; i++) scanf("%d", &V[i]);
	vector<int> R, C;
	for(int i=1; i<=N; i++) {
		R.push_back(i);
		C.push_back(i);
	}
	smawk(R, C);
	ll ans = 0;
	for(int i=1; i<=N; i++) ans = max(ans, f(i, X[i]));
	printf("%lld", ans);
	return 0;
}

위 코드에서는 대표 원소를 명시적으로 표시하지 않고, 스택 $S$에 들어 있는 원소의 개수를 이용하여 대표 원소의 위치를 구한다. 또한 최솟값이 아니라 최댓값을 찾는 코드이기 때문에 부등호 방향을 유의하면서 보자.

마치며

이러한 유형의 문제는 보통 Problem solving에서 DnC Optimization이라는 이름으로 $O(N \log N)$ 시간에 해결하는 방법이 잘 알려져 있다. DnC Optimization이 충분히 빠른 시간 안에 작동하기 때문에 SMAWK 알고리즘을 사용하여야만 해결할 수 있는 문제는 아직 거의 출제된 적이 없으나, 알고리즘도 복잡하지 않고 코드가 간단한 편이어서 소개하는 글을 작성해 보았다. 참고 자료[2]에 REDUCE와 INTERPOLATION을 큰 행렬에서 직접 수행하는 예시가 잘 나와 있으니 이를 같이 보면서 따라가면 이해가 수월할 것이다.

References

  • [1] Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195–208, 1987.
  • [2] http://web.cs.unlv.edu/larmore/Courses/CSC477/monge.pdf
  • [3] https://en.wikipedia.org/wiki/SMAWK_algorithm