1편을 먼저 읽고 오는 것을 추천한다.
4. 예선 이후 준비 과정
예선 이전까지 하루에 골드 이상 문제를 10개씩 풀며 지속가능한 공부량을 늘리는 데 성공했다. 이제 이 공부량을 유지하면서 조금 더 어려운 문제들을 푸는 연습을 해야 한다. 예선 전까지는 골드~플레티넘 중하위 문제들을 많이 풀며 저점을 높였다면, 이제는 플레티넘 상위~다이아몬드 문제들을 풀며 고점을 높일 때이다.
전부터 예선 이후로는 이렇게 해야 한다고 생각하기도 했지만, 예선의 결과로부터 이제 저점은 높지만 고점은 아직 부족하다는 것을 확인했기 때문에 더욱 이런 공부가 필요하다는 확신이 들었다.
예선 이후 한 달 동안 그냥 문제를 주구장창 풀었다. 난이도는 플레티넘5~다이아몬드3 사이가 대부분이었고, 문제들은 다양한 사람들이 만들어놓은 문제집에서 뽑아 Python의 list에 모아놓고 랜덤으로 하나씩 뽑았다. DP, 애드혹, 세그먼트트리, 트리DP, Network Flow 등 각 주제별 문제집에서 원하는 난이도의 문제들을 뽑아 넣었다. 문제집 검색에서 찾은 것들도 있고, 그룹 비공개 문제집에서 넣은 것들도 있다. 이렇게 하면 태그 문제집의 문제들을 풀면서도 문제를 볼 때 태그를 스포당하지 않을 수 있어 좋은 것 같다.
이것은 이제까지 골드 문제만 많이 풀었기 때문에 어려운 문제 푸는 감을 다시 잡는 동시에, 하루에 어려운 문제 여러 개를 큰 힘 들이지 않고 풀어낼 수 있는, 소위 말하는 '체급'을 키우기 위함이었다. 체급을 키우고 나야 더 많은 지식들을 힘들지 않게 공부할 수 있다고 생각하기도 했다.
문제를 풀다가 모르는 개념이 필요해 보이면, 그 개념을 공부한 뒤 문제를 풀었다. 또한 공부한 개념에 해당하는 백준 문제집을 찾아서 그 문제들을 list에 추가하여 그 개념을 쓰는 문제에서 랜덤문제뽑기에서 나와 풀 수 있게 했다.
예선 이후에 처음 공부한 것들은 HLD, Dynamic Segment Tree, Li-Chao Tree, DnC Optimization, FWHT, SOS DP, 트리압축, 트리동형, Segment Tree Beats, MCMF, Slope Trick이 있다.
또한 각종 태그 문제집에서 문제들을 풀다 보니, 레이지 세그먼트 트리, HLD, Centroid, 금광 세그, 네트워크 유량 등 웰노운이지만 구현이 어려운 문제들의 구현을 굉장히 많이 하면서 구현력이 많이 늘었다. 나는 원래 C++을 잘 못했었지만 지난 SCPC를 준비하며 어렵지 않은 알고리즘들을 계속해서 구현해보며 C++ 구현력이 많이 늘었는데, 이번에는 어려운 알고리즘들을 많이 구현해보며 더 많이 늘었다. 이제는 사실상 자료구조/알고리즘을 쓰지 않는 문제들(애드혹, 해구성, 그리디 등)만 Python으로 풀고, 그렇지 않은 문제들은 모두 C++로 푼다. 이때까지 자료구조 문제를 모두 Python으로 풀었다는 게 신기하다.
구현을 할 때는 복사+붙여넣기를 하지 않고 무조건 처음부터 다시 구현했다. 네트워크 유량, 접미사 배열, 아호코라식, PST, BCC는 팀노트를 보고 구현했으며(실제 대회에서도 볼 수 있는 코드만 보았다.) 나머지는 안보고 처음부터 구현하는 연습을 했다.
플레티넘~다이아몬드 문제를 하루에 평균 5~10문제 정도씩 풀었다. 플레 상위~다이아 하위 문제들을 많이 푸는 것은 어렵기도 하고 시험기간도 겹쳐서 조금만 푼 날도 있지만, 그런 날에도 조금씩은 풀고 많이 풀 수 있을 때 많이 풀었다.
10월 12일부터 11월 20일까지 39일간 총 241문제를 풀었고, 골드 51문제, 플레티넘 120문제, 다이아몬드 74문제, 루비 1문제를 풀었다.
날이 갈수록 실력이 많이 는다는 것이 느껴졌다. 이 시기가 최근 1년 중 가장 실력이 많이 늘었다고 생각한다. 어려운 문제들을 많이 풀어내면서 '이건 한 달 전만 해도 절대 못 풀었을 것 같다'라는 느낌을 많이 받았다. Codeforces에서도 이전보다 퍼포먼스가 안정적이면서 훨씬 높게 나왔다.
여기에 더해 대회 2주 전부터는 버추얼을 많이 돌았다. 아무래도 백준만 풀다 보면 웰노운이 많고 특정 태그에 편향되어 있을 수 있어서 대회때까지 그런 편향에 익숙해져 있으면 위험하다고 생각했다. 코드포스 버추얼을 돌기도 했고, 해외 ICPC 셋 버추얼을 5시간동안 혼자 돌기도 했다. 또한 내가 실력이 많이 상승했다고 느꼈기 때문에 이를 한번 테스트해보고 싶다는 생각도 있었다.
또한 가장 중요하게 생각했던 것 중 하나는 ICPC 서울리저널 기출 풀기였다. 비슷한 유형의 문제들로 연습하는 것이 중요하기도 하고, 과거 기출을 보니 비슷한 문제가 여러 번 나오는 경우가 많았다.(결과적으로는 올해는 그런 식의 출제는 없었다ㅠ) 특히 대회 2주 전부터 대회 직전까지 버추얼도 많이 돌고 버추얼때 안 푼 문제들도 따로 많이 풀었다. 대전리저널에서 서울리저널로 넘어온 2018년부터의 기출을 풀었고, 2018~2024년 본선 대회에서 10팀 이상이 푼 모든 문제를 푼 것 같다.
- Seoul 2018 : 풀려있는 문제가 많아 그냥 하나씩 잡고 풀었다. 옛날이라 그런지 문제가 다 재미가 없다.
- Seoul 2019 : 혼자 버추얼을 돌았다. 골드 이하 문제들은 다 풀려있었는데 어짜피 기억이 안나서 그냥 다시 풀었다. B에서 30분동안 디버깅하며 WA를 5번 받고 QOJ 채점에 문제가 있다는 것을 깨달았다. (백준에 내서 맞았다) 이때 매우 짜증이 났지만 그래도 다른 문제들을 계속 풀어서 8문제를 풀었다. 본대회 기준 9등.
- Seoul 2020 : 풀려있는 문제가 많아 그냥 한 문제씩 잡고 풀었다. I를 못풀고 답을 까서 아쉽다.
- Seoul 2021 : 예선 이전에 팀원들과 3인 팀연습을 돌았다. 8문제를 풀었다. 본대회 기준 8등.
- Seoul 2022 : ICPC 2주 전에 혼자 버추얼을 돌았다. 8문제를 풀었다. 본대회 기준 9등.
- Seoul 2023 : ICPC 5일 전에 혼자 버추얼을 돌았다. D에서 Python코드가 의문의 Runtime error을 계속 받고 또 QOJ오류인가 싶어서 백준에 내니까 맞았다. 나중에 똑같은걸 C++로 옮기니까 맞았다. 왜인지는 모르겠다. E는 매우 힘든 풀이를 2시간 동안 짜서 풀었는데 티어가 생각보다 낮아서 보니 쉬운 풀이가 있다고 한다.. 8문제를 풀었다. 본대회 기준 6등.
- Seoul 2024 : ICPC 이틀 전에 한 문제씩 잡고 풀었다. 참가했던 대회이기 때문에 풀이는 거의 다 아는데, 그냥 한 번씩 짜보는 것에 의의를 두었다. H는 모르겠어서 해설을 보고 풀었는데 정해가 매우 신기했다.
연습해보니 한자리수 등수가 계속 나와서 자신감이 많이 생겼다. 이번 대회에서 크게 말리지 않는다면 비슷한 등수로 상을 받을 수 있지 않을까 기대했다.
다만 예전 문제들은 그때 많이 출제되면서 지금 시점에서 웰노운이 된 것들이 많은데, 이를 감안한다면 예전 문제들을 잘 풀었다고 이번에도 잘 할거라고 방심하면 안 된다고도 생각했다.
개인 연습 말고도 팀연습을 많이 했다. 일주일에 한번씩 동아리방에 모여서 ICPC 기출 셋을 5시간동안 돌았다.
가끔은 연세대 모르고리즘 동아리에서 불러주셔서 신촌에 가서 같이 연습을 하기도 했다.
연습을 해보면서 팀원 각각의 성향을 파악하고, 이를 바탕으로 전략을 세웠다.
- sjh1224 : 비전형적인 문제들을 잘 푼다. 그로 인해 Codeforces 레이팅이 팀에서 가장 높다. 따라서 애드혹/해구성 문제나 발상이 주가 되는 문제가 나오면 가장 많이 푼다. 이외에 문자열/확률론 문제를 잘 푼다. 단점으로는 푼 문제 수가 적어서 나만 모르는 웰노운에 맞고 죽는 일이 많이 있다.
- hyperion1019 : 전형적인 문제들을 잘 푼다. 웰노운 자료구조/알고리즘을 많이 알고 잘 구현한다. 따라서 구현이 오래걸리는 DP/자료구조 문제가 나오면 가장 많이 푼다.
- ychangseok : 쉬운 문제 구현 속도가 매우매우매우 빠르다. 또한 전공이 수학이기도 하고 평소에 수학/기하 문제들을 많이 풀어서 수학/기하 문제를 잘 푼다. 따라서 sjh1224와 hyperion1019는 기하 문제가 나오면 읽어보지도 않고 ychangseok에게 '해줘'를 시전한다.(실제로 해준다)
사실 구체적인 대회 전략은 딱히 없고 기본적으로 '풀리는대로 잘 풀기'이지만, 암묵적으로 다음과 같은 과정으로 진행한다.
플레티넘 하위 난이도까지는 다들 잘 풀기 때문에 기본적으로 대회 초반에는 각자 그런 문제들을 푼다. 그러고 나면 각자 자신이 자신있는 분야의 문제들을 잡는다. 안 풀리면 서로 의논해서 풀이를 함께 내고, 구현이 머릿속에 더 잘 그려지는 사람이 구현한다.
아마도 대부분의 팀들이 이렇게 할 것이다. 팀원들이 모두 골고루 잘 해서 다른 전략(1명이 몰아서 구현하기 등)이 필요하지 않았던 것 같다.
특별한 점이 있다면 나는 어려운 문제더라도 풀릴 거 같으면 쉬운 문제를 팀원들에게 유기하고 그 문제를 풀러 가는 경우가 종종 있다. 아마도 내가 특정한 종류의 어려운 문제를 잘 풀어내는 일이 가끔 있었기 때문일 것이다.
다만 연습을 하다 보니 문제가 되는 부분이 조금 있어서 관련한 피드백을 많이 했다. '증명 안된 풀이 짜지 않기', '풀이가 너무 복잡하면 구현 안하고 더 간단한 풀이 생각하기'같은 것들이다.
예전에는 팀연습을 할 때마다 잘 안 되는 부분이 계속 생겼는데, 대회가 얼마 안 남았을 때쯤의 몇 번의 연습에는 팀합이 꽤 잘 맞게 되었다.
개인 연습 + 팀 연습을 바탕으로 스스로 나름의 피드백을 하고 항상 생각해야 하는 것들을 정리했다. 대회 때 이런 것들을 의식하는 게 조금 더 안정적인 퍼포먼스를 가져다준다고 믿었다.
- 잘하는 사람들은 알고리즘을 잘 알아서 잘 하는 것이 아니다. 어려운 문제들도 아무도 모르는 트릭이 필요하기보다는 생각하기 어려운 사고과정이 필요해서 어려운 것이다.
- 잘하는 사람들은 더러운 구현을 잘 해서 잘 하는 것이 아니다. 어려운 문제들도 구현 자체가 복잡하기보다는 구현을 단순화시키는 능력이 필요해서 어려운 것이다. 따라서 구현을 단순화시켜 내가 구현 가능한 범위까지 들여오는 것까지가 '풀이를 낸다'는 과정의 일부이다.
- 대회에서(특히 ICPC에서) 어려운 문제들의 난이도는 비슷한 경우가 많다. 스코어보드를 맹신해서는 안 되며, 다른 팀들이 많이 안 푼 문제들도 읽어보면 생각보다 풀이가 잘 보이는 경우도 있다.
- 하나의 관찰이나 풀이에 매몰되면 안 된다. 생각하는 것이 있더라도 답이 나올듯 안나오고 너무 깊이 들어온 것 같으면 잠시 접어두고 다른 방법으로도 다시 들어가봐야 한다. (풀이공간 BFS를 해야 한다)
- 팀대회에서 지금 뭘 해야할 지 모르겠다고 멍때리는 시간이 생각보다 많다. 개인대회라고 생각하고 모든 시간에 머리를 100% 써야 한다.
- 문제 풀이가 떠오른다고 무작정 구현하면 망하는 경우가 많다. 사소한 디테일까지 어떻게 구현할지 생각하고 풀이의 오류가 없는지 모두 점검한 뒤 구현하는 것이 저점을 높이는 효과적인 방법이다. 특히 팀대회에서는 컴퓨터를 점유한 상태로 말리면 피해가 매우 치명적이기 때문에, 풀이를 모두 점검할 때까지 컴퓨터를 안 잡는 게 이득이다.
- 팀대회에서 구현을 하다가 뭔가 생각대로 안 되는 게 있으면 바로 컴퓨터를 팀원에게 넘기고 천천히 생각해 보는 것이 좋다. 컴퓨터를 잡고 있으면 오히려 빨리 끝내야 한다는 부담감 때문에 계속해서 말리는 경우가 많다.
(개인적인 생각으로 다 맞는 말은 아니다)
대회 1일 전에는 예비소집을 위해 부산으로 내려가야 하기도 했고, 전날은 쉬어야 한다는 생각을 가지고 있었기에 PS를 하지 않았다. 그래서 대회 2일 전에 마지막 준비를 했다.
대회 2일 전에는 아침 9시에 동아리방에 모여 마지막 팀연습을 했다. 마지막인데 망하면 기분이 매우 안좋을 것 같았지만 다행히 매우 잘 했다. 아마 최근 팀연습 중 가장 잘 한 것 같다. 그래서 기분좋게 준비를 마무리할 수 있었다.
그러고는 대회에서 쓸 팀노트 준비를 했다. UCPC와 ICPC 예선, KAIST RUN ICPC Mock Competition에서 이미 팀노트를 썼기 때문에 새로 만들 필요는 없었고, 필요없어 보이는 것들을 빼거나 공백 지우기 등으로 여백을 만들어 새로운 것들을 추가하였다. 나는 FWHT, Segment Tree Beats등을 최근에 배워서 그런 것들을 추가했고, ychangseok은 알고리즘 이외의 한줄 팁이나 SIMD 코드 등을 추가하였다.
그렇게 모든 준비가 끝이 났다 !
5. 대회 전날 (2025.11.21.)
본선은 11월 22일에 부산 벡스코에서 열렸다. 최근 몇 년간 ICPC는 항상 수도권에서 열렸는데, 부산에서 열린다니 매우 신이 났다. 부산에 가기 귀찮다고 하는 사람들도 많았지만, 나는 오히려 큰 대회를 치러 가는 느낌이 나서 좋았다. 1년동안 준비한 대회를 고작 경전철이나 버스 1시간 타고 가서 치는 건 짜치지 않냐는 생각이다. 그리고 부산에 살고 있는 친구들이 많아서 (아마 내가 경상남도에서 초중고를 나와서 그럴 것이다) 가는 김에 만나서 놀다 올 수도 있었다.
대회 전날인 11월 21일에 예비소집이 있었기 때문에, 그날 아침에 기차를 타고 부산으로 가야 했다.
대회 전전날부터 뭔가 대회 전날처럼 긴장되었다. 아마도 대회 전날 아침에 부산으로 내려가기 때문에 그 전 날 팀노트를 만들고 짐을 싸면서 그런 생각을 했던 것 같다. 1년동안 준비했던 대회가 이제 코앞까지 다가왔고, 이번엔 꼭 잘 해야 한다고 생각하니 많이 떨렸다. 3년 전에 수능 전날에 느꼈던 기분과 매우 유사했다.
기차를 타기 위해 광명역으로 갔다. 광명역으로 가는 8507번 버스에서 ychangseok, platter와 또다른 SCSC부원(비PS러)을 우연히 만나서 신기했다. 기차는 ychangseok과 같이 탔는데, 알고 보니 같은 기차에 platter, ystaeyoon113과 다른 많은 서울대 PS러들이 있었다. 부산에서 내린 뒤 그 사람들과 만나서 약 10명이서 점심으로 국밥을 먹으러 갔다. 국밥을 먹고 버스를 타 벡스코에 도착했다.
대회 스태프 중에서는 ICPC 레전드인 leo020630, kwoncycle이 있어서 매우 반가웠다.
대기실과 대회장 둘 다 체감상 작년의 킨텍스 대회장보다 훨씬 컸다. 다른 팀들과 거리가 멀고 우리 팀이 사용할 수 있는 공간이 넓어서 좋았다. 이래서 부산에서 했나 싶다.
예비소집은 작년 본선에 나왔던 3문제가 나오고 자유롭게 풀어보는 식이었는데(몇 등 하는지는 중요하지 않다), B는 똥문제여서 풀다가 모든 힘을 소진할까 두려워 풀지 않았고, ychangseok이 A, 내가 C를 풀었다. 둘다 며칠 전에 풀었던 문제라 쉽게 풀면서 대회 환경에 적응하였다. (hyperion1019는 개인 일정으로 예비소집에 불참하였다ㅠㅠ)
사실 대회 환경에서 C++ 컴파일을 어떻게 하는지 모르겠는 이슈가 있었는데, kwoncycle의 세팅론을 읽은 ychangseok이 이것저것 해 주었다. 혼자 왔으면 큰일날 뻔 했다고 생각했다. sanitizer라는 것(세팅론에 나온다)을 그 때 처음 써 봤는데, 정말 사기라서 이걸 이때까지 왜 몰랐지 라고 생각했다. 대회장에 스태프로 있던 kwoncycle이 할 일이 다 끝이 났는지 우리 대회 자리로 와서 "그거 그렇게 하는 거 아닌데"하면서 분탕을 치길래 무한 숭배를 표현했다.
저녁에는 같은 과 친구인 asp345와, 우연히 부산에 있었던 모 군인(비PS러)과 함께 고기를 먹었다.
고기를 먹은 뒤, 팀원들끼리 잡아둔 해운대 근처의 숙소에 가서 짐을 풀었다. 그러고 무엇을 할까 생각하다가, PS러들과 리그오브레전드 칼바람 5인큐를 하러 벡스코 근처 PC방으로 갔다. 대회 전날에는 공부하는 것보다 노는 것이 다음날 대회에 도움이 된다는 생각도 있었고, 무엇보다 일찍부터 숙소에서 자려고 누워 있으면 잠도 안 오고 긴장만 너무 돼서 아너무떨린다아ㅣㅁ제발ㄹ더말더라ㅣㅁ더리ㅏ머ㅇ할 것 같았다. 그래서 뭐라도 하고 싶었는데 마침 칼바람을 좋아하는 사람들이 많았다.
PC방에는 ystaeyoon113, leo020630이 있었고, 이번 본선에는 참가하지 않는 다른 PS러들도 온라인으로 불러서 5인큐를 계속 했다. 원래 10시쯤까지 하고 일찍 자려 했는데, 한 판만 이기고 끝내자를 하다가 11시에 겨우 이겨서 끝났다.
칼바람이 끝나고, 마침 leo020630님과 숙소 위치가 같아서 함께 이동했다. 잔뜩 긴장해 있던 나는, 큰 대회를 나보다 훨씬 많이 나가본 leo020630에게 오랫동안 멘탈 케어를 받았다. 정말 감사합니다 ㅠㅠ
5. ICPC Seoul Regional (2025.11.22.)
본선 전날 잠을 조금밖에 못 자지 않을까 걱정했었다. 수능 전날에 아주 일찍부터 누웠음에도 3시간 정도밖에 못 잔 기억이 있기 때문이다. 그런데 전날 12시쯤 눕자마자 거의 바로 잤다. 칼바람을 너무 열심히 하기도 했고, 어떤 이슈로 leo020630과 11시 40분쯤까지 밖에 있었기 때문에 긴장이고 뭐고 피곤했던 것 같다. 나는 또한 중요한 날 아침에 일어나기 위해 알람을 맞추면 알람이 울리기 10분 전에 일어나는 병이 있다. 본선날도 어김없이 7시에 알람을 맞췄는데 일어나니까 6시 40분이길래, 그냥 일어나서 씻었다.
팀원들과 함께 편의점에서 간단히 아침을 먹은 뒤 대회장에 갔다. 대회장에서 등록을 하고, 연세대 Endgame 팀과 노가리를 열심히 까다 보니 어느덧 대회장에 입장할 시간이 되었다.
대회장에 가 보니 풍선이 13개인 것을 보고 대회 문제가 13개임을 알 수 있었다. 작년까지는 대회 문제가 12개였는데 한 문제 더 풀어야 한다니 무서웠다.
또한 준비된 풍선의 개수로부터 문제 난이도 추측하기는 잘 알려진 트릭이다(그 문제를 맞힌 팀은 모두 풍선을 받아야 하기 때문이다. 트릭이 실제로 동작하는 지는 모른다). 풍선을 유심히 보니, 어떤 3종류의 풍선이 다른 종류보다 개수가 확실히 적었다. 그로부터 그 문제들은 어려울 것이라고 추측했다. 그런데 대회 시작이 몇 분 안 남았을 때 갑자기 풍선이 셔플되는 것이다! 스태프들이 각 풍선을 다른 위치로 옮기고 있었다. 이게 무슨 일인가 굉장히 의아했다. 셔플 결과 개수가 확실히 적은 풍선은 B번, F번, K번 문제에 해당하는 문제들이었다. 그래서 B, F, K는 처음에는 보지 말자고 팀원끼리 합의했다. (결과적으로 3문제 모두 초반에 풀 만한 문제는 아니었으므로 이 전략은 유효했다.)
대회 내용은 다음과 같았다.
- 대회가 시작했다. ychangseok은 예비소집 때 연습했던 세팅을 했고, 문제들은 연습때처럼 ychangseok이 앞부분, 내가 중간, hyperion1019가 뒷부분을 보았다.
- 나는 처음에 H를 봤는데 이게 M이랑 연관 문제라고 되어 있고 난 M이 없어서 넘겼다. 그러고 남은 문제들 중 G의 관상이 제일 쉬워 보이길래 G를 읽었다. 읽어보니 세팅이 내가 예전에 풀었던 어지러운 케이스워크 그리디 문제(무슨 문제인지는 기억이 나지 않는다)와 비슷해서 똑같은 문제인가 하고 걱정했는데, 생각해보니 그냥 뇌빼고 파라매트릭 서치를 하면 된다는 사실을 깨달았다. 팀원들이 아직 아무도 풀이가 안 나와서 컴퓨터를 잡고 코드를 짰다. 코드를 짜다가 생각 안 했던 부분이 있어 약간 멈칫했는데, hyperion1019가 M을 5분이면 짠다길래 비켜준 뒤 구현을 구체화했다. 얼마 안가 M을 맞았고(16분, 1솔, +0 AC), 내가 G에 코드 몇 줄을 추가해서 맞았다(20분, 2솔, +0 AC). G의 First Solve를 1분 차이로 놓쳐 아쉬웠다.
- 우리가 G, M을 보는 도중 L이 많이 풀려서 ychangseok이 L을 풀었다. (24분, 3솔, +0 AC)
- 또한 ychangseok은 C의 풀이가 나왔다고 해서 C를 구현했다. 이때는 우리가 안 푼 문제 중에는 C, D, E가 솔브가 나온 상태였다. hyperion1019가 D를 읽어보더니 잉 어케함? 하고 나한테 준 뒤 E를 봤다. 나는 D를 봤는데, 처음에는 잉 어케함? 했다. 그런데 시간이 지나면서 솔브가 굉장히 많이 나오는 것을 보고, 이건 분명 뭔가 관찰을 하면 굉장히 쉬워지는 문제라고 생각했다. 며칠 전에 그 당시에는 비공개였던 동아리 대회 문제에서 해봤던, 'inversion을 swap할 수 있나 없나만 중요함'를 그대로 적용해봤더니, 문제가 굉장히 쉬워졌다. 몇가지 케이스에 대해 생각을 해보면 애드혹적인 풀이를 찾을 수 있었다.
- ychangseok은 C를 한 번 틀린 뒤 지옥의 디버깅 끝에 AC를 받았다. (69분, 4솔, +1 AC)
- 나는 바로 D를 구현했는데, 틀렸다. 알고 보니 하나의 케이스에서 식을 잘못 썼다는 사실을 깨달았고, 고쳤는데 또 틀렸다. 알고 보니 고친 식도 틀렸다는 사실을 깨달았고, 고쳤는데 또 틀렸다. 이때쯤 되니 풀이가 틀린 게 아닌가 하고 굉장히 무서웠다. 사실 마음이 급해서 풀이의 모든 부분을 세세하게 검증해보지 못했기 때문에, 풀이가 틀릴 확률이 어느정도 있다고 생각했다. 풀이가 틀렸다면 풀이도 다시 내고 처음부터 다시 구현해야 하니 최악인 상황이었다.
- 팀원들은 E, I 풀이가 나와서 기다리는 중이라고 했다. 나는 E 먼저 하실래요? 라고 물어봤지만 hyperion1019는 E도 구현이 빨리 끝나지는 않아서 그냥 D먼저 하는 게 나을 것 같다고 말했다. 디버깅을 열심히 하다가 코드의 for문에서 k+1이 들어가야 하는 곳에 k가 들어간 부분을 찾았다. 코드를 너무 스파게티처럼 짜서 생긴 실수였다. 일단 고쳐서 제출했다. 사실 제출해도 맞을 것 같다는 생각은 안 들었다. 풀이나 구현에 더 큰 문제가 있을 것이라 생각했다. 그런데 의외로 Accepted가 떴다! 안도의 한숨을 크게 내쉬었다. (91분, 5솔, +3 AC)
- hyperion1019는 E의 구현을 시작했고, ychangseok은 I의 풀이가 나왔다고 했으며 K도 자신이 풀 수 있다고 말했다.
- 그래서 나는 푼 문제와 풀이가 나온 문제 8문제를 제외한 다른 문제를 봐야 했다. 그런데 나머지 5문제(A, B, F, H, J)는 모두 제출조차 없었고, 어떤 문제를 볼지 고민했다. A는 5페이지짜리 인터랙티브 문제였으며 ychangseok이 대충 봤는데 어려워 보인다고 해서 패스했다. B는 읽고 조금 생각해보다가 할 게 엄청 많은 문제라는 것을 깨닫고 보스 문제라고 생각해 넘겼다. F, H, J는 뭔가 풀만해보인다고 생각했다.
- hyperion1019는 E를 구현해서 제출했는데 틀렸고, 10분정도 디버깅을 하다가 포기하고 ychangseok에게 I번을 먼저 구현하라고 한 뒤 코드를 프린트해 나에게 도움을 요청했다. 나는 hyperion1019에게 문제, 풀이, 코드의 설명을 모두 듣고, 풀이는 확실한 것 같아 코드를 한줄한줄 열심히 읽어보다가 뭔가 이상한 부분을 찾았다. hyperion1019에게 이거 min으로 해야되는거 아님? 라고 말했더니, 그는 내가 왜 그랬지 같은 소리를 하며 코드를 고치고 AC를 받았다. (138분, 6솔, +1 AC)
- ychangseok은 hyperion1019가 디버깅하는동안 I를 구현하여 제출했으나 WA를 2번 받았다. 그러나 결국 디버깅을 성공하여 AC를 받았다. (146분, 7솔, +2 AC)
- ychangseok은 K도 풀이가 나와서 구현했으나 TLE를 받았다. 이때는 WWE라고 생각했으나 ychangseok은 오랫동안 잘못된 부분을 찾지 못했다. K를 풀지 못하면 큰일이 날 것이라고 생각한 hyperion1019는 K를 도우러 갔다. (결과적으로 최고의 판단이었다) 두 명이서 열심히 싸우면서 코드를 고쳤다. 그러는 도중, 대회 종료 1시간 20분 전인 220분에 스코어보드가 프리즈되었다. ychangseok은 hyperion1019와의 오랜 토론을 바탕으로 코드를 열심히 고쳐 제출했고, 3명이서 조마조마하게 채점을 지켜보다가.. Accepted가 나왔음을 확인했다! (232분, 8솔, +1 AC)
- 나는 두 명이서 K를 열심히 보는 동안 다른 문제들을 계속해서 보고 있었다. 스코어보드를 보니 여전히 우리가 푼 8문제만 솔브가 계속 나오는 상태였으며, 1등팀인 Just Use CRT가 F를 두 번 제출했으나 틀린 것 이외에는 다른 문제 제출도 없었다.
- F는 5~6차원 DP 또는 MITM을 하라는 듯한 제한이었다. MITM은 잘 안 되는 것 같아 DP가 조금 더 가능성 높다고 생각했으나, 쉽게 되지는 않았다. Just Use CRT가 계속 틀리고 있는 것으로 보아 구현이 굉장히 어려운 문제라고 생각해서 넘겼다(결과적으로는 잘못된 예상이었던 것 같다. F를 봤어야 했나 싶다. 하지만 예상할 수는 없었다).
- H는 경우의 수를 세는 문제였는데, 별로 어렵지 않아 보였다. 그런데 알고 보니 내가 N=3일 때 예제만 보고 문제를 잘못 이해해서 다른 문제를 풀고 있었다. 그 다른 문제의 사풀이를 생각해 내서, 팀원들이 K를 푼 뒤 컴퓨터로 해보는데, 예제가 왜 안나오지 라고 생각하다가 잘못 이해한 것을 깨달았다.
- J는 문제에 나오는 식을 구간의 겹침으로 해석해야 하는 문제였는데, 그걸 못 보고 다른 방향으로 생각을 너무 오래 해버렸다. 뒤늦게 구간의 겹침을 깨달았을 때는 대회가 1시간밖에 안 남았었다.
- 결과적으로 나는 H와 J에서 잘못된 방향으로 너무 오래 생각함으로서 팀원들이 I, K를 풀 동안 아무것도 하지 못했다. 이때 조금 멘탈이 나갔다.
- hyperion1019는 우리 팀의 패널티가 매우 크고 8문제를 푼 팀이 많기 때문에 1문제를 더 풀어야 상을 받을 수 있다고 주장했다. 그러면서 H가 그나마 할만해 보인다며 H를 열심히 봤다. 나는 H에서 한번 말린 전적이 있고, N이 3k, 3k+1, 3k+2인 경우를 모두 따로 해야 하고 식이 너무 복잡하여 실수하기 쉬워 보여 H는 보면 안되겠다고 생각했다.
- 반면 J는 구간 겹침을 관찰했으니 뭔가 애드혹적인 사고와 간단한 구현으로 풀 수 있을지도 모른다고 생각했다. 그래서 남은 시간동안 J를 봤다. 그런데 풀다 보니 뭔가 정렬을 하고 2차원 세그먼트 트리로 스위핑을 열심히 하면 될 것 같은, 생각만해도 구현이 어지러운 모양이 나와버렸다. (풀이가 다 나온 것은 아니나, 방향은 아마 정해와 비슷한 것 같다). 이때가 대회 종료 20분 쯤 전이었는데, 풀이를 완성하고 한 번도 안짜본 2차원 세그먼트 트리 구현까지 하는 것은 절대 불가능하다고 생각했다.
- hyperion1019는 H의 O(N^2) 풀이를 내서 J를 보고 있는 나에게 설명해줬다. 나는 풀이가 잘 이해가 안 되었다. 뭔가 내가 생각했던 방향이랑 다른 풀이라서 이 풀이가 맞나 의심이 들었는데, 문제는 시간이 너무 조금 남아서 나에게 그게 왜 맞는지를 설명하게 하면 남은 시간을 너무 많이 빼앗아버릴 것 같았다. 그래서 일단 식이 맞다고 가정하고 O(N^2)을 어떻게 O(N)또는 O(NlogN)으로 최적화할지 열심히 고민했다.
- 결국 남은 시간이 너무 적어서 5분쯤 남았을 때 GG를 선언했다. 10솔우승을 주장하기 위해 A와 H에 페이크 제출(프리즈 후에 제출하면 채점 결과를 다른 팀이 볼 수 없다)을 했다.
- 남은 시간 동안 페이크 제출을 한 뒤 프리즈된 스코어보드 구경을 했다. 나는 우리가 한문제를 더 못풀었기에 상을 못 받을 것이라 생각하는 hyperion1019에게 스코어보드를 보여주며 사실 우리팀이 상을 받을 수 있다고 말했다. 나는 사실 대회 종료 40분 전쯤에 우연히 스코어보드를 한 번 보았고, 우리 팀이 수상권이라는 것을 알고 있었다. 우리팀이 프리즈 전에 15등이었는데 프리즈 직후 K를 풀었고, 우리팀 위에는 아직 7솔브에서 제출이 없는 팀이 많았기 때문이다. 그러나 이 사실을 말하면 팀원들의 간절함이 떨어져 문제를 열심히 풀지 못할까봐 조용히 있었다. (나는 간절함이 떨어져 문제를 열심히 풀지 못한 것 같기도 하다. 팀원들에게 미안하지만 나도 열심히 풀고 싶었고 마음대로 되는 것은 아닌 것 같다ㅠ)
다시 차근차근 스코어보드 제출들을 계산해 보니 우리 밑에서 프리즈후 9솔을 한 팀이 충분히 많지 않다면(실제로는 한 팀도 없었다) 무조건 상을 받는다는 것을 확인하고, 팀원들끼리 조용히 기뻐하며 대회를 끝냈다.
대회 종료 후에는 후원사 세션과 가위바위보 경품이벤트 등이 있었고, 마침내 매우 떨리는 스코어보드 오픈이 있었다.
결과는 12등으로, 장려상도 아닌 동상을 수상하였다 ! 프리즈된 스코어보드를 보고 예상했던 것보다 훨씬 높았고, 매우 만족스러운 결과였다.
한국 팀중에는 9등으로, 매우 잘했다고 생각한 예선 10등보다 더 잘 했다. 우리 팀보다 등수가 높은 팀들 중 이겼어야 한다고 생각하는 팀은 없었고, 오히려 다른 잘하는 팀들을 많이 이긴 것 같아 기뻤다.
대회가 끝나고는 함께 대회를 친 많은 사람들과 대회 스태프 kwoncycle, leo020630과 함께 뒷풀이를 한 뒤, 2차로 팀원들+leo020630과 술을 마시고 PC방에 가서 칼바람을 좀 하다가 자러 갔다.
6. 후기
예선을 겨우 통과해 참가했던 작년 대회에서 앞에 나가 상을 받는 사람들을 보며 많이 부러워했던 기억이 난다. 내가 계속해서 PS를 한다면 언젠간 저 자리에 설 수 있을까 하는 생각도 했었다. 그런데 과분하게도 1년만에 여기까지 올 수 있어서 매우 기쁘다.
올해 초까지만 해도 상을 받을 것이라고 생각 못했고, ICPC 직전이 돼서는 많이 성장하여 반드시 상을 받아야 한다 라고 생각했다. 그러면서도 항상 정말 상을 받을 수 있을까 의심하고 걱정했었는데, 결국 이뤄냈고 올바른 방향으로 계속해서 나아갔다는 것을 증명한 것 같아서 행복하다.
여기서는 대회가 끝나고 느낀 많은 생각들을 병렬적으로 서술하겠다.
- 대회 성적은 매우 마음에 든다. 동상보다 높은 상을 바라기에는 아직 많이 부족하기도 하고, 다른 팀들이 매우 잘 하기 때문이다. 오히려 말려서 상을 못 받을 까봐 계속 걱정했었는데 장려상도 아닌 동상을 받다니 너무 좋다.
사람들에게 축하도 많이 받아서 좋다. 축하해주신 분들 모두 감사합니다! - 그럼에도 대회가 끝나고 많이 아쉬웠다. 대회 중 내용을 보면 20분에 G, 91분에 D를 푼 것, E의 디버깅을 도운 것 이외에는 내가 한 것이 사실상 아무것도 없다. 심지어 D를 풀 때 많이 틀리기도 했으며, H와 J에서 트롤짓을 해서 많은 시간을 낭비하고 3시간반동안 1문제도 풀지 못했다. A F H J 모두 내가 절대 못 풀 문제였냐 하면 그렇다고 믿고 싶지만 그렇지 않은 것으로 보인다.
그렇기 때문에 대회 성적이 마음에 드는 것과 별개로, 개인적인 아쉬움을 많이 느꼈다. 준비 과정에 쓴 것처럼 정말 많은 것들을 공부하고 정말 많은 시간과 노력을 투자해 연습했다. 실력도 크게 늘었고, 따라서 이를 큰 무대에서 증명하고 싶다는 생각도 있었을 것이다. 그런데 대회에 와서는 아무것도 하지 못하는 그냥 팀원들이 어려운 문제를 풀어내는 것을 구경만 하다 끝난 샘이다. 대회에서 내 자리에 임의의 오렌지 이상의 PS러가 있었다면 높은 확률로 비슷한 결과가 나왔을 것이다. 나는 '이만큼 준비해서 이런 엄청난 결과를 만들어냈다!' 같은 서사를 원했던 것 같다. 하지만 내가 얻은 서사는 '이만큼 준비했는데 대회에서는 버스타서 상을 받았다'였다. 그동한 준비한 것이 모두 아무 의미가 없는 것처럼 느껴졌다.
물론 당연히 그건 아니다. 저점을 높이기 위해 열심히 노력했기 때문에 말릴 만한 부분이 꽤 있는 문제인 G와 D를 오래 걸리지 않고 풀어낸 것이며, 팀적으로는 연습을 상당히 많이 했기에 각 순간에 무엇을 해야 하는지 서로 말하지 않아도 다 알고 있어 8문제를 매우 빠르게 풀어낼 수 있었다. 특히 대회 중에 말릴 것 같은 적절한 순간에 2인 디버깅을 통해 빠르게 넘어간 일이 2번 있었다. 수많은 연습이 없었다면 이렇게 최적화된 행동을 하지는 못했을 것이다. 또한 준비하면서 실력이 실제로 많이 늘었기 때문에 다음 대회나 다른 것을 할 때에도 도움이 될 것이며, 내가 열심히 준비했기 때문에 좋은 팀원들도 구했고 팀원들이 나를 보며 더 열심히 준비했을 것이다.
그럼에도 아쉬운 것은 아쉬운 것이다. 기대가 높았기 때문에, 그리고 실제로 더 잘할 수 있는 여지가 있었기 때문일 것이다. 그래도 어쩔 수 없다. 대회에서 모든 게 완벽한 것은 사실상 불가능하기 때문에, 어쨋거나 잘할건 잘하고 못할건 못해서 이정도의 결과를 만들어낼 수 있었겠지 라고 생각한다. 아쉬운 부분은 내년에 더 잘해야지 라는 생각을 할 수 있는 학년이기에 괜찮다. - 나의 G 코드는 반례가 있다. 이분탐색을 1e18까지 해야하고, 이 과정에서 long long overflow가 일어날 수 있어 int128을 사용해야 하는데, 나는 이분탐색을 1e12까지 해서 overflow도 없었다. 그렇게 해도 된다고 생각했으나 대회가 끝난 이후 자유시간에 platter가 반례를 말해주었다. 아마 대회 중에는 잘못된 논리로 반례가 없다는 것을 증명했던 것 같다. 그런데 다행히 채점 데이터에는 그 반례가 없었고 한번에 AC를 받았다. 나중에 AC를 받은 코드에 반례를 넣어 보니 TLE가 나는 것을 확인할 수 있었다... 이렇게 운이 좋지 않았다면 여러번 WA를 받고 말려서 패널티를 많이 정립하고 동상을 받지 못했을지도 모른다.
- 쉬운 문제를 다 밀어내고 난이도를 모르는(솔브가 나오지 않은) 어려운 문제들 중 하나를 잡아서 풀어내는 능력이 아직은 많이 부족하다고 느낀다(ICPC예선, KAIST대회, ICPC본선 모두 그랬다). 대회에서 그래본 경험이 아직 없기 때문에 당연하다. 이전에는 항상 고수들보다 앞문제를 푸는 속도가느렸기 때문에 그들이 푸는 걸 보고 아 이건 난이도가 이쯤 되는 문제겠구나 해서 잡아서 하나씩 푸는 식으로 대회를 했었다. 그런데 지금은 속도가 충분히 빨라졌고, 더이상 고수들을 따라 풀 수 없어 갈 길을 잃는다. 이는 내가 다음 단계로 나아가기 위해 반드시 극복해야 할 문제이다. 빠른 속도로 쉬운 문제를 푼 뒤 아무도 풀지 않았지만 나에게는 풀만한 문제를 찾아서 풀 수 있는 능력을 길려야 하겠다.
이번 대회에서도 A, F, H, J 모두 한 문제만 봤을 때는 매우 잘 했으면 풀 수도 있었다고 생각한다. 그러나 무엇을 풀어야 할지 몰라서 한 문제에 시간을 오래 박지 못했으며, 잘못된 생각으로 인해 시간을 너무 많이 날렸다. 2년 뒤 또는 3년 뒤가 될 다음 대회에서는 이것을 극복해올 수 있었으면 좋겠다. - 대회에서 내가 잘 했는지와 별개로, 그동안 당연히 할 수 있다고 생각해왔으나 한 번도 성공하지 못했던 '단기간 성장'을 이루어냈다. 단기간에 매우 많은 것들을 공부하고, 실력을 이전과 비교도 안될 정도로 높은 곳까지 끌어올렸다. 이전까지 이렇게 못한 것이 굉장히 아쉽고 후회되지만, 어쩔 수 없는 시행착오였다고 생각하는 것이 맞아 보인다. 지금이라도 한 번 성공해보았으니 이번 경험을 바탕으로 PS든 다른 일이든 이전보다 훨씬 잘 해볼 수 있을 것이라고 기대하고 있다. 오히려 이것을 PS를 졸업하기 전에 일찍 깨달아 다행이라는 생각도 든다. 이걸 깨닫고 군대를 가는 신지환?이거 못막습니다 ㅇㅇ
- 앞으로는 무엇을 할 것인가? 사실 군대에 가야 한다. 군대에 가서는 머리를 좀 식히면서 템포가 느린 공부를 하고 싶다는 생각이고, 갔다 와서는 아마 ICPC를 계속하지 않을까 싶지만, 확실한 건 나도 모른다.
지금은 모든 게 끝나고 군입대만을 기다리고 있는 상황에서 비효율을 즐기고 있다(사실 그래서 후기를 한 달이나 지난 지금에야 써서 올리는 것이다..ㅈㅅ). 항상 '이거 하면 시간 너무 많이 쓰는데 어카지'라는 생각에 얽매여 살았는데, 지금은 그런 생각이 들면 '어짜피 할 것도 없는데 걍 다 날리지 뭐~'라고 할 수 있는 상황이다. 이런 여유가 수능 이후 3년만에 나에게 찾아와 너무 좋다.
수능이 끝나고 대학에 입학하기 전까지의 너무 심심해서 미치겠는 그 시간이 그렇게 행복한 시간인 줄 몰랐는데, 대학을 다니며 여유가 없는 걸로 스트레스를 많이 받다 보니 다시는 오지 않을 그 순간을 많이 그리워했다. 그런데 그와 같은 순간이 다시 왔다. 그저 시간 사용의 스트레스가 사라진 지금 순간에 매우 감사하며 살고 있다. 행복하다. - 군대는 12월 22일에 간다. 단 일주일밖에 남지 않았다. 죽고싶다. 군생활 무사히 잘 하고 와야겠다.ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
긴 글 읽어주셔서 감사합니다 !