근황
안녕하세요, 방치해두었던 블로그에 근황을 전하러 찾아왔습니다.한줄요약: 입대해서 남는 시간에 PS랑 게임 개발을 해보는 중입니다. PS월파운이 좋게도 21년 대학에 입학하자마자 훌륭한 팀원들과 DO Solve라는 팀으로 ICPC 월드 파이널 진출권을 얻었다. 그러나 코로나19 때문에 대회 일정이 밀리고 밀리고 밀려 24년이 되어서야 이집트에 가서 월드 파이널을 치르고 올 수 있었다. 덕분에 팀원들과 연습은 정말 길게 했다. 생각한 풀이를 제대로 증명하지 않고 사풀이를 그냥 구현하는 습관이 있었는데, 팀원들과 연습하면서 풀이를 설명할 일이 많아서 이 습관을 조금 고칠 수 있었다. 전반적인 PS 실력도 팀연습 덕분에 그나마 유지할 수 있었던 것 같다.아쉽게도 월파에는 우리 팀이 잘하는 스타일의 문제 셋이..
간단한 트위치 챗봇 만든 이야기
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$개 이상 삭제하는 것이 목표이다. 이를..