====== SMAWK 알고리즘 =====

  * [[wp>SMAWKalgorithm]]
  * SMAWK라는 이름의 유래는, 만든사람 5명의 이름의 첫 글자를 모아서 나온 것이라고 한다. 발음은 스모크(smoke)처럼 읽는다고 어디선가 봤었는데 출처를 까먹었다;
  * totally monotone matrix에서 row minima들을 O(n+m)에 찾아주는 알고리즘이다.
  * Monge array ⊂ Totally monotone ⊂ Monotone 의 관계가 성립하므로, monotone matrix에서 쓸수 있는 [[ps:분할 정복 최적화]] 보다 사용 가능 범위가 좁기는 한데... 분할정복 최적화를 사용해서 푸는 문제들은 대부분 이미 Monge array여서 SMAWK로 대체해서 풀수 있다. (대부분은 monotone matrix를 증명하기 위해서, Monge array라는 것을 증명한다).