코딩딩

Solved.ac 주최 그랜드 아레나 파티에 신청을 해 뒀는데, 선발되었다는 메일이 도착했다.

사실 무엇보다 선발 기준이 좀 궁금해졌는데, 선발 시점 마지막 아레나 A16을 지각+실력 이슈로 처참하게 말아먹고 난 직후였기 때문에 왜 선발됐는지 정말 궁금해졌다.

처음 예상은 1, 2번 조건은 해당 없음, 3번 조건은 100명을 뽑아도 컷에 못 들기 때문에 불가능, 4번 조건은 7회 모두 (A10~A16)참여한 사람 중 운이 좋은 경우, 5번 조건은 상위권에서 뽑겠다는 의미에서 컷보다 낮을 것으로 예상, 6, 7, 9번 조건에서 운이 좋게 선발되는 경우정도가 선발되는 경우라고 생각했기 때문이다. 실제로 4, 6, 7번 조건 내에서 우선순위를 높이려고 7회 모두 참여했는데 (A16은 컴퓨팅 환경이 없어서 휴대폰으로 억지로 참여하기도 했고), 예상 외로 4번 조건에서 7회 참가자가 전원 선발되었다.

사실 선정 확률을 높여보고자 컨퍼런스 발표 신청이라도 할까 했는데 마땅한 주제가 없어서 결국 신청 못하고 되면 좋고 하는 마인드로 기다렸는데 약간은 허무하게(?) 선정되었다.

11시까지 대회장에 도착하는 것을 목표로 계산해본 결과 8시까지는 동대구역에 도착해야 했고, 전날 금요일 저녁약속에서 집에 돌아왔을 때 이미 12시였기 때문에 바로 잠자리에 누웠다. 그런데 6시까지 잠들지 못해 밤을 샌 채로 서울행 KTX에 올랐다....

한 11시 10분쯤 돼서 대회장에 도착했다. 프론트에는 @shiftpsh 대표님, @kipa00님, 대회 후원을 해주신 Chris "utilforever" Ohk님 및 여러 스태프 분이 계셨고 (죄송합니다... 얼굴이 매칭이 잘 안돼서...) 안내를 받고 대회 유니폼으로 갈아입었다.

대회장에 들어서자마자 스태프 분들과 퍼즐 헌트를 진행중인 많은 참가자 분들이 분주하게 움직이고 계셨다. 자리를 찾아 앉자마자 퍼즐 헌트 팀원이셨던 @mingmingmon님이 빠르게 저를 납치해 가셨고 눈치 살필 겨를도 없이 퍼즐 헌트 이벤트에 바로 뛰어들었다. 

팀 스코어 최종 6솔브로 마무리했다. 내가 푼 문제는 네 번째 이야기인데, 원래부터 이런 유형의 문제에 강했기 때문에 가장 먼저 시작했다. 혼자 풀 때는 잘 안풀렸는데 예전에도 그런 경험이 있어 팀원 중 아무나를 붙잡고 설명하면서 문제 풀이를 똑같이 했는데 답이 나왔다... 답안 제출할 때까지만 해도 그냥 그런줄 알았는데 지금 다시 보니 답이 "TAB UI"였다. TABUI가 뭐지 하면서 그냥 제출하긴 했는데... 이후 다섯 번째 이야기의 io.cpp를 해석하고 시간이 끝났다. 결국 답을 얻지는 못했고 최종 6솔브로 끝났다.

@toycartoon님이 대회장 전체를 돌면서 많은 참가자분들의 사인을 받으러 다니셨는데, 퍼즐헌트를 본격적으로 시작해보려 하기 직전에 사인을 뺏겼다. 본 대회가 시작되기 전 쉬는 시간 Chris "utilforever" Ohk님이 잠시 시간이 있어보이시길래 지난 대회 검수 감사 인사도 드릴겸 인사드리고 왔다. 

본 대회가 시작하기 전 갑자기 책상이 무너져서 상당히 당황했는데, @shiftpsh 대표님께 말씀 드리니까 즉시 책상을 교체해주셨다. 감사합니다.

본 대회에서는 3솔브로 마무리했다. A, B는 5분 이내로 빠르게 마무리 했는데 C를 풀다가 구현의 늪에 빠져버려서 120분째에 포기, D, E를 번갈아가면서 보다가 D가 빠르게 솔루션이 나와서 119분째에 해결했다. 해결하자마자 스코어보드가 프리즈됐는데, 스태프 분들이 프리즈 이후 해결로 잘못 보셨는지 결국 풍선은 두 개밖에 받지 못했다...

C 구현이 너무 힘들어서 자주 스코어보드를 들여다보게 됐는데 C번에서 많이 갈렸던 듯 하다. C번이 까다로운 구현 문제였었던지 많은 분들이 제 위로는 그런 분들이 많지 않았는데 아래로는 AC를 받았던 받지 못했던 많은 횟수를 트라이하신 분들이 많았다. 덕분에 3솔브 스코어보드가 패널티가 상당히 큰 셋이 되었고, 아예 C를 일찍 포기했던 내 등수가 3솔브가 상당히 늦었음에도 불구하고 3솔브 중 중간정도 등수까지 올라갈 수 있었다. 더군다나 그 덕에 특별상도 수상하게 되었다.

대회가 끝나고 유저 컨퍼런스를 진행했는데 @kiwiyou님, @cki86201님, @kipa00님 순서로 발표가 이어졌다. 요약하자면 @kiwiyou님과 @kipa00님은 "그들만의 웰노운", @cki86201님은 "yandex cup 재밌었다" 정도였다. 추이공간과 다면체군, 법률과 OOP 같은 "그들만의 웰노운"같은 발표할만한 자료가 있긴 한데 준비가 된다면, 그리고 기회가 된다면 해보고 싶긴 했다.

모든 순서가 끝나고 바깥에 계시던 @kiwiyou님, @dohoon님, Chris "utilforever" Ohk님 등 여러 분이 모여계시길래 잠시 인사를 하고 나왔다. @kiwiyou님께서 문제 잘 풀었다고 감사의 말을 해주셨는데 사실 무슨 문제인지 잘 모르겠다. (파댕이컵 H번인 것 같긴 한데... 맞나요...?) 아무튼 잘 풀어주셔서 감사합니다. @dohoon님은 "가을 프사분"으로 기억하고계셨다...

마지막으로 @mugamta 선배님과 저녁을 먹고 다시 서울역으로 갔다. 부족한 잠을 채우기 위해 KTX 안에서 잘까 했는데 스트릭을 위해 다른 문제를 KTX 안에서 풀고 잤다.

한 일.

@kiwiyou님, Chris "utilforever" Ohk님, @toycartoon님께 :fan:이에요 시전

릭롤링당하기

TODO.

@shiftpsh 대표님, Chris "utilforever" Ohk님 명함에 사인 받기

구현 문제 보고 도망가지 않을 정도로 연습하기

대회 링크: https://www.acmicpc.net/contest/view/1208

첫 대회 개최인 만큼 열심히 공들였던 것 같다. 출제/검수진 모집, BOJ 대회 개최 신청 컨택, 무엇보다 이모티콘 작가님 컨택까지 제법 오래 신경썼던 것 같다.

내가 출제한 문제는 E번, H번이다.

E번은 원래 "정점 분할 말고 간선 분할이 정해인 문제를 만들어보자"하고 만든 문제인데, 간선분할 데이터를 만들고 보니 정점 분할이 더 최적해였다... ... 정점 분할이 적정 부하를 받도록 문제를 세팅하고 보니 간선 분할이 메모리를 2GB나 먹는 사태가 벌어졌다. 

실제 출제 과정에서 가장 조용히 넘어갔던 문제였다. 조용히 세 분이 풀어주시고 디스크립션 수정 한두번이 끝이었다.

하지만... 대회가 시작되자마자 가장 많은 질문과 지문 수정과 토의가 이루어진 문제가 되었다. 대회 전에 문제 꼼꼼히 읽어야 한다는 것을 다시금 깨닫게 해준 문제였다.

H번은 이상한 알고리즘같은걸 찾아보다가 보로노이 다이어그램을 발견하고 읽던 와중에 떠오른 아이디어이다. 쌍대그래프라는 단어가 등장했는데, 쌍대를 이용한 문제를 만들고자 했다. 그때 4차원 기하학 문제를 만들고 싶어서 여러가지 생각이 많았는데, 4차원 쌍대를 발견하고 이거다 해서 만들게 되었다. 사실 결국 쌍대다포체가 풀이에 반드시 필요하지는 않아서 에디토리얼에서 쌍대다포체 얘기를 빼고 싶었는데, 예전에 문제 풀때 에디토리얼이 불친절해서 고생했던 기억이 떠올라 그래프 모델링 과정까지 작성했다. 출제검수단계에서 이 문제를 사람들이 어떻게 느낄지 좀 궁금했다. 당연히 내가 봤을 때는 4차원 이상의 기하학, 정다면체 등에 대해 집중해서 찾아봤기 때문에 대놓고 이분매칭이라는 느낌이 들었는데, 검수진들 반응을 보니 그렇지 않았던 것 같다. 특히 검수 코멘트로 "이분 그래프인지 알기 어려웠다"는 멘트가 달려서 제법 난감했다. 그래서 다차원 입방체가 이분그래프라는 말을 에디토리얼에 추가로 작성해줬다.

실제 대회에서도 이분 그래프라는 사실을 파악하지 못하고 General matching으로 해결하신 분이 있었다. 크기가 작아서 해결됐지만, 4차원이 아니고 k차원으로 줬으면 해결 못했을지도...

원래 전체 문제가 난이도 순으로 정렬될 예정이었으나 문제 순서에 맞게 디스크립션을 작성하다 보니 결과적으로 A,B,H정도만 제외하면 Gold~Platinum 난이도에서 섞여있는 모양새가 되었다. (C번이 빡센 구현이 된 것이 컸던 것 같다.)

다른 분이 출제한 문제 리뷰도 해보자면, C번은 O(NMT)를 O(T^3)으로 줄여야 풀리도록 설계되었는데, bitset을 이용해 깡으로 뚫어버린(...) 문제가 되었다.

D, E, F, G는 객관적으로 난이도가 제법 비슷했는데, G가 가장 먼저 풀렸고, 깡 수학이었던 F는 일찍 풀리긴 했으나 푼 사람이 적었다. D나 E는 웰 노운 문제들을 꼬아 낸 문제라 적당한 시간에 적당히 풀린 것 같다.

대회 퀄리티가 아쉬운 부분이 많았는데, 검수진들 시험기간이다 뭐다 해서 일정 여유가 적었고, 애초에 기획단계에서 기간을 촉박하게 잡기도 해서 여러 부분에서 부족한 부분이 보였다. 문제만 좋다고 좋은 대회가 아니라는 것도 겪어 봤고 (문제가 좋은지를 차치하고서라도), 성공하면 늘지만 실패하면 반복하지 않는걸 배운것이라 생각해야겠다.

TODO.

다차원 초다포체 문제 만들기

대회 링크 :https://www.acmicpc.net/contest/view/1151

BOJ에서 첫 출제를 하게 되었는데 문제 선정에 제법 고민이 있었다. 가지고 있는 몇개 문제 중에 기하 문제를 출제하기로 결정했다. 사유는 여러 가지가 있겠지만 이번 문제를 제법 빠르게 내고 싶었다. 출제 마감 기한 전에 문제가 몇개 남아서 문제를 더 추가할까 생각도 했지만 검수진들이 들어오고 나서 보니 안 내길 잘한 것 같다. (14문제 8시간짜리 대회가 될거라고는 상상도 못했다.)

O. 이사하자!

사실 이 문제를 출제하게 된 배경은 약 9달 전 게시판에 쓴 글에서부터 출발한다.

이 문제 이후 문제 조건을 명확히 명시해야 한다고 많은 사람들에게 알려주고 싶었고 이 문제를 만들게 되었다. 3차원 이하의 공간에 직사각형(또는 직육면체)을 적절히 배치해서 어떻게 하는 문제를 출제하고 싶었고, 예전에 한 번 생각했던 직사각형 충돌 문제를 내기로 결정했다. 원래 문제에서 검색을 통해 쉽게 풀릴 수도 있다고 fs_edge님이 얘기해주셨고, 그렇게 수정해서 나온 문제가 이 문제이다. 원래 이 문제에는 정사각형의 각 모서리가 좌표축에 평행하지 않을 수 있다는 힌트가 없었는데, 출제/검수진 두 명이 낚였다. 한 분은 입력 데이터를 가지고 오셔서 "이 데이터는 정사각형이 아닌게 들어오는데요?"라고 하셨고, 한 분은 "~~~하면 CCW 없이 뚫리겠네요?"라고 하셨고 당연히 평행하지 않은 경우 반례가 나오는 풀이였다. 사실 이 부분은 힌트를 줄지 오래 고민해왔다. 그러던 와중에 검수진 한 분이 "악의적으로 받아들이는 참가자가 나올 수 있다"는 말을 해주셔서 좀 더 깊이 고민하게 됐는데, 결국은 1. 생각보다 긴 대회시간과 많은 문제, 2. 생각보다 높게 뽑힌 문제 난이도, 3. 이미 두분의 출제/검수진이 낚인 점을 고려해서 힌트를 넣기로 결정했다. (힌트를 추가했지만 검수진 한 분이 또 낚이셨다...)

대회 도중 계속 O번 제출 코드를 지켜봤는데, 보고 정렬로 해결한(...) 풀이는 정말 문제 입력 범위를 잘 판단해야한다는 것을 다시금 상기시켜줬다.

결국 대회 처음 공지했던 내용은 지켜지지 않았다.(...)

덕분에 첫 출제도 해보고 출제/검수 방법이나 다른 사람들의 풀이같은 곳에서 많이 배워 간 것 같다. (디스코드 사용법도 많이 배웠다.) 

https://www.acmicpc.net/problem/30300

풀이

요약하면, 배열에 x값을 AND 했을 때 MEX값이 최대가 되는 x를 찾는 문제이다.

MEX에 대해 잘 생각해보자. MEX값이 k이려면 k보다 작은 모든 자연수 k-1, k-2, ... , 1, 0이 모두 배열에 있어야 한다.

사실 생각해보면 0부터 차례대로 숫자를 채워 나가야 하는데, 배열 위의 각 수는 자신이 갖고 있던 비트만을 사용해야 하지 없던 비트를 만들어낼 수는 없다. 따라서 MEX가 1보다 크려면 최하위 비트가 0인 수와 1인 수가 모두 있어야 하고, MEX가 3보다 크려면 최하위 2비트가 00, 01, 10, 11인 수가 모두 있어야 하고, ... 과 같은 논리 전개가 가능하다. 대회 도중 이 시점에서 풀이를 작성해 AC를 받았다.

예를 들어 [1, 8]이 주어졌다고 하자. 이 자체로는 MEX가 0이지만 x=1을 AND해주면 8이 0의 자리를 채우면서 MEX값이 2가 된다. 즉, 상위 비트를 0으로 날리면서 0부터 순서대로 채우는 것으로 MEX를 크게 만드는 문제이다. 사실 0으로 날리지 않은 비트가 있다면 그 하위 모든 비트들은 0으로 만들어주면 안된다. AND로 0으로 만든 비트가 있다면 그 비트가 최상위비트가 되는 수가 배열에 존재하지 않게 되고, 그런 수 중 최소값이 MEX값의 상한이 된다. 따라서 AND를 통해 0으로 만든 비트가 있다면, 그 상위 비트에 관계 없이 MEX의 상한이 정해진다. 이때 최대한 많은 정수를 하위 비트들에 채워야 하므로 상위 비트를 0으로 만들어 AND를 통해 결정된 상한보다 작게 만들어 주는 것이 최적이다.

이를 통해 얻을 수 있는 로직은 아래와 같다.

1. 0부터 2^30보다 작은 모든 bit = (1<<i)-1 (0 ≤ i ≤ 30)를 순회한다.

2. bit를 각 배열 요소에 AND해주고 MEX를 구한다.

3. 이전까지 구한 MEX의 최대값보다 크다면 최대 MEX값을 갱신하고 bit값을 저장한다.

4. 순회가 끝난 뒤 최종 갱신된 bit값이 문제의 정답이다.

https://www.acmicpc.net/problem/30191

풀이

애드 혹 태그가 달린 문제답게 풀이도 코드도 간단했지만 풀이를 얻기까지 한두시간 고민했다.

실제 풀이에서 맨 처음 생각한 아이디어는 우선 문자의 쌍을 찾아야 한다는 것이다. 예를 들어 U를 입력하면 그에 대응되는 S가 어딘가에 존재한다. 이런 경우 누적 합을 통해 구간을 관리할 수 있다. BOJ1023(괄호 문자열)과 비슷한 맥락에서 두 부분문자열을 연결한 문자열도 동일하게 해결할 수 있으므로 반대로 원래 문자열을 문제의 조건을 만족하는 두 부분문자열로 컷 한 뒤 해결하는 방법을 생각해봤다.

우선 예제 입출력을 분석해보자. 예제 입출력에서 발견한 특징은 "정답 문자열 제일 끝에 불필요한 N이 붙어있다. 그것도 두개씩이나."였다. 

예제 출력을 따라가면 입력의 문자열을 "뒤에서부터" 구성한다는 것을 알 수 있었다. 예컨대 예제 입력 1은 SS로도 작성할 수 있지만, 뒤에서부터 작성하면  SNNS로 작성하게 된다.

실제로 뒤에서 부터 작성하려는 아이디어를 떠올렸을 때 문뜩 든 생각은 앞서 생각한 문자 쌍을 찾기 아주 쉽다는 것이다. 최소해를 찾는 경우가 아니기때문에 문자 쌍이 대응되는 것이 유일할 필요가 없고, 아무거나 적당히 문자 쌍을 대응시킬 수 있다면(풀이 과정 중의 해의 성질을 여전히 만족하는 이상), 대응시키면 된다. 실제로 이 시점에서 문제의 풀이가 완성되었고, 바로 코드를 작성해서 AC를 받았다. 물론 코드를 작성하는 과정에서 어림으로 계산했던 디테일을 잡아갔다.

일단 최초 상태를 빈 문자열 가장 뒤에 커서가 위치한 것으로 볼 수 있다. 가장 뒤의 문자가 S라고 가정하자. 이 문자는 자명하게 U를 입력해 나온 S여야 한다. 따라서 이 S와 대응되는 U가 앞선 문자열의 일부에 존재한다. 만약 이 이전 문자가 U라고 가정하면, 즉 가장 마지막 두 글자가 US라면 이 두 글자를 제외한 나머지 앞선 부분문자열은 본 알고리즘으로 풀 수 있다. 따라서 UNN을 시행하면 마지막 US를 오른쪽에 입력하고 나머지 문자열을 입력하기 위해 US를 제외한 나머지 빈 문자열 가장 뒤에 위치시킨 것과 같다. 다르게 말하면, US를 가장 오른쪽에 입력하고 나머지 부분문제를 풀기 위한 최초상태로 진입하는 것이다.

앞서 생각했던 괄호 문자열과 비슷하게 입력을 분석해보자. US, SU는 입력할 수 있는 문자열이다. 입력할 수 있는 두 문자열 S, T에 대해 ST도 입력할 수 있는 문자열이고, UTS, STU도 입력할 수 있는 문자열이다. 어떤 부분문자열 T를 입력하고 난 뒤 커서를 가장 왼쪽에 위치할 때 까지 N을 실행하고, 다시 부분문자열 S를 입력하면 ST를 출력할 수 있고, UN을 실행하고 T를 입력하면 UTS, SN을 실행하고 T를 입력하면 STU도 입력할 수 있다.

이 로직에서 커서를 우선 어떤 문자 왼쪽으로 이동시키고 나면 커서 오른쪽 문자열은 어떤 일이 있어도 수정될 수 없다. 따라서 커서 오른쪽 문자열을 입력마다 추적해보자. 커서의 위치를 C로 쓰자. UNUNNN의 경우 "USC" -> "UCS" -> "UUSCS"-> "UUCSS"-> "UCUSS" -> "CUUSS"와 같이 작성된다. 이때 N이 하나 추가될 때마다 커서가 한 칸 왼쪽으로 이동한다. 반대로, N이 하나 추가될 때마다 커서 오른쪽에 문자가 하나 추가된다. 우리가 원하는 로직이 문자를 입력한 뒤 커서를 이미 입력한 문자 왼쪽으로 보내는 것이기 때문에 N을 문자열 길이만큼 입력해야 한다.

실제로 이를 재귀로 실행할 필요는 없다. 두 부분문자열이 연속해서 등장하는 경우는 N을 출력해 커서의 위치를 이동한 뒤 출력하면 되고, STU, UTS의 경우는 UN(또는 SN)을 실행한 뒤 커서 왼쪽의 부분문자열을 보면 S(또는 U)가 하나 U(또는 S)보다 하나 많은 부분문자열이 된다. 이때 입력할 수 있는 문자열을 오른쪽부터 입력하고 난 뒤 S(또는 U)를 만난다면 가장 앞선 문자와 쌍을 이루는 문자라고 생각할 수 있으므로 N을 실행하면 UTS, STU의 문자열을 입력하고 커서를 왼쪽 끝으로 이동시킬 수 있다. 좀 더 자세히 얘기하자면, 오른쪽에서 왼쪽으로 훑으면서 커서 오른쪽의 문자열이 입력가능한 문자열일 때 처음 만난 문자와 대응되는 S<->U는 이 두 문자를 제외하고 입력가능한 문자열이 지난 후에 처음으로 나오는 대응되는 문자인 경우는 해가 된다.

설명이 길었는데, 실제 로직은 아래와 같이 해결된다.

1. 가장 오른쪽 문자부터 순서대로 확인한다. S에 1, U에 -1을 대응시키자. 오른쪽에서 왼쪽으로 이동하면서 문자열의 누적합을 구하자. 누적합이 0이라면 이전까지 탐색한 문자열이 입력가능한 문자열이라는 뜻이다. (문제 조건에서 해가 존재함을 증명가능하다고 서술했다.)

2. 현재 만난 문자가 S이고 누적합이 0 이상이라면 UN을 출력한다.

3. 현재 만난 문자가 U이고 누적합이 0 이하라면 SN을 출력한다.

4. 현재 만난 문자가 S이고 누적합이 음수이거나, 현재 만난 문자가 U이고 누적합이 양수라면 N을 출력한다.

이렇게 완성된 문자열은 N이 문자열 길이만큼 존재하고 문자열 길이의 절반만큼 U나 S를 입력해야 하므로 정확히 3/2N개의 길이가 된다.

뭐라 설명하기는 어렵지만 순서대로 따라가면 해가 되겠거니하는 생각은 쉽게 할 수 있을거라고 생각한다. 애드혹 문제들이 설명하거나 유도하는 과정을 말로 설명하기는 어렵지만 로직을 짰을 때 타당하다고 확인하기 쉬운 문제들인 것 같다.

https://www.acmicpc.net/problem/18185

관점을 바꿔서 어떤 공장에서 라면을 구매하는 가격을 책정하는 문제로 바꿔보자. 한 공장에서 라면을 구매하는 방법은 3원을 주고 구매하는 방법과 특정 조건이 만족되면 2원을 주고 구매하는 방법의 두 방법 뿐이다. 당연히 한 공장에서 라면을 구매하기 위해서는 2원에 구매할 수 있는만큼 구매하는 것이 최적해이다.
첫번째 공장에서는 이전 공장이 하나도 없으므로 무조건 3원에 라면을 모두 구매해야 한다. 따라서 유일한 방법인 3원에 모두 구매하는 것이 최적해이고, 이후에 다른 공장에서 구매하는 것과 관계없다. 두번째 공장에서는 최대 첫번째 공장에서 3원에 구매한 라면의 수만큼 2원에 구매할 수 있고, 나머지는 모두 3원에 구매해야 한다. 두번째 공장에서 3원에 구매했거나, 첫 번째 공장에서 3원에 구매한 것을 토대로 두 번째 공장에서 2원에 구매한 개수만큼 세 번째 공장에서 2원에 구매할 수 있다.
세 번째 공장 이후의 2원에 구매할 수 있는 라면의 최대 개수는 i번째 공장에 대해 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수가 된다.
좀더 일반적으로 두 번째 공장의 경우 i-2번째 공장에서 구매한 라면의 총 개수가 0이라 두면 동일한 계산이 되고, 첫 번째 공장도 i-1, i-2번째 공장에서 라면을 0개 구입한 것과 동일하다.

따라서 존재하지 않는 공장에서 구매한 개수를 0이라 강제하고 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수를 이용해 DP를 돌리는 것으로 해결 가능하다.

https://www.acmicpc.net/problem/11003

크기 L인 부분구간의 최솟값을 모두 찾는 문제이다. 처음 봤을때는 슬라이딩 윈도우로 풀어야 할 것 처럼 생겼다. 

"최솟값을 아주 빠르게 찾을 수 있고, 원하는 값을 아주 빠르게 제거할 수 있는" 자료구조가 있으면 된다. 일단 슬라이딩 윈도우로 작은 크기의 문제를 풀어보자. 시간복잡도는 O(N*L)이다.

예제의 앞 10개항이다.

이제 관찰을 해보자. 슬라이딩 윈도우 안에 삽입된 수열의 항은 L번의 최솟값 산출 후 제거된다. 이 슬라이딩 윈도우에 삽입된 수는 삽입된 순서대로 제거된다. 즉, 큐를 이용해 해결할 수 있을 것으로 보인다. 

D3을 구할 때 5 뒤에 2가 삽입되었다. 5는 2보다 먼저 제거되는데, 제거되기까지 슬라이딩 윈도우에는 5보다 작은 2가 항상 존재하므로 5는 답이 될 수 없다. 따라서, D3을 구할 때 굳이 5가 슬라이딩 윈도우 안에 있을 필요가 없다. 따라서 위의 해결과정을 살짝 수정하자. 

이 과정을 보편적으로 설명하면, 슬라이딩 윈도우 중 현재 단계에서 새로 삽입될 수 보다 작은 값을 미리 제거할 수 있다는 것이다. 즉, 슬라이딩 윈도우의 가장 마지막 항 보다 큰 수는 슬라이딩 윈도우에서 미리 제거할 수 있다. 하지만, 이 과정을 전 과정에 동일하게 적용한다면, 가장 뒤의 원소를 삽입하기 이전에도 이전의 가장 마지막 항보다 큰 수는 슬라이딩 윈도우 안에 없고, 귀납적으로 슬라이딩 윈도우는 정렬되어있다.

정렬되어있는 슬라이딩 윈도우는 큰 값이 뒤에 위치한다. 이때 이 슬라이딩 윈도우의 제일 뒤에 값을 삽입하려한다. 이때 새로 삽입되는 숫자보다 큰 숫자가 존재한다면, 슬라이딩 윈도우의 제일 끝의 원소는 새로 삽입될 숫자보다 자명하게 크다. 따라서 가장 마지막 원소를 제거하고 다시 판단하면 된다. 즉, 슬라이딩 윈도우의 가장 나중에 삽입된 원소를 제거하는, 스택의 쿼리도 지원해야 한다.

이 슬라이딩 윈도우가 제공해야 할 쿼리는 제일 앞의 원소를 제거하고, 제일 위의 원소를 추가하거나 제거하는 쿼리이고, 덱으로 쉽게 구현할 수 있다.

정리하면, i번째 항 Ai를 슬라이딩 윈도우에 추가하기 위해서, Ai-L을 슬라이딩 윈도우에서 제거한다. 이 제거과정은 삽입되는 순서대로 원소를 제거하는 과정이므로 덱의 제일 앞에 있거나 그 전에 이미 제거되었을 것이다. 따라서 덱의 제일 앞에 있는 경우에는 제거하고, 아니면 그냥 넘어간다. Ai를 추가하기 전, 덱의 제일 뒤에서 Ai보다 큰 값들을 모두 제거한다. 그리고 Ai를 덱에 넣고, 제일 앞의 값이 Di가 된다.

https://www.acmicpc.net/problem/1854

n=1일때는 자명하게 다익스트라로 구할 수 있다. 다익스트라로 1번째 최단경로를 구하는 과정을 다시 곱씹어보자.

이때까지의 모든 방문에 대해 방문하지 않은 모든 정점을 방문하고, 1번째 최단경로를 갱신한다. 이를 적절히 변형해서 k번째까지 구하면 된다.

우선순위 큐에는 아직 갱신되지 않은 적절한 경로들이 들어있다고 하자. 우선순위 큐의 정렬 순서는 경로의 길이이다. 우선순위 큐에서 경로 하나를 pop하자. 이 경로의 최종 정점에 인접한 모든 정점들로 가는 전체 경로들을 우선순위 큐에 넣자. 이렇게 되면 각 최종 정점으로 가는 새로운 경로가 생긴다. 이때 최종 정점 중 한 번 이상 방문한 경우 우선순위 큐에 넣는 과정을 생략하면 1번째 최단경로를 다익스트라를 이용해 구할 수 있다.

일정 횟수 이상 방문을 제한하는 것으로 k번째 최단경로도 쉽게 구할 수 있다. 위 과정에서 방문 횟수가 k 미만인 경우 우선순위 큐에 넣고, k 이상인 경우 넣지 않는 것으로 충분하다.

먼저, 1번 정점으로 가는 길이 0의 경로를 우선순위 큐에 넣고 시작하자. 반복문을 통해 우선순위 큐에서 경로 하나를 pop한다. 그리고 이 정점의 방문횟수를 추가한다. 이 방문횟수는 이 경로가 몇 번째 최단경로인지를 의미한다. 이 정점과 연결된 모든 k번 미만 방문한 정점에 대해 이 경로 뒤에 그 정점을 추가해 우선순위 큐에 집어넣는다. 

이 로직의 정당성은 아래 과정을 통해 보일 수 있다.

1. 경로를 우선순위 큐에 넣고 순서대로 탐색했기 때문에, 정점을 방문할 때 사용한 경로 가운데 k번째 경로를 반환한다.

2. 누락되는 경로는 없다. 만약 존재한다면, 다시말해 적절한 시점에서 우선순위 큐의 경로 길이 length에 대해 우선순위 큐에 한 번도 들어가지 않은 경로 중 length보다 작은 길이의 경로 P가 존재한다면, P의 마지막 정점을 제거한 P-가 우선순위 큐에 들어간 적이 없다는 것이고, P--도 우선순위 큐에 들어간 적이 없다는 것이고, ... 의 과정을 통해 모순을 반환할 수 있다. (1번 정점으로 가는 길이 0의 경로를 넣은 적 없다는 결론을 얻을 수 있으므로)

3. k번을 초과하여 정점 A를 방문한 뒤 B를 방문하는 경로는 B를 k번 이하 방문하는 경로일 수 없다. A를 방문한 뒤 B를 방문하는 k개의 경로가 더 짧은 경로가 되기 때문이다.

마지막으로 경로의 모든 과정을 우선순위 큐에 넣을 필요는 없다. 따라서 경로의 길이와 최종 방문한 정점만 우선순위 큐에 넣는 것으로 해결가능하다.