SMAWK 알고리즘

SMAWKalgorithm

SMAWK라는 이름의 유래는, 만든사람 5명의 이름의 첫 글자를 모아서 나온 것이라고 한다. 발음은 스모크(smoke)처럼 읽는다고 어디선가 봤었는데 출처를 까먹었다;

totally monotone matrix에서 row minima들을 O(n+m)에 찾아주는 알고리즘이다.

Monge array ⊂ Totally monotone ⊂ Monotone 의 관계가 성립하므로, monotone matrix에서 쓸수 있는 분할 정복 최적화 보다 사용 가능 범위가 좁기는 한데… 분할정복 최적화를 사용해서 푸는 문제들은 대부분 이미 Monge array여서 SMAWK로 대체해서 풀수 있다. (대부분은 monotone matrix를 증명하기 위해서, Monge array라는 것을 증명한다).