cdjs의 코딩 공부방

이전 글에서 살짝 떡밥을 뿌렸던 알고리즘 대회인 제1회 보라매컵이 종료되었습니다.

제 2022년 최대 프로젝트기도 했고, 어쩌면 지금까지 알고리즘 공부를 하면서 가장 크게 일을 벌였던 경험이었던 것 같습니다. 또한, 아무래도 군대 내에서 진행했던 대회다 보니 특별한 점들도 많았습니다.

이 글에서는 알고리즘 대회를 개최하기로 한 계기부터 마무리까지, 제1회 보라매컵을 개최한 후기를 작성해보고자 합니다.

1. 대회 개최 계기

대회 개최 계기는 사실 이전 글에 어느 정도 적혀있었습니다. 7월에 진행되었던 UCPC 본선이 끝나고 난 뒤, 솔직히 조금 무료해졌습니다. UCPC 문제를 단 하나만 출제하긴 했으나 제 역량 밖의 문제였기에 해당 문제를 준비하는 데 정말 많은 노력과 에너지가 소모되었고, 그렇게 에너지를 소모해가며 한 달 가량을 지내다 보니 이제는 에너지를 쏟을 곳이 없어서 무료해졌던 것이었습니다.

그러던 중 문득 "부대 내에서 알고리즘 대회를 개최하면 어떨까?" 라는 생각을 하게 되었습니다. 저희 부대는 설날과 추석마다 정기적으로 부대 동아리에서 여러 대회들을 개최하는데, 개발 현업자 및 지망생이 많은 저희 부대 특성 상 알고리즘 대회를 개최하면 꽤 많은 사람들이 참여할 것이라 생각되기도 했습니다. 또, UCPC 문제를 출제하며 군생활이 빠르게 녹았다는 점을 고려하면, 대회 개최 준비를 하다 보면 제 군생활이 더욱 빠르게 녹을 것이라고 생각했습니다.

그렇게 8월 중순부터 대회를 조금씩 구상하기 시작했습니다.

2. 대회 및 문제 구상하기

초기 대회의 구상은 다음과 같았습니다.

• 예선/본선 구분 없이 단일 대회로 개최
• 문제는 총 7문제
• 난이도는 Bronze 하위권부터 Platinum 하위권까지
• 모든 문제는 군대 컨셉

예선/본선을 나누게 되면 너무 많은 문제를 출제해야 될 것 같다는 생각에 처음에는 도저히 예선/본선으로 나눠서 대회를 개최하려는 계획은 세우기 힘들었습니다. 또한, 부대 내에서 알고리즘 문제 풀이를 별로 하지 않으신 분들도 재미있게 참여할 수 있도록 아주 쉬운 Bronze 난이도의 문제도 필요했으며, 실력자들을 가려내기 위해 Platinum 문제도 필요하다 생각되어 난이도를 BBSSGGP 정도로 배치한 7문제 셋을 구상했습니다. 또한, 군대에서 진행되는 대회라는 점을 강조하기 위해 출제되는 모든 문제는 군대 혹은 공군과 관련된 내용으로 구성하기로 했습니다.

해당 구상에 맞춰, 바로 문제 아이디어를 짜내기 시작했습니다. 저는 일반적으로 풀이를 먼저 생각한 뒤 문제를 만드는 방식보다는 문제 상황을 먼저 구상한 뒤 풀이를 생각하는 편이라, 군대를 컨셉으로 한 바탕들을 여러 가지 나열한 뒤에 마음에 드는 것들을 골라서 사용하기로 했습니다. 다만, 이 당시 8월달까지만 해도 대회를 무조건 개최하겠다는 생각보다는 문제들을 만들어놓고 나중에 생각하자는 마인드기도 했어서, 당시에 만들어진 문제들 중에는 군대 컨셉이 아니었던 문제들도 꽤 많았습니다. 그래서인지 이때 만들었던 문제들은 대회에 하나도 출제되지 않았지만, 아마 언젠가 재활용해서 쓸 날이 오겠지요..?

그렇게 9월 중순까지 열심히 문제를 만들어, 총 6문제를 구상하였습니다. 그 중에서 실제 대회에 출제된 문제로는 본선 C - 조사전달 문제가 있고, 그 당시 구상했던 문제를 마개조하고 강화하여 나온 문제로 본선 G - MVP 투표 문제가 있습니다. (다시 말하면, 구상했던 6개의 문제 중 4문제는 버려졌다는 뜻입니다 허허...)

그런데 이렇게 문제를 구상하던 중, 곰곰히 생각해 보니 예선과 본선으로 나누지 않고서는 대회를 개최하기가 힘들었습니다. 저희 부대에서 명절 대회를 개최하기 위해서는, "부대 내 모든 사람들"이 참여할 수 있는 대회를 만들어야 합니다. 이는 알고리즘 대회를 좋아하는 사람뿐만 아니라, 알고리즘에 별 관심이 없는 사람이더라도 대회에 참가할 수 있도록은 해야 한다는 뜻입니다. 즉, 대회에 참여할 수 있는 인원 수가 상당히 많아질 수 있다는 뜻입니다. 하지만 저는 부대 내에서 대회를 개최해야 했고, 그러면 부대 내의 사지방에서 많은 인원이 대회에 참가할 수 있도록 해야 하는데, 사지방의 PC 수는 많아야 25개였기 때문에 많은 인원들을 동시에 대회에 참가시킬 방법이 없었습니다. 결국, 단일 대회로 진행하기로 한 초기 계획은 취소하고 예선과 본선으로 나누어 진행하기로 결정했습니다. 예선은 그냥 아예 길게 48시간가량 진행하기로 하고, 본선은 시간을 잡고 딱 16명만 뽑아서 사지방에서 진행하기로 했습니다.

그렇게, 만들어야 할 문제 수가 갑자기 두 배로 늘어나는 바람에 이때부터는 정말 미친듯이 문제를 뽑아내야 했습니다. 그래서 제 사무실의 같은 파티션을 쓰는 후임 @asdarwin03을 꼬셔 같이 대회를 운영하기로 하였고, 그렇게 약 한 달동안 두 명이 합쳐서 20문제 이상을 구상한 뒤, 너무 어렵거나 / 컨셉에 맞지 않거나 / 단순히 마음에 안드는 문제들을 모두 버린 뒤 총 14문제를 골라 대회 문제 셋을 어느 정도 마무리해가고 있었습니다. 그런데 그러던 중, 만들었던 문제 중 하나의 N 제한을 늘려도 해결할 방법이 있다는 사실을 깨달았고, 쉬운 버전과 어려운 버전 모두 퀄리티가 괜찮은 문제라고 생각되어 과감하게 문제 개수를 8개로 늘렸습니다. 이때 만들어졌던 문제가 본선 D, H - 이기적인 목봉 체조 문제입니다. 사실 문제 개수를 8개로 늘리게 된 이유가 하나 더 있는데, 그 당시 저는 예선 H - 위문공연 문제의 난이도를 대략 G2~G1 정도의 난이도로 생각했기 때문에 예선 대회가 너무 쉽다고 생각하고 있었습니다. 따라서 예선에 P5 수준의 문제를 하나 추가하고자 했고, 그렇게 나온 문제가 예선 G - 전투기 출격 문제입니다. 문제 번호를 보시면 아시겠지만, 해당 두 문제들은 검수 과정에서 순서가 바뀌게 되었습니다.

3. 군대에서 대회 개최 준비하기

그렇게 16문제를 만들면서, 추가로 해야 하는 작업이 있었습니다. 부대 내 지침 상, 명절 대회를 개최하기 위해서는 적절히 운영되는 동아리가 필요하고, 없던 대회가 새로 만들어지는 과정이었기 때문에 대회 설명 및 진행 계획에 대한 서류를 작성하여 주임원사님께 제출해야 했습니다. 그러나 부대 내 다른 선임분들께 여쭤보아도 동아리를 신설하는 과정을 정확히 알고 계신 분이 없었고, 심지어는 간부님조차도 새로 오신 분이었기에 동아리를 개설하는 과정을 정확히 모르고 계셨기 때문에 맨 땅에 헤딩을 해 가며 동아리를 신설해야 했습니다.

우선, 동아리 담당 간부님께 찾아가서 동아리에 소개를 한 뒤, 동아리 관련 서류들을 제출했습니다. 당연히 서류에 양식따윈 없었기 때문에 대충 인트라넷에 있는 계획서 서류를 하나 가져다가 마개조해서 서류를 그럴듯하게 만들었고, 동아리 계획도 거창하게 적어 내었습니다. 부대 내에 알고리즘에 관심 있는 분들께 동아리 홍보까지 진행하여 동아리 참가자 명단도 작성한 뒤 같이 가져가니, 간부님께서 본인이 나중에 확인해보겠다고 하시며 저를 돌려보냈습니다. 그러고 나서 실제로 동아리가 개설된 것은 이로부터 2달 뒤였는데, 간부님 曰: "그냥 대충 하겠다고 만들어 놓으면 나중에 다시 조사할테니까 동아리 있는셈 치렴" 이라는 말과 함께 개설된 "셈" 치게 되었습니다. 물론 대회를 개최하기 위한 용도로는 이정도도 충분했으므로, 저도 별 말 없이 넘어갔습니다.

다음으로는 대회 소개 및 계획서를 주임원사님께 제출해야 했습니다. 미숙하게 대회 개최를 요청해서 주임원사님의 분노를 사게 되면 대회 개최는 물거품이 되는 것이었으므로, 해당 서류를 작성할 때는 상당히 조심스럽게 작성했습니다. 서류의 양식은 동아리를 만들 때 사용했던 양식을 그대로 사용하여 대회 설명 및 계획서를 작성하였고, 서류를 작성하며 유의했던 점들은 다음과 같습니다.

• 모두가 참여할 수 있는 대회로 만들어야 함 - 명절 대회에 대한 주임원사님의 기조는 "화합" 이었습니다. 즉, 부대원 모두가 화합하고 즐기는 대회가 될 수 있어야 한다는 의미입니다. 비록 알고리즘 대회가 대중적이고 모두가 즐길 수 있는 부류의 대회는 아니긴 하지만, 예선 / 본선으로 나눠 알고리즘 및 프로그래밍을 처음 하는 사람도 충분히 즐길 수 있도록 문제를 출제했다는 내용을 강조하여 서류를 작성했습니다.
• 이게 정확히 무엇을 하는 대회인지 알려야 함 - 당연하다면 당연하겠지만, 주임원사님이 PS 및 알고리즘 대회가 뭔지 아실 가능성은 극히 낮습니다. 그에 따라 알고리즘 대회가 무엇을 하는 것인지 정확히 알릴 필요가 있었기에, 알고리즘 문제가 뭔지에 대해서도 열심히 작성하였습니다.
• 의도가 좋은 의도임을 강조해야 함 - 물론 대회 개최 계기는 "군생활을 빠르기 녹이기 위함", "심심해서" 이긴 했으나, 당연히 그런 식으로 쓰면 대회 개최가 거부될 것이 뻔하기 때문에, 좋은 의도를 강조해야 했습니다. 다행히도 알고리즘 문제 풀이는 단순 오락보다도 "코딩 테스트 연습 및 프로그래밍 실력 증진에 기여"하는 의미가 있으며, 부대 내 많은 병사들이 실제 프로그램을 작성하는 개발병이기에 좋은 의도를 강조하는 것이 그리 힘들지는 않았습니다.

위와 같이 이런저런 많은 점들을 고려하여 대회 개최 계획서를 작성하는 일은 생각보다 힘든 일이었습니다. 애초에 저는 평소에는 이런 일들을 나서서 하지 않는 사람이기도 하고, 당연히 서류 작성도 해 본 적이 없으니 그만큼 서류 작성이 더더욱 힘든 일이었습니다. 더군다나, 서류 제출 후 한 번이라도 거절당하면 지금까지 만들었던 문제들은 전부 먼지가 되어 날아갈 것이 뻔했기 때문에, 서류 작성이 더욱 부담이 되었습니다. 다행히도 부대의 으뜸병사님도 PS에 관심이 있으셨던 분이었기에, 그분께 많은 도움을 받아 가며 서류 작성을 완료했습니다. 특히 주임원사님께 PS가 무엇인지 설명해 가며 직접 설득해주신 덕분에, 보라매컵 대회 개최가 확정될 수 있었습니다.

4. 구상했던 문제 세팅하기

이렇게 대회 개최가 확정되었으니, 구상했던 문제들을 직접 실물로 만들어야 할 시간이 되었습니다. 문제 세팅은 codeforces polygon 플랫폼에서 진행하였습니다. 저는 UCPC에 문제를 출제하며 polygon을 사용해본 경험이 있었기에 큰 무리 없이 문제 세팅을 진행하였으나, 같이 문제를 출제한 @asdarwin03은 polygon 사용이 처음이었기 때문에 제가 이것저것 알려주며 세팅을 진행했습니다.

문제를 출제하신 분들은 모두 아시겠지만, 문제 세팅에 필요한 과정들은 다음과 같습니다.

• 지문 작성 - 당연히 지문을 작성해야 합니다. 지문은 대회 참가자가 보기에 간결해야 하며, 모든 조건들을 명확히 명시해 주어야 합니다.
• generator 작성 - 문제의 테스트케이스를 만들기 위한 generator를 작성해 주어야 합니다. 랜덤한 데이터만으로도 충분히 강력한 데이터를 만들 수 있는 문제들의 경우에는 비교적 쉽게 generator를 생성할 수 있으나, 예선 C - 시간 외 근무 멈춰! 문제와 같이 너무 랜덤으로 데이터를 생성했다가는 대부분의 데이터의 정답이 -1이 되는 문제들이나, 본선 E - 운전병의 딜레마 문제와 같이 틀린 풀이가 많으나 랜덤하게 데이터를 생성하면 틀린 풀이가 정답을 받기 쉬운 문제들은 generator 생성이 상당히 까다로울 수 있습니다.
• validator 작성 - 물론 generator를 제대로 생성했다면 항상 문제에서 요구한 조건대로 입력이 주어지겠지만, 만에 하나 데이터가 틀렸을 경우를 대비해서 validator를 작성해야 합니다. validator 또한 대부분의 문제들은 간단하게 작성할 수 있으나, 일반적인 변수 범위만을 체크하는 것이 아니라, "정답이 존재하는 입력만 주어진다"와 같은 까다로운 경우에는 validator 생성이 상당히 힘들 수 있습니다. 다행히도 (그리고 의도적이게도) 보라매컵에는 validator 작성이 까다로운 문제는 출제하지 않았습니다.
• checker 작성 (special judge의 경우) - special judge를 할 필요가 없다면 사실 따로 작성할 필요는 없으며, 보라매컵에서는 스페셜 저지 문제가 단 하나도 나오지 않았기 때문에 신경 쓸 필요가 없었습니다.
• 정해 코드 및 틀린 코드 작성 - 사실 문제 출제자라면 정해 코드는 간단히 작성할 수 있겠지만(일부 어려운 문제 제외), 틀린 코드의 경우 상당히 창의적이어야 하기 때문에 작성하기 힘든 경우가 많습니다. 가령, DP 문제에 그리디 풀이를 작성한다거나, dfs를 써야 하는 문제에 bfs를 쓰는 등이 있습니다.
• 엣지 케이스 생성 -  off by one, overflow 등을 막는 케이스들을 만들어 주어야 합니다. 

사실 이번 대회의 경우 스페셜 저지 문제도 없었고, 데이터를 만들기 까다로운 문제도 많지 않았기 때문에 상당히 무난하게 문제 세팅 과정이 끝났던 것 같습니다. 다만, 본선 F - 체육대회 문제의 경우는 데이터 만들기가 상당히 까다로웠는데, 문제도 세팅 중간중간 자주 바뀌었던지라 이 문제에만 거의 10시간은 쓴 기분이 듭니다. 실제로 @asdarwin03이 만들고 세팅했던 문제 세개를 제외한 총 13문제를 세팅하는데 거의 1~2주는 걸렸던 것 같습니다. 그래도 UCPC때 한 문제 세팅에 1주일 넘게 썼던 걸 생각하면 싸게 먹힌 편이라 생각됩니다.

5. 대회 운영(?)하기

이렇게 문제를 모두 출제하고 준비를 마친 뒤, 대회를 개최하기 위한 작업을 진행했습니다. 대회를 개최하기 위해선, 반드시 문제를 검수해 주실 검수진 최소 세 분을 모셔와야 하며, 백준 측에 메일을 보내 대회 개최 요청을 보내야 합니다. 안타깝게도 이번 대회는 따로 부대의 지원을 받거나 스폰서가 있던 대회가 아니기 때문에 검수진 분들께 검수비를 지원해 드릴 수 없었습니다. 그렇기에 사실 대회 개최 직전까지는 검수진 분들을 모셔오지 못해 개최 취소가 될까 걱정을 많이 했었습니다. 만에 하나 검수진 분들을 3분을 모셔오기에 실패하면 DomJudge라도 사용해서 대회를 개최해야 하나 걱정이 많았는데, 다행히도 정말 많은 검수진 분들께서 검수진 신청을 해주셨습니다. 이 자리를 빌어, 대회를 검수해주신 검수진 분들께 진심으로 감사드립니다.

아무튼 검수진을 모두 모셔온 뒤, 백준 측에 대회 개최 요청을 보냈습니다. 생각보다 빠르게 관련 회신이 왔고, boj stack 권한이 주어져 대회 4개(예선/본선 및 open contest)의 개최 권한과, 문제 16개의 제작 권한이 주어졌습니다. boj stack은 사용이 상당히 직관적이었으며, 애초에 polygon에서 이미 문제를 모두 세팅해 둔 상태였기 때문에 package를 생성하여 테스트케이스 및 solution, validator를 복붙한 뒤 버튼 몇 개만 누르면 되는 일이라 boj stack에 문제를 세팅하는 것은 별 일은 아니었습니다. 다만, 아직 지문이 완벽히 다듬어지지 않은 상태였기 때문에 검수진 분들께 컨택을 하기 이전에 지문을 다듬는 작업을 진행했는데, 이 작업이 꽤나 오래 걸렸던 것 같습니다.

아무튼 그렇게 지문까지 다듬은 뒤, 검수를 위해 대회 디스코드 서버를 개설했습니다. 사실 대회 운영은 처음이라 어떻게 해야할지 고민이 많았는데, UCPC와 비슷하게 하면 반이라도 가겠지 라는 생각으로 디스코드에서 검수를 진행했습니다. 또, 거의 사용해보지 않았던 엑셀을 조금 손봐서 그럭저럭 괜찮아 보이는 검수 시트를 만들어 해당 검수 시트를  활용하여 검수를 진행했습니다. 검수 시트는 각 사람이 어떤 문제를 검수했는지 체크한 뒤, 체크한 셀에 메모를 달아 난이도, 태그 및 피드백을 작성하는 형식이었습니다.

6. 대회 문제 검수받기

검수 과정에서 가장 많이 지적받았던 문제들은 지문 설명에 관한 것이었습니다. 모든 문제의 지문에 크고작은 오류들이 많았습니다. 기본적인 맞춤법 및 오타부터 심각한 오류까지, 가지각색의 지문 오류들이 있었습니다. 사실 조금 급하게 지문을 작성한 감이 있기도 했고, 지문을 작성해야 할 양부터 심상치 않았기에 어찌 보면 당연한 일이기도 했습니다. 다음 대회부턴 지문 검수부터 꼼꼼히 한 뒤에 검수진 분들을 불러야겠다는 다짐을 할 수 있었습니다. 이 자리를 빌어 잘 이해되지도 않는 지문으로 검수해주신 검수진 분들께 사과의 말씀을 드립니다 ㅠㅠ

물론 지문 관련 오류를 제외하고도, 검수진 분들이 상당히 다양한 부분에서 꼼꼼히 검수를 도와주셨습니다. 가령 예제 부분에서 -1을 출력하는 예제를 넣으면 좋겠다는 의견과, 잘못 작성한 Tex 문법까지 잡아내 주신 분들도 계셨습니다. 그러나 그 무엇보다도 검수에서 중요한 것은 정해가 틀렸는지 여부와, 통과되선 안되는 풀이가 통과되는지, 또는 더 쉬운 풀이가 있는지 여부라고 생각합니다. 다행히도 정해가 틀렸던 문제는 없었지만, 통과되선 안되는 풀이가 통과된 경우도 있었고 조금 더 쉬운 풀이가 있는 경우도 있었습니다. 가령 본선 E - 운전병의 딜레마 문제는 SPFA 및 이분 탐색을 잘못 돌린 코드가 통과하는 문제가 있었고, 본선 H - 이기적인 목봉 체조 (Hard) 문제의 경우 제 원래 풀이와는 다른 풀이로 풀어주신 분이 계셨습니다. 다행히도 더 쉬운 풀이의 난이도도 원본 풀이와 비슷한 수준의 난이도였기 때문에 문제 셋에 큰 변화는 없었습니다.

그 외에도, 검수진 분들이 생각하신 난이도와 출제진이 의도했던 난이도가 다른 경우들도 있었습니다. 가령 예선 H - 위문공연 문제의 경우 출제 과정에서 G1정도 난이도라고 생각하고 출제했으나, 검수진 의견은 P5부터 P1까지 상당히 넓게 분포되어 있었습니다. 오히려 G - 전투기 출격 문제의 난이도가 더 쉽다고 생각하신 분들이 많아 두 문제의 위치를 바꾸게 되었고, 결과적으로는 훌륭한 판단이었다 생각됩니다. 실제로 현제 solved.ac 난이도 기준으로 G는 G1, H는 P4가 찍혀 있네요.

7. 대회 진행하기

예선 본 대회의 경우 크루근무 병사에게 참여의 기회 제공 및 사지방 자리 부족으로 인해 48시간동안 진행되었고, Open contest는 본선 대회와 동일하게 3시간동안 진행되었습니다. 따라서 예선 본 대회에서는 딱히 재밌는 상황들이 많지는 않았습니다. 48시간 내내 대회를 관제하고 있을 수는 없었으니, 가끔씩 접속해서 진행 상황을 구경하곤 했습니다. 본 대회 순위 예상은 8솔브 1명, 7솔브 3명, 6솔브 5명 정도로 예상하고 있었으나 실제로는 6솔브가 최대였습니다. 아마 다들 본선 진출 확정 상태에서는 딱히 열심히 시도하지 않았기 때문이라고 생각합니다. 재밌는 점은, 6솔브한 인원이 6명이었는데, 그중 F번을 푼 인원이 3명, G번을 푼 인원이 1명, H번을 푼 인원이 2명이었습니다. 아무래도 각 문제 유형이 서로 다른지라 이런 현상이 일어났다고 생각됩니다.

예선 Open contest의 경우, 스코어보드가 프리즈되기 전에 무려 두 분이나 All Solve를 하셨습니다. 물론 예선인지라 난이도가 막 많이 높진 않았으나, 그래도 어떻게 이 문제 셋을 2시간도 채 되지 않고 모두 풀 수 있는지는 경이로울 정도라 생각됩니다. 저도 언젠간 저런 수준의 실력을 갖고 싶긴 한데... 조금 너무 목표가 높지 않나 생각도 듭니다.

본선 본 대회는 사지방에서 예선 상위 16명을 추려서 진행했으며, 3시간짜리 대회인 만큼 조금 더 긴장감이 넘쳤습니다. 사실 대회 시간 중에 7문제 이상 풀 수 있다는 생각을 아예 안했기 때문에 제 최대 예상은 6솔브였고, 그마저도 누군가가 컨디션이 극도로 좋은 경우에 6솔브를 할 수 있으리라 생각했습니다. 그래도 D번과 E번이 어느 정도 전형적인 스타일의 문제였기에 5솔브는 충분히 2~3명가량은 나오지 않을까 기대했으나, 안타깝게도 많은 분들이 B번과 C번에서 오랜 시간 뇌절을 경험하며 최고 성적은 4솔브로 나오게 되었습니다.

본선 Open contest에서는 올 솔브가 한 명 정도는 있지 않을까 기대해 보았지만, 안타깝게도 6솔브가 최대였습니다. 다만 놀랐던 점은, 다들 F, G번이 아니라 H번을 풀어서 6솔브를 하셨다는 점이었습니다. F, G번은 대회 중 아무도 풀지 못했고, 특히 G번은 아무도 제출하지 않았습니다. 실제로 검수 중 G번이 H번보다 어렵다는 의견이 있긴 했으나 제가 그 사실을 너무 늦게 인지한 바람에 G번과 H번의 위치를 바꾸진 못했습니다. 아마 다들 H번을 먼저 푼 이유가 D번의 Hard버전이어서 문제 이해가 더 수월한 점과, F번이 풀기 싫게 생긴 유형의 문제여서 그런 것이라 생각됩니다.

문제 진행 중 질문을 통해 지문이 수정된 경우도 있었습니다. 예선 C - 시간 외 근무 멈춰! 문제에서 "평일"의 정의를 따로 하지 않고 평일이라는 말을 썼던 부분을 누군가 질문을 통해 지적해 주셔서, "평일"을 "월요일부터 금요일까지" 정도로 바꾸었습니다. 그 외에는 검수진 분들이 깔끔하게 검수를 해 주신 덕분에, 따로 수정해야 할 정도의 지문 오류는 없었습니다. 다만 예선 본 대회 중에는 심각한 오류가 하나 있었는데, 예선 F - 통신소 문제의 제한 조건을 잘못 적어 놓은 오류가 있었습니다. 해당 문제의 경우 대회 시작 불과 2일 전에 제한 조건을 급히 바꿨는데, 깜빡하고 문제 지문의 제한 조건을 수정하지 않았던 것입니다. 불행 중 다행으로, 수정 시점에 해당 문제의 제출이 많지 않았고, 제출되었던 모든 코드들이 잘못 적혀있던 조건에서도 동작하지 않는 (시간 초과가 나는) 코드였기에 크게 문제가 되지는 않았으나, 절대로 하지 말아야 할 실수였음은 분명한 사실입니다. 앞으로는 절대로 이런 실수 없이 대회 직전까지 검수를 진행해야겠다고 다짐했습니다.

8. 대회 후기

이렇게 준비 기간 약 5개월의 대회가 모두 종료되었습니다. 두 명이서 16문제를 뽑아내려니 아무래도 많이 지칠 수 밖에 없었던 것 같습니다. 또한, 문제 출제뿐만 아니라 운영까지 하면서 조금 더 지쳤던 것 같습니다. 사실 지친 것도 문제지만, 아무래도 군대 안에서 대회를 운영하려다 보니 애로사항이 많았습니다. 특히 컴퓨터를 사용할 수 있는 시간이 적었다는 것이 가장 큰 장벽이었습니다. 대충 밥 먹고 씻으면 7시쯤 되고, 청소 시간인 9시까지 잠깐 사지방에서 컴퓨터를 썼다가 연등 시간인 10시부터 대략 2시간씩, 하루에 4시간 정도의 시간이 있으나 저도 사람인지라 조금의 쉬는 시간정도는 필요하니 평균잡아 하루에 약 3시간정도 사지방을 사용했던 것 같습니다. 16문제를 출제하고 세팅하고 검수하다 보면 아무래도 시간이 금방 가다 보니, 문제 출제 기간 및 검수 기간에는 제 스스로의 공부 시간도 너무 적어지기도 했습니다. 부대원의 알고리즘 공부를 독려하고자 대회를 개최했는데, 대회를 운영하느라 문제 출제진은 공부를 덜 하게 되는 상황이 된 셈이었습니다. 그래도 직접 낸 문제와 유사한 유형의 문제는 확실히 더욱 잘 풀 수 있게 되었다는 것은 부정할 수 없는 사실이지만요. 이제는 대회도 끝났으니 몸을 추스르고 다시 알고리즘 공부에 정진해야겠습니다.

문제를 출제하면서 다시금 느낀 점은, 출제진의 의도 난이도와 검수진의 예상 난이도, 그리고 실제 난이도 간에는 큰 차이가 있다는 점이었습니다. 저는 일반적으로 문제 상황을 먼저 생각한 뒤, 해당 상황에 맞는 풀이를 떠올리고, 상황을 조금씩  확장하거나 수정해가며 문제를 만드는 편인데, 이런 방식으로 문제를 구상하다 보니 제 예상 난이도와 실제 난이도가 상당히 다른 문제들이 생기곤 했습니다. 가령 예선 H - 위문공연 문제의 경우, 당직 근무를 서다가 이리저리 그래프로 장난을 치던 중 우연히 발견하게 된 성질을 토대로 푸는 문제였기에 다른 사람들이 그 성질을 얼마나 쉽게 떠올릴지 도저히 가늠이 안되어 실제 난이도보다 훨씬 낮은 난이도를 예상했었습니다. 또한, 검수진 예상 난이도와 실제 난이도 간의 차이가 있는 경우도 있었는데, 가령 본선 A - 장기자랑 문제의 경우 대부분이 S2 이하로 난이도 예상을 해 주셨으나 현재는 압도적 S1 정도의 난이도로 책정되어 있습니다. 물론 아직 문제가 공개된지 많이 지나지 않아 달라질 수는 있을 듯 싶습니다.

그러나 아무래도 가장 크게 느꼈던 점은, 알고리즘 문제 제작이 굉장히 재밌다는 점입니다. 새로운 문제 아이디어를 생각해 냈을때의 짜릿함은 실제 문제를 풀었을 때의 짜릿함 그 이상이며, 여러 가지 틀린 풀이들을 떠올리고 엣지 케이스를 막아내며 문제를 단단히 만드는 과정은 문제를 풀기만 할 때에는 느끼기 힘든 재미를 가져다 줍니다. 무엇보다도 대회 중에 사람들이 제 문제들을 풀어주고, 제가 의도한 대로 틀려주는 과정을 지켜보는 것이 정말 즐겁습니다. 애초에 ICPC 본선 스코어보드 방송도 즐겨봤던 저이기에, 제가 만든 대회의 스코어보드 및 채점 현황은 정말 3시간 내내 지켜보고 있었습니다. 아무리 문제 제작이 힘들고 지치는 과정이라 하더라도, 이렇게 즐거운 과정이기에 아마 앞으로도 계속 문제를 만들어낼 듯 싶습니다.

다만 알고리즘 문제 제작과 대회 운영은 상당히 큰 차이가 있음도 같이 깨달았습니다. 문제를 제작만 했던 UCPC때와는 다르게, 이번에는 백준 측에 개최 요청 메일도 보내고, 검수진 모집 및 디스코드 서버도 만들고, 홍보 게시판에 글도 올리는 등 해야 할 것들이 다채로워졌습니다. 뿐만 아니라, 군대에서 진행했던 대회였던 만큼 대회를 개최하기 위한 서류작업과 특별 대회 규칙 글 작성, 홍보 글 작성 등의 작업도 해야 했습니다. 이런 작업들은 알고리즘과는 하등 연관이 없을 뿐만 아니라, 제가 저런 작업들을 잘 못하던 사람이기도 했어서 상당히 큰 부담이 되었습니다. 이번 대회를 운영하면서 이런 작업들에 대한 실력이 조금이나마 올랐기를 기대해 봅니다.

9. 문제별 TMI

이대로 글을 끝내기 아쉬워서, 문제 출제 의도부터 여러 해프닝들까지, 대회에 출제된 문제들에 대한 자잘한 TMI들을 모아보았습니다.

예선

A - 특식 배부

출제자: 99asdfg / 출제진 의도 난이도: B4 / 검수진 평균 예상 난이도: B4 / 현재 기준 solved.ac 난이도: B4

출제 의도: 본 대회 참가자 모두가 어렵지 않게 풀 수 있도록, 프로그래밍 지식을 최대한 배제하고 머리를 조금만 써도 풀 수 있도록 출제

예선 B번과 함께 가장 늦게 만들어진 문제 중 하나입니다. 모두가 참여할 수 있는 대회라는 패러다임에 맞게, 첫 문제는 아이디어도 굉장히 쉬우면서 프로그래밍 실력도 거의 필요하지 않은 문제가 필요했고, 그러면서도 단순히 요구하는 내용을 출력하는 수준의 문제는 내기 싫었기에 나오게 된 문제입니다. 적당히 잘 만든 문제라 생각합니다.

B - 출입 기록

출제자: 99asdfg / 출제진 의도 난이도: B1 / 검수진 평균 예상 난이도: B1~S5 / 현재 기준 solved.ac 난이도: S5

출제 의도: 배열을 사용하여 문제를 해결하는 방식 소개

가장 마지막에 만들어진 문제입니다. 의도는 배열을 사용하여 O(N)으로 풀기를 바랬으나, 본 대회에서 정말 많은 분들이 set 및 map 자료구조를 사용하여 해결하는 모습이 마음이 조금 아팠습니다. 그렇다고 N을 늘리기에는 python 사용자 중에 fast input을 하지 않아 억까당하는 사람이 있을까봐 O(NlogN)을 막는 정도로 N을 늘리기는 싫었습니다. 아무래도 "쉬운 문제" 축에 속하려고 낸 문제였기 때문에...

C - 시간 외 근무 멈춰!

출제자: 99asdfg / 출제진 의도 난이도: S4~S3 / 검수진 평균 예상 난이도: S2 / 현재 기준 solved.ac 난이도: S2

출제 의도: 가벼운 그리디 연습 + 간단한 구현 연습

적당한 구현 문제를 만드려던 중 개발 기간이 밀린 동기가 시간 외 근무를 나가는 모습을 보게 되었고, "이걸로 문제 하나 만들어보자"는 생각으로 만들어진 문제입니다. 만들고 보니 구현도 적당히 어려운 정도이고 간단한 그리디도 살짝 들어가는 점이 썩 쓸만해 보여서 채택되었습니다.

D - 잠입

출제자: asdarwin03 / 출제진 의도 난이도: S1 / 검수진 평균 예상 난이도: S1~G5 / 현재 기준 solved.ac 난이도: G5

출제 의도: 문제 상황을 토대로 그리디 판별 + case work 구현

제가 구상한 문제가 아니라 구상 과정은 정확히 모르지만, 문제 초안은 N 제한과 M 제한이 모두 10^9 이하였으며, 그에 따라 입력도 레이저 개수 K를 미리 입력받고 K개의 (y, x, 방향)을 입력받는 방식이었습니다. D번 문제 치고는 너무 까다로운 구현을 요구하는것 같아 보였고, 문제가 이렇게 출제되면 본 대회에서 풀 만한 사람이 너무 줄어들까 우려하여 N 제한을 10^5로 줄였습니다. M 제한도 10^5로 줄이는 것이 어떻겠냐는 의견도 냈으나, 그러면 너무 간단한 시뮬레이션 문제가 되어버리기에 해당 의견은 묵살되었습니다. 예선 대회 중에 가장 큰 통곡의 벽이 된 문제였으며, 본 대회 정답률 17% / Open contest 정답률 19%로 상당히 많이 틀린 문제가 되었습니다.

E - 조교의 맹연습

출제자: 99asdfg / 출제진 의도 난이도: G4 / 검수진 평균 예상 난이도: G4 / 현재 기준 solved.ac 난이도: G4

출제 의도: 웰노운 알고리즘 잘 쓰기

원래 이 문제의 초안은 이런 내용이 아니었으나, 어쩌다 보니 이런 형태로 바뀌게 되었습니다. 제가 만들었던 문제 중 가장 출제하기 싫었던 문제 중 하나였는데, 너무 웰노운이라 단순히 "냅색 알고리즘을 알고 있느냐" 정도의 문제라고 생각되었기 때문입니다. 다만 "그래도 대회에 이런 문제가 하나쯤은 있어야 하지 않을까" 정도의 생각으로 문제 출제를 결심하였습니다.

F - 통신소

출제자: asdarwin03, 99asdfg / 출제진 의도 난이도: G3 / 검수진 평균 예상 난이도: G3~G2 / 현재 기준 solved.ac 난이도: G2

출제 의도: 통곡의 벽 만들기 / 문제를 풀 때 시간 초과를 유의할 것 + 적절한 관찰을 토대로 효율적으로 BFS 돌리기

원래 해당 문제의 출제 의도는 "단순 BFS 구현" 이었고, 단순한 BFS 구현 문제를 만들어줄 것을 @asdarwin03에게 요구하여 만들어진 문제입니다. 초안과 현재 버전이 상당히 다른 문제 중 하나인데, 초기에는 상당히 작은 (N, M) 범위에 대해 "모든 통신소끼리 서로 연결이 되어 있는가"를 물어보는 문제였습니다. 단순히 모든 통신소에 대해 BFS를 돌리면 되는 문제였으나, 제가 의견을 내어 N, M 제한을 늘렸고, 단순히 통신이 가능한 격자점을 세는 문제로 바뀌었습니다. 이 외에도 N, M 제한을 늘리고 "모든 통신소의 세기를 x만큼 올려서 모든 통신소끼리 통신이 가능하도록 만들때 필요한 최소 x"를 구하는 문제의 버전도 존재했으나, 예선에 들어갈 수준의 난이도가 아니었고 처음 문제를 구상했던 출제자의 반대로 인해 현재 버전으로 출제되었습니다.

문제를 만들며 이 문제를 통곡의 벽으로 만들기로 작정하였고, 단순히 Priority Queue를 사용하는 풀이 및 비효율적으로 BFS를 돌리는 등 다양한 풀이들을 막아냈습니다. 결국 Open contest 정답률 18%로 최하위를 달성하여 출제 의도에 정확히 맞는 문제가 되어 주었습니다. 안타까웠던 점은, 고수 분들은 imos법 혹은 좌표 변환 후 2차원 구간 합으로 문제를 해결했는데, 이렇게 되니 너무 단순한 문제가 되어버렸습니다. 아무래도 어려운 버전으로 냈었다면 이런 풀이는 막을 수 있었을텐데 싶은 아쉬움이 남습니다.

G - 전투기 출격

출제자: 99asdfg / 출제진 의도 난이도: G1~P5 / 검수진 평균 예상 난이도: G1~P5 / 현재 기준 solved.ac 난이도: G1

출제 의도: 문제 설명을 토대로 차근차근 해야 할 것들을 쌓아나가는 방식으로 문제 해결하기

예선/본선 대회를 통틀어 풀이 아이디어 먼저 떠올리고 낸 단 두개의 문제 중 하나입니다. 문제 출제 과정에서, 풀이 아이디어를 문제 상황으로 바꾸는 과정에서 실수가 있어 해당 방식이 정해가 아니게 된 사건이 있었으나, 다행히도 외부 검수로 나오기 전에 내부 검수진 선에서 발견되어 문제를 살짝 수정하여 만들어졌습니다.

H - 위문공연

출제자: 99asdfg / 출제진 의도 난이도: G1 / 검수진 평균 예상 난이도: P1~P5?? / 현재 기준 solved.ac 난이도: P4

출제 의도: 머리 열심히 굴려서 풀기...

위의 본 글에서도 말했듯, 당직사관실에서 이런저런 그래프 관찰을 해 보다가 나왔던 문제입니다. 초기 버전은 약 N^2가지의 티켓을 교환하는 방식을 합하는 내용 없이 단순히 총 이동 횟수를 출력하는 문제였으나, 신뢰의 도약으로 단순 순회 후 제출하는 풀이가 반드시 나올 것 같아 급히 문제를 수정했습니다. 티켓을 교환하는 경우가 추가되어 문제가 더 재밌어졌다고 생각됩니다. 관찰이 재밌어서 제가 만들었던 문제 중 유독 애착이 가는 문제 중 하나입니다.

본선

A - 장기자랑

출제자: 99asdfg / 출제진 의도 난이도: S4~S3 / 검수진 평균 예상 난이도: S3 / 현재 기준 solved.ac 난이도: S1

출제 의도: 코포식 애드혹, 조금 생각하다 보면 답이 저절로 나오는 쉬운 문제

실제로 부대에 장기자랑 행사가 있는 것은 아니지만, 있었으면 어땠을까 하고 만들어 본 문제입니다. 만들고 보니 적당히 머리를 쓰면서 구현은 쉬운 종류의 간단한 문제가 나오게 되어 본선 A번으로 출제하게 되었습니다.

B - 영내순환버스

출제자: asdarwin03 / 출제진 의도 난이도: S2 / 검수진 평균 예상 난이도: S2 / 현재 기준 solved.ac 난이도: S1

출제 의도: 뇌절하지 않고 침착하고 빠르게 문제 해결 능력 평가 / 열심히 수학 식 정리 OR 무지성 이분 탐색

초기 의도는 열심히 수식을 세운 뒤 해당 수식으로 각 병사마다 O(1)로 계산하여 해결하는 것이지만, 제가 문제를 보자마자 이분 탐색을 박아서 풀어버려 @asdarwin03이 상당히 슬퍼하는 모습을 바로 앞에서 직관했습니다. 간단히 누적 합을 사용하면서, 수학 식 세우는 과정이 조금은 까다로워 보였기에, 시간을 아껴야 하는 본선 대회에 뇌절하지 않고 코드 짜는 실력을 평가할 수 있는 좋은 문제라 생각되어 채택되었습니다. 실제로 대회 중 본 대회 및 Open Contest 모두 정답률 29%로 많은 분들이 식 세우기에 실수하는 모습을 확인할 수 있었습니다.

C - 조사전달

출제자: 99asdfg / 출제진 의도 난이도: G5~G4 / 검수진 평균 예상 난이도: G4~G3 / 현재 기준 solved.ac 난이도: G4

출제 의도: 문제 거꾸로 생각하기 + 그리디한 방법 고민해보기

대회에 출제된 문제들 중 가장 일찍 만들어진 문제입니다. 실제로 저희 부대에서는 인트라넷 PC의 조사전달 체계를 사용하여 사역을 차출하는데, 그 생각을 하다가 문득 "이거 고장나면 차출은 어떡하나..."라는 생각이 떠올랐고, 바로 문제화시켰습니다. 이렇게 만들어진 문제 치고는 상당히 재밌게 잘 만들어진 문제라고 생각하며, 예선 / 본선 대회를 통틀어 가장 애착이 가는 문제 중 하나이며, 제 기준에서 가장 잘 만든 문제 중 하나라고 생각됩니다.

D - 이기적인 목봉 체조 (Easy)

출제자: 99asdfg / 출제진 의도 난이도: G3~G2 / 검수진 평균 예상 난이도: G4~G3 / 현재 기준 solved.ac 난이도: G4

출제 의도: 간단하지만 너무 간단하지는 않은 DP 문제

문제 출제 후반부에 나온 문제입니다. 출제 후반쯤에는 특정 알고리즘 사용하는 문제를 만들고자 하였는데, 본선 문제셋에 DP 문제가 하나도 없는 것을 보고 본선 D번에는 DP 문제를 놓고 싶었습니다. 다만 DP 문제를 만들기 위해 일부러 만든 문제는 아니고, 만들고 보니 DP여서 정말 행복했던 문제였습니다. N 제한을 늘린 Hard 버전의 문제도 있었으나, Easy 버전의 N 제한의 문제의 퀄리티도 좋았고, Hard 버전과 난이도 차이가 심하다고 판단해 Easy / Hard 버전으로 나누어 출제하게 되었습니다.

E - 운전병의 딜레마

출제자: 99asdfg / 출제진 의도 난이도: G1 / 검수진 평균 예상 난이도: G1 / 현재 기준 solved.ac 난이도: G1

출제 의도: 다익스트라와 이분 탐색 잘 활용하기

다익스트라와 이분 탐색을 동시에 사용하는 문제를 어떨까? 하는 생각으로 냈던 문제입니다. 내고 나서 보니 너무 웰노운 문제같아 보여서 출제하기는 조금 싫었지만, 예선 E번을 출제했을 때와 비슷한 마인드로 출제를 결정하게 되었습니다. 그 대신 시간 제한을 빡빡하게 둬서 다익스트라 구현에 실수가 있으면 시간 초과가 나도록 열심히 데이터를 만들어 두었습니다. 스스로 틀린 코드 약 10개를 만들어 두고 해당 코드를 전부 틀리게 만드는 데이터를 만드느라 꽤나 힘들었습니다. 이렇게 열심히 막았음에도 문제 검수 과정에서 SPFA 코드와 이분 탐색을 잘못 구현한 코드가 뚫리는 바람에, 해당 코드들을 막는데 꽤나 고생했습니다. 아마 문제 데이터를 만드는 과정에서 제일 힘든 문제 중 하나가 아니였나 생각이 됩니다.

F - 체육 대회

출제자: 99asdfg / 출제진 의도 난이도: G1~P5 / 검수진 평균 예상 난이도: G1~P1?? / 현재 기준 solved.ac 난이도: P4

출제 의도: 똑똑하게 완전탐색 하기 / 시간복잡도를 잘 고려하며 코드짜기

Functioncup 2016에 출제된 Baseball Watching이라는 문제를 본 뒤, 브루트포싱 문제도 이렇게 어려울 수 있구나 하는 생각에 만든 문제입니다. 만들다 보니 저 문제보다 훨씬 더러운 문제가 되긴 했지만, 대회에 이런 더러운 문제도 있어줘야 한다고 생각해 출제했습니다. 개인적으로 문제를 만들면서 연산 시간을 최적화하는 과정이 재밌었는데, 입력의 압박이 너무 심해 입력을 바꿀까도 고민해 보았으나 입력을 더 예쁘게 받으려면 문제 자체가 더러워져야 할 것이라 판단해서 지금의 버전 그대로 나오게 되었습니다.

출제 과정에서 가장 문제가 많이 바뀐 문제이기도 한데, 초기에는 실력 제한 최댓값이 20이었고, 팀도 총 3개였으며, 팀당 인원은 12명이었고, 종목은 총 4개였으며, 우승 팀이 되는 조건도 과반 이상의 승리였습니다. 출제 과정과 검수 과정 모두에서 정말 여러 번 바뀐 문제며, 데이터를 만들 때도 polygon의 stress를 활용하여 대부분의 테스트케이스가 만들어졌습니다. 여러모로 만들기 가장 어려운 문제였다고 생각됩니다.

G - MVP 투표

출제자: 99asdfg / 출제진 의도 난이도: P3 / 검수진 평균 예상 난이도: P2~P1 / 현재 기준 solved.ac 난이도: D5

출제 의도: 문제 상황 그래프로 추상화하기 + tree dp 잘 적용하기

의외로 이 문제도 출제 초기에 나온 문제입니다. 다만 그 당시에는 tree dp따윈 쓰지 않아도 되는 문제였으며, 여러모로 더 쉬웠던 문제를 마개조하다보니 현재의 버전으로 완성되었습니다. 처음 아이디어만 생각했을 때는 그다지 어려운 문제라는 생각이 들진 않아 P4정도의 난이도일 것이라 생각했는데, 직접 구현하다 보니 꽤나 빡세다는 것을 깨닫고 예상 난이도를 P3으로 올렸습니다. 검수 의견 중에 G번 문제가 본선 문제 셋을 통틀어 가장 어려운 문제라는 의견도 있었으나, 아쉽게도 해당 의견이 너무 늦게 나와버려 문제 위치를 바꿀 틈이 없었습니다. 실제로 대회 중에 그 누구도 코드를 제출하지 않은 유일한 문제이며, 현재 기준으로도 푼 사람이 거의 없어 solved.ac 난이도도 측정되지 않았습니다. 이번 대회에서 올 솔브가 나오기 힘들 가장 큰 이유로 꼽았던 문제이기도 합니다. 추후 G번 풀이자가 여럿 나오고 난이도가 확정되면 해당 난이도로 수정해 놓도록 하겠습니다.

H - 이기적인 목봉 체조 (Hard)

출제자: 99asdfg / 출제진 의도 난이도: P2~P1 / 검수진 평균 예상 난이도: P2 / 현재 기준 solved.ac 난이도: D5

출제 의도: 여러 자료 구조 잘 활용하기

D번 문제인 이기적인 목봉 체조 (Easy) 문제를 만들고 나서 곰곰히 생각해 보니, 뭔가 N제한이 10만정도로 커져도 풀 수 있을거라 생각되어 열심히 파 보던 중, UCPC에서 제가 출제했던 문제인 대충 카드로 몬스터 잡는 게임과 유사한 방식으로 풀 수 있다는 사실을 깨달았습니다. 따라서 원래 정해의 의도는 lazy segtree에서 set query / sum query / max query를 잘 구현하고, monotone stack을 활용해 쿼리를 적용할 구간을 결정하는 것이었으나, 검수 과정에서 multiset / multimap 및 좌표 압축을 활용하여 문제를 해결할 수 있다는 사실을 깨달았습니다. 또한, 대회 중에는 검수 과정에서도 나오지 않았던 단순 stack만을 사용하여 푸는 풀이로 푸신 분도 계셨습니다. 본선 Open contest중 총 4분이 해당 문제를 해결하셨는데, 다들 서로 조금씩 다른 방식으로 문제를 해결한 모습에 개인적으로 만족했습니다.

이렇게 제가 직접 운영한 첫 대회인 제1회 보라매컵이 마무리되었습니다. 정말 뜻깊은 경험이었고, 앞으로도 다양한 대회에 출제진 및 운영진으로 참가하여 더 질 좋은 문제들을 많이 선보이고 싶습니다.

다시 한번, 이 자리를 빌어 대회를 열정적으로 검수해 주신 보라매컵 검수진 분들께 진심으로 감사드립니다!

길었던 2022년도 드디어 끝이 났습니다. 다사다난했던 한 해였고, 그만큼 또 재밌는 일들도 많이 있었습니다.

이번 글에서는 올 한 해 제가 어떻게 지냈는지 회고해보고자 합니다.

2022년에 있었던 가장 큰 사건은... 당연히 저의 군 입대입니다.

2022년 1월 10일, 저는 대학교 1학년을 끝마치자마자 공군 834기 전자계산병으로 군에 입대하였습니다. 일반적으로 전문연구요원으로 과기원에 다니던 저로서는 사실 그리 뻔한 결정은 아니었는데, 그럼에도 군 입대를 결정하게 된 이유는 다음과 같았습니다.

1. 전문연구요원 선발의 축소: 전문연구요원이 해가 갈수록 인원이 상당히 적어지고 있었습니다. 제가 막 1학년을 다닐때쯤 DGIST의 전문연구요원 선발 제도도 바뀌어 대학원 학점 순으로 선발하는 것으로 바뀐 것으로 알고 있는데, 그 해 컴퓨터과의 전문연구요원 커트라인이 4.1점을 넘었던 것으로 기억합니다. 대학원에서까지 군대에 대한 압박을 느끼기는 싫었기에, 군 입대를 결정하게 되었습니다.
2. 코로나로 인한 FGLP 연기 가능성: 2021년에는 코로나로 인해 해외 유학 지원 제도인 FGLP가 온라인 제도로 바뀌면서 사실상 한 해를 건너뛰었습니다. 물론 오프라인 유학을 지원하는 학교도 있긴 했으나 소수였고, 원하는 학교도 아니었기에 그다지 끌리지 않았습니다. 당시만 해도 코로나가 빠르게 사그라들진 않을 것이라 판단해서 2022년에도 FGLP를 안할 줄 알았습니다만... 2022년에는 FGLP가 정상 진행되었습니다. 그러니 사실 결과론적으로는 아무런 이유도 아니었지만, 그 당시에는 이것도 조금 무서웠었습니다.
3. 불확실한 미래: 물론 가능성은 희박하겠지만, 혹시라도 해외 유학을 가야 한다면? 대학원을 가기가 싫어진다면? 과 같은 고민도 했었습니다. 군대로 인해 제 미래의 경로가 제한되는 것은 싫었기에, 차라리 군대를 갔다 오자는 생각을 하게 되었습니다.

사실 공군을 쓰게 된 계기같은 것들도 쓰고싶은 마음이 있긴 한데 그건 여기서 쓸 글은 아닌 것 같아서... 이유는 이만 줄이겠습니다.

아무튼 이러한 이유로 1월에 빠르게 군입대를 하게 되었지만, 훈련소부터 심상치 않은 기운을 느꼈습니다. 많은 분들도 아시다시피, 2022년 1월은 한국에서 코로나가 갑자기 급증하던 시기였고... 훈련소도 별반 다를 바 없었습니다.

사실 입대하기 전까지만 해도 코로나가 그렇게까지 심하지는 않았습니다. 그 당시 매일 약 3000명정도의 확진자가 나오고 있었는데, 입대 이후 갑자기 증가폭이 가팔라지더니 3월에는 기어코 10만을 넘어버리기도 했습니다.

안타깝게도 훈련소는 코로나에 대한 대비가 충분치 못했던 것 같습니다. 훈련소 2주차에 확진자가 나오기 시작해 훈련을 중단하더니, 그렇게 훈련을 싹다 날려버리고 무한 격리를 시켰습니다. 지금 와서 생각하면 "훈련 안했으니까 꿀 아닌가?" 싶을지도 모르겠지만, 당시 저는 상당히 두려웠습니다. 우선 기본적으로 공군은 훈련을 충분히 받지 못하면 훈련소 유급을 하게 됩니다. 격리 초기에는 훈련소 전체의 격리가 어떻게 이뤄지고 있는지, 확진자가 몇 명이나 나오고 있고 사회에서도 코로나가 심한지 등등 아무런 정보도 얻을 수 없었기에 "우리들만 유급하게 되는건가" 싶기도 했고, 격리 후반기때는 "시험은 그래서 어떻게 보지"같은 생각도 했습니다.

그리고 약 2000명중 거의 1500명 가량 확진이 되었던 834기였던만큼, 저 또한 격리가 끝나가던 시점에 코로나에 걸렸습니다. 코로나 걸린 후기로는 뭐... 생각보다는 더 아프지만 그래도 생각만큼 많이 아프진 않았다는 느낌? 코로나 완치 이후에도 얼마동안 간헐적으로 기침을 하긴 했지만 지금은 더이상 그러진 않으니, 뭐 우려했던 영구적인 후유증은 없긴 했습니다.

아무튼 그렇게 훈련없는 훈련소 생활을 보내고 난 뒤, 원래 특기학교로 가서 특기 학습을 해야 했으나 당시 코로나가 하도 심하기도 하고, 이미 거의 대부분의 특기학교 시설을 격리시설로 사용하고 있었기 때문에 저희들은 특기학교로 가지도 못하고 그대로 자대로 들어가게 되었습니다. 당연히 훈련도, 시험도 보지 못했기에 자대 배치도 3지망까지 선택한 뒤 랜덤으로 돌렸는데, 다행히도 1지망 부대에 당첨되어 좋은 자대로 올 수 있었습니다.

자대에 도착한 후에도 아직 남아 있던 834기의 코로나때문에 834기 전체가 자대에서 모이는 것은 한참 나중에 일이었고, 그렇기에 저 또한 먼저 사무실을 배정받게 되었습니다. 원래는 한 기수의 모든 병사들이 서로 모여 원하는 사무실을 선택하여 배정받으나, 저는 그럴 여건이 되지 않았기에 주임원사님의 지시로 제비뽑기로 사무실을 결정하게 되었고, 또 한번 다행히도 제가 원하던 사무실로 배정받아 개발병이 될 수 있었습니다. 그렇게 저는 원래 하고 싶었던 공군 개발병으로 들어오게 된 것입니다. 그뿐만 아니라, 저와 함께 같은 기수로 입대한 친구 한 명과, 한 달 후임 기수로 입대한 친구 두 명 모두 같은 자대로 배속받게 되었습니다. 자대를 랜덤으로 배정받았던 834기뿐만 아니라, 코로나로 인한 여러 억까들이 혼재했던 835기까지 모두 원하는 자대로 배속받게 된 것은 상당히 놀랍기도 했습니다. 이런 행운들 덕분에, 아직까지도 행복하게 자대 생활을 지속해 나가고 있습니다.

자대 배속 이래로 제가 가장 열심히 하고, 또 가장 중요하게 생각하고 있는 것은 바로 알고리즘입니다. 최근 블로그 글들만 보더라도, 죄다 알고리즘 및 PS로 도배되어 있습니다. 처음 훈련소로 들어갈 때 들고갈수 있는 책 두 권중 한 권을 종만북으로 들고갔었기에, 사실 예견된 미래이긴 했습니다.

사실 원래는 고등학교때 열심히 했던 인공지능을 다시 한번 기초부터 훑는 시간을 가져보려고 했었습니다. 한 달에 논문 한 개씩 읽기라던지... 뭐 그런 것들을 하려고 했으나, 자대 배속 이후 오랜만에 풀었던 알고리즘 문제가 너무나도 재밌었습니다. 실제로 자대 배속받은 당일에 바로 사지방에 가서 5문제나 풀었던 것을 보면, 그만큼 오랜만에 만져봤던 키보드 감촉과 오랜만에 풀어보는 알고리즘 문제들에 흥분했던 것 같습니다.

그렇게 자대 배속 후부터 지금까지 꾸준히, 알고리즘 문제들을 열심히 풀고 있습니다. 실제로 지난 1년간 제 solved.ac 레이팅 변화를 보면, 실력이 비교적 가파르게 올라온 것을 알 수 있습니다. 입대 이전에는 플래티넘 5 초반이었던 제 레이팅이, 어느샌가 다이아 5 승급을 목전에 두고 있는 상황이기까지 합니다.

자대 배속 초기에는 골드 하위권 문제들을 열심히 풀었습니다. 입대 전에도 알고리즘 문제들을 그리 열심히 풀지 않기도 했고, 거의 두 달가량을 계속 격리만 해대니 지능이 상당히 많이 떨어졌었던 것 같았기에 재활훈련 느낌으로 그렇게 풀었던 것 같습니다.

그렇게 조금씩 난이도를 올려가며 골드 상위권에서 플레티넘 하위권 문제들까지 해결해 나가던 중, DGIST 현풍전산에서 개최하는 알고리즘 대회 글을 보아 무작정 신청했습니다. 1등상은 고가의 키보드, 2등상은 마우스, 3등상은 충전기였고, 저는 충전기를 목표로 대회에 참가했습니다. 애초에 대회는 5월이었고, 제가 본격적으로 재활 훈련을 시작했던 것은 3월 중순이었기에 높은 등수를 기대하지는 못했습니다. 그러나 대회 당일, 컨디션이 상당히 좋았었는지 예상치도 못하게 우승을 차지하게 되었습니다. 제 생각보다 적은 인원들만이 대회에 참가했던 것도 작용했겠지만, E번 랜선 연결 문제의 함정을 비교적 빠르게 캐치하여 고쳐냈고, F번 뮤직 플레이리스트 문제에서 상당히 더럽게 짰던 무려 2483B짜리의 코드가 (물론 6번이나 제출하긴 했으나) 정말 다행히도 제대로 돌아갔던 덕분에 우승까지 할 수 있었던 것 같습니다.

그렇게 대회에서 우승을 하게 되어 더닝 크루거 효과의 우매함의 봉우리에 올라갔던 그 때, 우연히 UCPC 문제 출제진 모집 글을 보게 되었습니다. 이전에도 알고리즘 문제들을 직접 출제하고 싶다고 생각했었기에 잠깐 혹하긴 했었으나, 당시에는 사무실 적응 등 여러가지 일들이 많이 겹치기도 했고, 무엇보다도 마감 기한 안에 도저히 문제를 내기 힘들어 보여 문제 출제를 포기했었습니다. 그런데, 5월달에 갑작스럽게 문제 출제진 모집 기한을 연장한다는 글을 보았고, 문제 출제를 준비하기 시작했습니다.

그 당시에 두 문제 가량을 준비해 두었었는데, 첫 번째로 만들었던 문제는 아름다운 풀이가 있으리라 믿고 열심히 구해 보았으나 결국 브루트포스 해법밖에 나오지 않아 자연스레 버리게 되었고, 두 번째로 만들었던 문제는 문제 컨셉이 너무 마음에 들어 해법을 더 파보게 되었습니다. 그러나 그 당시의 저는 실력이 충분치 못했을 뿐만 아니라, 문제의 아이디어가 떠오른 시점이 너무 늦었기에 상당히 더러운 풀이밖에 나오지 않았습니다. 몇 가지 핵심적인 관찰들을 하긴 했으나 그 관찰들을 적절히 사용할 방법을 찾지 못하고, 결국 O(N^2logN) 풀이만을 만들어서 출제진 모집에 제출하게 되었습니다. 이때 마음 한구석에는 비교적 빠르게 O(N^2) 또는 O(NlogN) 정도의 풀이를 운영진 측에서 찾아줬으면 좋겠다는 생각을 했었습니다.

...그리고 그 생각은 현실이 되었습니다. UCPC에 제출했던 문제가 통과되었을 뿐만 아니라, O(NlogN)으로 돌아가는 풀이가 있다는 소식에 정말 기뻤습니다. 과연 어떤 풀이로 O(NlogN) 풀이가 있을지 궁금해 운영 디스코드 방으로 들어간 뒤 바로 확인을 해 보았는데, 생전 처음 보는 알고리즘을 사용하고 있었습니다. 그 풀이 파일을 보았을 때의 충격은 아직도 잊을 수 없습니다. 함수의 단조성을 이용하여 Monotone Queue Optimization을 사용하고, 이를 Persistent segment tree 내지는 Merge sort tree를 적용하면 O(NlogN) 안에 풀린다는 내용이었는데, 당시의 저는 저 알고리즘들을 전부 다 몰랐었습니다. 당장 기본 세그먼트 트리도 배운지 얼마 되지 않았던 시점이었고, 레이지 세그트리도 출제 후에야 공부했었던 저였기에 위 내용들은 충격적일수밖에 없었습니다.

그래서 풀이 파일을 본 뒤로 바로 Monotone Queue Optimization 내지는 segment tree 공부를 시작했습니다. Monotone Queue Optimization은 솔직히 처음 봤을때 "이게 대체 무슨 소리지" 싶은 느낌이었고, 상당히 오랜 시간 해당 알고리즘을 이해하는 데 소모했었습니다. 구사과님의 블로그에 작성되어 있던 동적 계획법 최적화 글은 휴가 나가는 중에도 읽을 정도로 여러번 읽었으나, 당시의 저는 DP 혐오자라 불릴 정도로 DP를 못하는 사람이었을 뿐만 아니라(당장 제 문제의 O(N^2) DP 풀이도 못찾아서 요상한 풀이로 제출했었습니다), 실제 동작하는 코드를 본 적이 없었기 때문에 정확히 어떤 식으로 코드를 작성해야 할지도 감이 안잡혔습니다. 그래서 저는 바로 DP 특훈에 들어갔고, 그 당시 매일마다 사지방에서 DP문제를 적어도 하나씩은 풀었던 것 같습니다. 또, 구사과님의 블로그에 예제로 올라와 있던 문제에서 구사과님의 코드를 어떻게든 찾아내어 읽어보고 구현을 어떻게 해야 하는지 감을 잡았습니다.

그렇게 사용되는 알고리즘들에 대한 공부를 어느 정도 끝냈으나, 아직 고비는 남아있었습니다. 당연하게도 문제 출제가 처음이었던 저는 codeforces polygon 및 boj stack 등 문제 출제에 필요한 도구들의 사용법을 아예 모르고 있었고, 이것들에 익숙해질 시간도 필요했습니다. 아무래도 이런 도구들을 처음 사용하다보니 문제 세팅도 상당히 오랫동안 하게 되었습니다. 애초에 예상 난이도가 다이아몬드 수준인 문제였기에, 당시에도 플레티넘 문제들을 제대로 풀지 못하던 저에게는 정해 코드 작성 또한 고역이었습니다. 중간에 공동출제자인 functionx님께 정해 코드 작성을 맡길까도 고민해 보았으나, 한 문제밖에 출제하지 않은 제가 그 문제에서조차 정해 코드를 작성하지 않으면 너무 하는게 없을 것 같아 어떻게든 코드를 짜내어 정해 코드를 작성할 수 있었습니다. (지금 와서 말하는 것이지만, 당시 거의 1주일동안을 정해 코드 작성에만 쏟았던 것 같습니다...)

그렇게 순조롭게 출제가 진행되던 도중, 누군가 "이거 레이지세그 DP로 되겠는데요"라는 의견을 냈고, 실제로도 그랬다는 사실을 깨닫게 되었습니다. 해당 풀이로는 Monotone queue optimization과 merge sort tree가 아예 필요하지 않았고, 더구나 해당 방법이 시간도 훨씬 빠르게 돌아갔기에 정해 풀이는 레이지세그 DP쪽으로 바뀌게 되었습니다. 또, 카드 게임에 관한 내용이었기에 지문에서 카드 게임의 이름이 필요했습니다. 원래는 UCPC 비스무리한 약자로 게임 이름을 지으려다가 도저히 생각이 안나서 디스코드 방에 추천을 받았었는데, doju님이 "대충 카드로 몬스터 잡는 게임"이라는 이름을 제안하셨고 이게 상당히 마음에 들어서 문제 제목까지도 게임 제목으로 짓게 되었습니다. 그렇게 해서 출제된 문제가 UCPC 2022 본선 F - 대충 카드로 몬스터 잡는 게임입니다.

마음같아서는 저도 본선 대회장에 나가서 온사이트 대회 구경도 하고 여러 경품들도 받아오고 싶었지만, 휴가 일정에 맞지 않아 UCPC 대회장에 직접 가보지는 못했습니다. 올해는 출제진으로든, 참가자로든 대회장에 가볼 수 있었으면 좋겠습니다.

UCPC가 끝난 뒤, 정말 많은 것들을 느꼈습니다. 특히, 제 실력이 아직 너무 모자라다는 것을 뼈저리게 느꼈습니다. 언젠가는 ICPC 본선도 가보고 싶고, 언젠가는 UCPC 본선도 가보고 싶었던 저는 직접 UCPC 대회를 운영하며 지금 이 상태로는 절대로 본선 진출은 못하겠구나 싶은 마음이 들었고, 그때부터 더욱 열심히 알고리즘 공부에 매진했던 것 같습니다. 그때쯤부터 푸는 문제의 난이도도 올리고, 여러 알고리즘들을 배웠으며, 공부하는 방식도 조금 바꿨습니다. USACO 문제와 같이 풀이가 공개된 대회의 문제들을 풀다가 1시간이 넘어가면 그냥 풀이를 본 뒤 다음주쯤에 다시 도전하는 방식으로 공부 방식을 변경했고, 이전까지는 그냥 재미로 문제들을 풀었다면 이때쯤부터는 실력을 올리고 싶다는 마음으로 공부했던 것 같습니다. 실제로 이 방식은 꽤나 잘 먹혀들었고, 그 덕에 7월 중순부터 10월 초까지 꽤나 가파른 실력 향상이 있었습니다.

UCPC가 끝난 뒤에 느꼈던 다른 점은, 알고리즘 문제 출제가 상당히 재밌다는 점이었습니다. 사실 중학교 3학년때 PS를 처음 시작하던 시절부터 알고리즘 문제를 출제하고 싶다고 생각해 왔었는데, 실제로 해보니 생각보다 문제 출제 과정이 더욱 재밌었습니다. 그래서 UCPC가 끝난 뒤에 다른 대회에서 출제진을 구하고 있나 살펴보았으나, 딱히 문제 출제진을 구하는 글들이 없었습니다. 그러다가 문득 "부대 내에 알고리즘 대회를 개최하면 어떨까?" 싶은 생각을 하게 되었고, 8월쯤부터 천천히 준비하기 시작했습니다. 일반적으로 명절때 부대 내에 여러 행사가 진행되는데, 2023년 설날을 목표로 대회 개최를 준비한 것입니다. 그리고 이 대회는 아직 개최되지 않았으므로, 이 다음 내용들은 추후 대회가 개최된 뒤에 따로 후기를 작성하겠습니다.

아무튼 이로 인해 2022년의 후반기는 거의 대부분이 대회 개최 준비로 가득 찼습니다. 공동 출제진인 제 친구와 예선 / 본선 8문제를 각각 구상하고, polygon에 세팅하는 일반적인 준비뿐 아니라 부대 내 알고리즘 동아리 개설, 대회 개최를 위한 문서 작성 등 여러 준비들을 하며 시간을 보냈습니다. 지금 생각하면 정말 정신없이 지나갔지만, 오히려 그 덕분에 군생활이 빠르게 녹았던 것 같습니다.

또 다른 주요 사건으로는 2022 ICPC Seoul Regional Mirror Contest에 참여했던 것인데, 이 내용에 대해서는 이미 후기를 작성했으므로 링크로 대체합니다. 비록 미러 대회긴 했지만 정말 즐거운 경험이었고, 전역하고 나면 반드시 ICPC 본선에 나가리라는 다짐을 하게 된 좋은 경험이었습니다.

그리고 이렇게 2022년이 끝이 났습니다. 막상 이렇게 적어 두니 생각보다 많은 일이 없었나? 싶다가도, 무려 지금까지 4달가량동안 준비한 대회에 대한 내용을 자세히 쓸 수 없으니 당연하다는 생각도 듭니다.

이렇게 2022년 회고록을 작성하다 보니 올해의 목표도 자연스레 떠오르는 것 같습니다. 올해 꼭 하고 싶은 리스트를 작성해 보자면...

1. UCPC 온사이트 대회 참여: 출제진으로든 참가자로든 올해 안에 UCPC 대회장을 가보고 싶습니다. 오프라인으로도 고수분들을 만나며 더 큰 자극을 받고 싶은 마음도 있고, 오프라인 대회장의 분위기도 한번쯤은 느껴보고 싶습니다.
2. Codeforces 퍼플 달성: 사실 2022년 목표였으나, 군대 내에서 코드포스 대회를 치루기가 시간 관계상 상당히 힘든 탓에 최근 거의 대회를 참가하지 못하고 있습니다. 사실 개인적인 욕심은 오렌지 달성이긴 한데, 군대에 있는 만큼 최대한 보수적으로 잡았습니다. 물론 그래도 2000점정도는 되어야 하지 않을까 싶은 욕심은 버릴 수 없긴 합니다.
3. 여러 대회 개최 및 검수: 부대 내 대회뿐 아니라, 더 다양한 대회들에서 문제를 출제하거나 검수를 하고 싶습니다. 물론 검수를 위해서는 일단 위의 Codeforces 퍼플 달성 목표부터 달성하긴 해야겠지만... 문제 출제와 검수 모두 즐거운 경험이고, 검수 과정에서 틀린 풀이를 생각하거나 시간 초과 풀이를 생각하는 등의 과정에서 공부에 큰 도움이 될 수 있으리라 생각합니다. 실제로 이번 대회의 문제를 출제하면서, 제가 냈던 문제 유형의 다른 문제들이 훨씬 더 풀기 쉬워졌던 것 같습니다.
4. 몸 성히 전역: 2023년 10월 9일은 온다...!!!

2023년 한 해도 2022년처럼 즐거운 한 해가 되면 좋겠고, 더욱 성장하는 한 해가 되도록 노력해 나가야겠습니다.

P3 | 4243 - 보안 업체

풀이 시간: 30분 + 극한의 뇌절

시도 횟수: 2회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

여담: "n은 100... t는 1500000이니까..? nt=15억? 음 최댓값은 INT_MAX로 박아도 되겠군!"..... 풀고 나서 내가 틀렸나 하면서 식을 이리저리 살펴보며 코드 잘못짠거 있나 계속 돌려보고 논리가 틀렸나 하고 이것저것 확인해봤는데... 반례도 이것저것 넣어보면서 손으로 해보면서 뭐가 틀린 부분이 있나 해봤는데..........

P5 | 2150 - Strongly Connected Component

풀이 시간: X

시도 횟수: X

체감 난이도: X

풀이 쓸 의향: X

풀이

여담: 플3랜디를 몇번 돌려봤는데, 이제 슬슬 새로운 알고리즘들을 배워야 할 시기인것 같아서 SCC / 2-sat / LCA / sparse table / MCMF 공부를 시작해보려고 한다.

P4 | 5461 - 고용

풀이 시간: 굉장히 오랜 시간

시도 횟수: 굉장히 많은 횟수

체감 난이도: P3

풀이 쓸 의향: 中

풀이

여담: "만약 고용할 수 있는 노동자의 수가 같다면, 노동자들에게 최소 비용을 지급하는 고용 방안을 원하며"... 이걸 못봐서 다 풀어놓고 대가리박고 있었다.

P3 | 11873 - 최대 직사각형

풀이 시간: 30분 + a (예전에 풀다 때려쳤던 경험 있음)

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

여담: 예전에 이 문제 봤을때는 2차원 구간합 구현해놓고 "이걸 어케 풀어;"하면서 던졌었는데, 다시 보니까 바로 "그 문제" 삘이 나서 바로 풀었다.

P3 | 20945 - 의자 게임

풀이 시간: 1시간 + a

시도 횟수: 2회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

여담: 처음에 아예 틀리게 생각했었는데, 그 풀이에서 조금씩 뻗어가면서 풀이에 접근해갔다. set 안쓰고 무지성 n^2으로(미쳤었던듯) 제출했다가 TLE 한번 뜨고, 다시 set으로 구현해서 AC.

P3 | 23834 - 커여운 키위

풀이 시간: 45분?

시도 횟수: 2회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

여담: segtree + dp 유형의 문제. 태그를 보니까 덱을 이용한 dp라고도 하던데... 세그트리가 참 만능인듯 싶다.

P4 | 2532 - 먹이사슬

풀이 시간: 약 30분

시도 횟수: 4회 + 1회 (992ms로 통과한 뒤에 좌표압축 다시 구현해서 제대로 풀었음)

체감 난이도: P3 하위권

풀이 쓸 의향: 中

풀이

여담: 시즌 292148호 태그랑 딴판으로 문제풀기 성공! 문제 풀다가 "이거 lis 비슷하게 될것 같은데...?" 싶다가 갑자기 세그트리 풀이로 틀어버렸다.

군대에서 후임, 동기와 함께 ICPC Seoul Regional Mirror Contest에 참가했습니다.

원래 팀명을 부대 이름으로 할까 고민했다가, 그냥 별 의미 없는 이름으로 지었습니다.

군대 입대 이후로 살면서 가장 열심히 PS를 하고 있고, 전역하고 나서 24년도 ICPC Regional에 반드시 참가하겠다는 의지로 올해 ICPC Mirror에 참가했습니다.

팀원은 부대에서 PS를 잘하는 사람을 모아온 것이 아니라, 그냥 저랑 친한 친구 두 명(@terabyte, @asdarwin03)을 불렀습니다.

팀 대회는 고등학교 시절 2인으로 치뤘던 에리카 대회를 제외하고는 한 번도 치뤄본 적이 없었기 때문에, 높은 등수가 목표라기보단 단순히 팀 대회를 해보고 싶어서 친한 친구들끼리 진행했습니다. 그래서 팀 노트도 없이 그냥 대회를 진행했습니다.

당연히 세 명 모두 부대 안에 있었기 때문에, 사지방에서 대회를 진행했습니다.

다른 사람들도 사용하는 공공장소이기에 컴퓨터 하나를 잡고 세 명이 모여서 앉기도 힘들었고, 서로 이야기하기는 더더욱 힘들었기에 대회 전에 대안을 생각해 두었습니다.

우선 대회 로그인은 제가 해 두고, discord를 통해 대회 시작과 동시에 문제를 전송했습니다. 세 명이 서로 컴퓨터를 잡고 고민하다가, 풀이가 생각나면 "이제 코딩 시작한다" 라는 멘션을 보낸 뒤 코드를 짰고, 그 동안 다른 사람들은 코드를 짜지 않기로 했습니다.

서로 말도 못하므로 거의 대부분의 대화는 discord 메시지를 통해 진행됐습니다. 점심 시간에나 같이 밥을 먹으며 대화를 나누고자 했으나, 밥을 먹을 타이밍쯤에는 안타깝게도 별로 논의할 내용이 없었어서...

또, 스코어보드도 제가 가끔씩 보면서 캡쳐로 보내주는 방식으로 봤었습니다. 제가 스코어보드를 보면서 풀만한 문제들을 색출하고 친구들에게 던져주는 역할을 했습니다.

이번 대회 목표는 크게 두 가지였습니다.

1. 세 명 모두 적어도 한 문제씩은 풀자 : 제가 부른 친구 둘은 사실 저만큼 PS를 열심히 하는 친구들은 아니었고, 사실상 제가 미러 대회 쳐보고 싶어서 강제 차출 수준으로 불렀습니다. 그 상태에서 제가 쉬운 문제라고 전부 다 풀어버리면 당연히 두 명은 재미가 없을 것이므로, 세 명이 한 문제씩은 풀 수 있도록 노력하기로 했습니다. 제가 스코어보드를 보니, 쉬워보이는 문제들을 친구들에게 넘기고 저는 어느 정도 난이도 있는 문제를 풀기로 했습니다.
2. 플레티넘 중상위 문제를 적어도 한 문제는 풀어내자 : 최근 USACO를 중심으로 플래티넘 중상위 랜덤 디펜스를 열심히 하고 있었는데, 풀면서도 "내가 대회 중에 이 정도 난이도를 풀어낼 수 있을까" 하는 걱정이 컸습니다. 플랜디 중에는 난이도가 보이지만, 대회장에서는 문제 난이도가 안보이니 풀어내기 더 어려울 것 같았습니다. 그리고 제가 최근 열심히 문제를 풀었던 결과물을 (미러긴 하지만) 대회에서 실제로 보고 싶었습니다.

3초간의 마라톤 회의 끝에, terabyte는 ABCD, 저는 EFGH, asdarwin03은 IJKL을 보기로 했습니다.

다음은 대회 타임라인입니다.

대회 시작 타이밍에 Contest Delayed가 뜨길래 잠시 기다리다가, 00:02에 접속이 되는것을 확인하고 즉시 ICPC 홈페이지에서 본선 문제를 다운로드받아 전송했습니다.

E번 문제를 봤는데, 처음에는 상당히 어려워 보였습니다. $m \leq 10n$이라는 조건을 못봐서 이 문제는 답이 없다 생각하고 빠르게 F번으로 넘어갔습니다.

F번 문제를 읽어봤는데 간단한 문제같아 보였습니다. 풀이를 생각해보진 않았지만 단순히 path에 있는 거리 계산을 구현하기만 해도 풀릴 것 같았습니다, 바로 팀원들에게 문제 다 보고 풀거 없으면 F번 보라고 일러두고 다음 문제를 읽었습니다.

G번은 보자마자 제가 풀 문제가 아니라 생각하고 던졌고, H번은 제가 아직 제대로 공부도 하지 않은 문자열 문제이길래 바로 던졌습니다. 이렇게 10분만에 제가 봐야할 문제를 다 보고 다른 문제들을 살펴보다, asdarwin03이 I번 문제가 LCS nlogn으로 풀릴 것 같지만 알고리즘 구현 기억이 안난다면서 저에게 I번을 던졌습니다.

안타깝게도 저도 LCS nlogn 풀이를 외우고 다녔던 것은 아니라 문제를 찬찬히 읽고 있었는데, $k=0, 1, 2, 3$이라는 조건으로는 투 포인터 및 백트래킹으로 풀릴 것 같아 보였습니다.

그렇게 바로 I번 구현에 들어갔고, AC를 받았습니다.

00:20 I AC

풀자마자 terabyte가 B번 문제가 구현 문제인것 같다며 구현을 시작했고, asdarwin03은 J번이 단순 그래프 BFS 구현 문제인것 같다고 합니다. terabyte가 아직 C, D번 문제를 안봤다길래 C, D번 문제를 읽어봤습니다.

근데 C번은 보자마자 빡센 기하학 문제같아 보여서 바로 걸렀고, D번 문제를 읽었습니다.

D번 문제는 그래도 할만해 보여서 해당 문제를 이리저리 생각해 보고 있었습니다. 그리디로 풀리나 싶어서 고민하던 중, 문제 상황 추상화 중에 terabyte가 5분만에 코드를 짰다고 코드를 줬지만, 스코어보드에는 아무도 B를 풀지 못한데다 예제에서도 틀리는 코드였기에 바로 B번을 버리고 F번을 보라고 말해줬습니다. 그 즉시 asdarwin03이 J번 구현을 시작했고, 2분만에 코드를 짜서 제출했지만 틀렸습니다. 코너 케이스를 처리하지 않은 것 같다며 코드를 다시 짜다가 10분쯤 뒤에 도움을 요청했는데, 코너 케이스 문제가 아니라 답이 long long 범위인데 int를 써서 틀렸던 것이었습니다. int를 long long으로 바꿔서 다시 제출했고, AC를 받아냈습니다.

00:32 J WA

00:47 J AC

J AC 코드를 작성 중에 terabyte가 F번이 단순 구현이라며 손코딩을 시작했고, J AC를 받은 뒤 구현에 시작하여 약 10분 뒤 F도 AC를 받아냈습니다.

00:59 F AC

이 시점에서, 이미 목표 1.은 달성했습니다. 이때쯤 스코어보드를 한번 캡쳐해서 보내줬습니다. 남은 문제들 중에서 K, D, E 순서로 많이 풀렸었는데, D는 원래 terabyte의 문제였으므로 가서 문제에 대해 알아낸 내용을 설명해줬고, K, E 중 어떤걸 asdarwin03에게 줄까 고민하다가 그래도 K가 더 많이 풀리기도 했고, 제가 원래 E번을 보는 거였으니 제가 E번을 보고 asdarwin03이 K를 보기로 했고, 문제만 대충 읽은 뒤 밥을 먹으러 갔습니다.

밥을 먹기 전에 E번 문제를 보던 중 문제 제한에 $m \leq 10n$인 것을 발견하고, 그럼 대충 구현해도 맞지 않을까 싶어서 생각해 보니까 충분히 가능해 보였습니다. 플레 하위권 정도의 구현이 필요해 보였고, 제가 풀기로 생각했습니다. 다만 밥을 좀 천천히 먹는 바람에 약 40분 가량을 날렸고, 밥을 먹고나서 바로 구현해서 10분만에 AC를 받았습니다.

02:04 E AC

사실 밥을 조금만 더 빨리 먹으면 좋았겠다 싶긴 했지만, 대충 플레 하위권 그래프 문제를 하나 풀었다는 점에 만족하고 넘어갔습니다. 다만 약간 물플레 수준 아닌가 싶은 난이도였어서, 목표 2.를 성공했다고 보기엔 조금 애매했습니다.

그 타이밍에 본선 스코어보드를 봤었는데 본선 38등 수준의 점수였습니다. 물론 대회장과 환경이 다르므로 곧이곧대로 비교하긴 힘들겠지만 사실상 제가 끌고온 멤버를 데리고 이정도 성적을 냈다는 점에 상당히 만족했습니다.

E번을 풀고 나서 terabyte에게 D번에 대한 조금 더 자세한 내용을 들었는데, 문제를 추상화한 결과 "수열에서 연속한 부분을 적절히 합쳐서 증가 함수를 만들었을 때 함수의 최댓값의 최솟값을 찾아라" 였습니다. 최댓값을 인자로 갖는 Parametric Search가 가능할까 생각해봤으나 증가 함수여야 한다는 조건을 맞추기가 힘들어 보여서 일단은 terabyte에게 넘기고, L번 문제를 살펴봤습니다.

이 과정이 조금 복잡하게 돌아갔는데, discord로 소통을 하다 보니까 이것저것 많이 섞여버렸습니다. 제가 L번 문제를 생각하던 도중 terabyte와 D번에 관한 내용을 논의하고, 그러면서 asdarwin03에게 K번이 DP 문제일것 같다는 이야기를 들었습니다. L번 문제는 크기 3 이상의 동일한 크기의 서로 다른 사이클 두 개를 찾으라는 문제이므로 tree dp를 사용해 풀 수 있을것 같아 dfs로 구현하다가 중간에 구현이 꼬여버리는 바람에 약 30분동안을 날려버렸습니다. 그 와중에 asdarwin03이 K번 문제를 구현해보겠다고 해서 자리를 비켜주고, terabyte가 D번을 포기하고 C번을 보겠다고 선언해버려서 일단 L을 버리고 제가 다시 D번을 보기 시작했습니다. 이때쯤 든 생각은, 우리가 풀 수 있는 최대는 DEFIJKL으로 총 7문제라고 생각했습니다.

그렇게 30분이 지나고, asdarwin03이 구현하다 중간에 막혀서 다시 메모장 모드로 들어갔고, C번을 보던 terabyte는 빠른 포기 후 asdarwin03과 같이 K를 보기 시작했습니다. 저는 D를 보겠다고 했으면서 L번에 미련을 못버리고 L번에 집착하고 있다가, 원래 생각했던 방식이 완전히 틀렸다는 것을 늦게 파악하고 다시 D로 돌아갔습니다. 그러던 중 풀다가 정신이 나가버린 나머지 한 번을 그냥 약간의 최적화를 거친 O(N^2) dp 코드를 신뢰의 도약으로 던졌다가 어림도 없이 TLE를 받고, 약 10분 뒤 정신을 차리고 식 정리를 끝마쳐 D번을 맞았습니다.

04:36 D WA

04:45 D AC

전 이때쯤 K번에서 좋은 소식이 들려올 줄 알았지만, 안타깝게도 두 친구 모두 K번을 푸는 데 실패하고 말았습니다. 저도 마지막 15분동안 K번에 도전해봤지만, 결국 실패하고 예제에서도 틀리는 asdarwin03의 K번 코드 제출을 마지막으로 대회가 끝났습니다.

이렇게 총 5 Solve로 대회를 끝마쳤습니다. 실제 대회장에서 이 정도 성적이었으면 45등의 성적이네요.

대회를 치면서 느껴졌던 아쉬웠던 부분들은,

1. 너무 산만했다 : 대회 환경을 말하는 것이 아니라, 너무 여러 문제들을 동시에 봤던 것 같습니다. 실제로 중간에 E번을 풀고 난 이후로 어떤 문제를 잡아야 할지 갈피를 못잡아서 K번을 보다가 L번을 보다가 D번으로 돌아간 뒤에 다시 L번으로 갔다가... 물론 결국 D번을 풀긴 했지만, 한 문제씩 고민을 했더라면 K번까지는 풀 수 있지 않았을까 하는 아쉬움이 남습니다.
2. 서로 소통을 잘 못했다 : 사지방에서 대회를 쳤던 거라 서로 말을 못했던게 좀 아쉬웠습니다. 디스코드로는 소통하는 데 제약이 있었고, 물론 기록하는 용도로는 괜찮았으나 결국 채팅을 치느라 꽤 오랜 시간을 보냈던 것 같습니다. 실제 대회 환경에서는 어떻게 소통하게 될지 감을 아직 잘 못잡겠습니다.
3. K번을 결국에는 못풀었다 : 이건 사실 제가 아쉽다기 보다는 같이 대회를 치뤘던 asdarwin03과 terabyte가 좀 아쉬울 것 같았습니다. 특히 asdarwin03은 본인의 원래 실력보다 더 낮은 성적을 얻은 것 같아 더 아쉽습니다.
4. L번에서 뇌절을 너무 심하게 했다 : 이건 1. 너무 산만했다 의 결정적인 원인이기도 했는데, 제가 좋아하던 그래프 문제에서 그렇게 뇌절을 때려버린 것이 조금 많이 아쉬웠습니다.

전 원래 목표였던 1. 세 명 모두 한 문제씩은 풀자 는 성공했고, 2. 플래티넘 중상위 수준의 문제를 풀어내자 또한 E번과 D번을 풀어내며 성공했습니다. 사실 큰 기대 없이 치뤘던 대회였던 만큼 5솔브라는 꽤나 괜찮은 성적에도 만족하고 있습니다.

다만 앞으로 더 실력을 쌓아야겠다는 생각도 들었습니다. 이번 대회에서 이상적인 성적은 L, K까지 풀어내면서 7솔브를 하는 것이었는데, D, L에 시간을 너무 쏟아 실패했다는게 많이 아쉬웠습니다.

내년에도 저는 군대에 있을 예정이기에 ICPC 본선에 직접 출전은 못하겠지만, 다음 ICPC때까지 ICPC 리저널 본선에 나오는 플래티넘 수준의 문제는 무조건 풀 수 있는 실력까지 끌어올리고 싶습니다.

P4 | 3043 - 장난감 탱크

풀이 시간: 30~40분

시도 횟수: 3회

체감 난이도: P4 하위권

풀이 쓸 의향: 下

풀이

여담: 동일한 칸에 겹치는 탱크를 고려 안해서 -1, push_back(y)자리에 (x) 집어넣어서 -1... 복붙하다 실수했다..

P3 | 1523 - 종점

풀이 시간: 25분

시도 횟수: 1회

체감 난이도: ??

풀이 쓸 의향: 下

풀이

여담: 사실 난이도 플레 랜덤으로 슬쩍 가리고 풀었는데... 풀고 나서 이게 이 난이도가 맞나 싶었던 문제. 경험상 이런 생각이 들던 문제들은 보통 다른 사람이 기여했던게 맞았어서 난이도 기여에서는 손 뗐다.

P4 | 1604 - 도망자 원숭이

풀이 시간: 약 1시간

시도 횟수: 2회

체감 난이도: P4

풀이 쓸 의향: 下

풀이

여담: 플로이드-워셜 알고리즘이 어떻게 동작하는지 다시 찬찬히 이해해본 다음에야 풀 수 있었던 문제. 훌륭한 문제인듯.