0. 동기 평소에 내가 즐겨 보는 트위치 방송이 하나 있다. 슈퍼 마리오 메이커 2라는 게임의 '어디까지 마리오 챌린지' 매우 어려움 난이도를 주로 플레이하는 방송인데, 이게 뭔지 간략하게 설명하자면 전 세계 유저들이 만든 마리오 코스들 중에서 난이도가 가장 어려운 코스들이 무작위로 주어지면 한정된 목숨 내에서 그 코스를 클리어해야하는 컨텐츠다. 코스를 잘 클리어하면 목숨을 더 얻을 수도 있고, 여러 번 죽으면 많은 목숨을 잃을 수도 있다. 목숨이 0이 되면 게임 오버이고, 게임 오버가 되지 않는 한 무한정 코스들을 클리어하는 모드가 '어디까지 마리오 챌린지'이다. 아무튼 이 방송을 하시는 분이 1위와 점점 가까워지고 있는 상황이라 방송에서 1위랑 차이가 얼마나 나는지, 언제쯤 세계 1위가 될 수 있는지..
들어가며 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하다고 한다. $c < d$이면 $a n$일 때 수행된다. 먼저 REDUCE가 어떻게 수행되는지 살펴보자. Reduce REDUCE에서는 행렬의 단조성을 이용하여 고려할 필요가 없는 열들을 최소 $m-n$개 이상 삭제하는 것이 목표이다. 이를..
BOJ 11744 Jump 정답 스트링 $S$를 찾기 위해서는, 일단 $Jump(Q) = n/2$인 상황을 어떻게든 만들어야 한다. $S$에서 $0$의 개수를 $a$라고 하고, $1$의 개수를 $b$라고 하면 $a+b=n$이기 때문에 $min(a, b) \le n/2 \le max(a, b)$가 성립한다. 즉, $Q=00...00, Q=10...00, Q=11...00, \cdots, Q=11...10, Q=11...11$을 모두 질문하면, $Jump(Q) = n/2$인 경우를 무조건 얻을 수 있다. 즉 $N+1$번의 질문으로 $Jump(Q_m) = n/2$를 만족하는 String $Q_m$을 찾을 수 있다. 이제 $Q_m$을 조금씩 만지면서 $Jump$값의 변화를 살피면 $S$를 알아낼 수 있을 것이다..