경쟁적 프로그래밍 대회 중 우리나라 최대 규모 개인 대회인 삼성 대학생 프로그래밍 챌린지(SCPC)를 치고 왔다.
원래 블로그 같은거 안 썼었는데, 왜냐면 뭔가 대회때마다 망해서 자랑할 게 없었기 때문이다.. 그렇다고 뭔가 남들과 다른 할얘기가 있는 것도 아니고.. 그래서 쓰고 싶지만 쓸얘기가 없으니 수상 하나 하면 그때부터 하자!라고 맨날 생각했었다. 그렇다. SCPC 2025에서 수상하고 블로그를 시작하게 되었다!
하고 싶은 얘기가 많다 보니 후기글 내용이 조금 길다. 마음의 준비를 하시길 바란다. 순서는 다음과 같다.
0. 배경
1. 1차 온라인 예선
2. 2차 온라인 예선
3. 본선 준비
4. 오프라인 본선
5. 후기
0. 배경
컴퓨터공학과 학부생들 중 일부는 PS(Problem Solving) 또는 CP(Competitive Programming)라 부르는 활동을 매우 열심히 한다. PS는 수학이나 컴퓨터 과학 이론을 이용해 특정 문제의 해결법을 찾고, 이를 프로그래밍으로 구현하여 문제를 푸는 공부이다. CP는 이런 PS를 하는 대회에 참가해서 다른 사람들과 경쟁하는 활동이다. 대회에 나가면 스포츠 대회와 비슷하게 사람들과 경쟁하는 짜릿함을 느낄 수 있고, 잘하면 상금과 명예를 얻을 수 있다. PS와 CP는 서로 비슷하기 때문에 혼용해서 사용하기도 한다. 나도 앞으로는 계속 PS라고 부르도록 하겠다. 뭔지 감이 안온다면 이 글을 참고하면 좋다.
이런 PS 대회는 다시 팀 대회와 개인대회로 나뉘는데, 한국에서 가장 규모가 큰 팀대회는 ICPC Seoul Regional(전국 대학생 프로그래밍 경시대회)이고 가장 규모가 큰 개인대회는 SCPC(삼성 대학생 프로그래밍 챌린지)이다. 그래서 이 둘을 중점적으로 열심히 준비하고 있고, 고3때 수능 끝나고부터 열심히 했으니 이제 3년째 거의 이것만 하는 중이다.
그런데 나는 단 한번도 공식대회에서 상을 받은 적이 없다! 재작년ICPC, 작년ICPC, LGCPC와 올해UCPC, 이외의 많은 작은 대회들에 참여했지만 모든 대회에서 상을 받지 못했다. 특히 7월에 열린 팀대회인 UCPC(전국 대학생 프로그래밍 대회 동아리 연합 대회) 2025에서는 최근 실력이 많이 올랐고 연습도 잘 돼서 반드시 상을 받겠다고 다짐했지만, 내가 5시간동안 0문제를 푸는 트롤짓을 해버려서(...) 우리팀이 상을 받지 못했다. 또한 올해 열린 ACPC라는 작은 대회에서도 엄청난 바보짓을 해서 망해버렸다. 그래서 연습때는 잘하다가 대회때마다 망하는 그런 트라우마같은 게 쌓여 있었다.
그러던 중 이번 8월29일에 SCPC가 열렸다. 먼저 7~8월에 온라인 예선을 2번해서 본선 참가자를 선발하고 마지막에 오프라인 본선을 진행하는 방식이다. 이번 대회에서는 꼭 상을 받고 싶었다. 작년 재작년에도 SCPC에 참여 기회가 있었으나, 나는 프로그래밍 언어를 Python만 사용하였고 SCPC에서는 Python을 지원하지 않아 제대로 하지 않았다. 하지만 올해는 내가 연초부터 C++을 꾸준히 공부해왔기 때문에, Python만큼은 아니지만 구현을 잘 할 수 있게 되었고, 충분히 수상을 노려볼만한 실력이 되었기 때문에 꼭 참가해서 수상하겠다고 다짐했다.
이번엔 진짜 무조건 상을 받고 싶었다. 3년째 PS를 하면서 상이 하나도 없으니까 요즘 내가 이 짓 하는 게 의미가 있나 하는 생각도 들었고, 시간은 계속 가는데 결과물이 하나도 없으니 이대로 무관으로 끝나는거 아닌가 하고 불안했다. 뭔가 상 하나만 있으면 스펙도 생기고 아 내가 잘 하고 있구나 하는 자신감도 생길 것 같았다. 그리고 대회때마다 망하는 트라우마를 이번에 극복하고 싶었다. 특히 이번에는 이전과 다르게 상을 받는 게 정배인 실력이라고 생각해서, 못받으면 많이 슬플 것 같았다.
그리고 예전엔 몰랐는데 SCPC에서 수상하면 상금만 주는 것이 아니라, 삼성 SW멤버쉽이라는 것에 가입하여 다양한 혜택을 받을 수 있다는 매우 큰 메리트가 있다고 한다. 이것 때문에라도 꼭 수상하고 싶었다.
1학기 때부터 그렇게 생각하며 공부하던 중 6월 쯤에 SCPC 대회 공고가 나왔는데, 좋은 소식과 안좋은 소식이 있었다. 좋은 소식은 본선이 코로나 이전인 2019년 이후 6년만에 오프라인으로 열리게 되어, 더 재밌는 대회 분위기를 즐길 수 있게 되었다는 점이었다. 매우 신나는 일이었다. 그런데 안좋은 소식은 이전부터 19~38등까지 주는 5등상이 삭제되었다는 것이다. 원래 5등상이 있었다면 어렵지 않게 상을 받을 수도 있었겠지만, 5등상이 없어지면서 18등안에 들어야 4등상 이상의 상을 받을 수 있기 때문에 상을 받는 난이도가 상당히 올라갔다. 그래서 더욱 더 열심히 준비해야 했다. 18등 정도면 아직은 내가 잘하면 충분히 해볼만한 등수라고 생각했고, 4등상 이상의 상을 받는 것을 목표로 열심히 공부하였다.
1. 1차 온라인 예선 ( 07.11 ~ 07.12 )
1차 예선은 24시간동안 진행되며 5문제가 출제되는데, 그중 가장 쉬운 2문제만 풀어도 붙는다고 알려져 있다. 하지만 딱 2문제 푸는 건 쫄렸기 때문에 1, 2, 4번을 풀고 껐다. 1,2,3번을 푼거보다 점수가 높아서 + 3번이 4번보다 귀찮아보였기에 4번을 풀었다.
사실 5문제 모두 시도해봤어도 좋았겠지만 이때 계절학기, 랩인턴 등 할일이 많아서 그랬던 것 같다.
2. 2차 온라인 예선 ( 08.09 )
1차 예선은 통과하기 쉬운 반면, 2차 예선은 문제들도 어렵고 100명 정도밖에 통과하지 못하기 때문에 최선을 다해 풀어야 한다. 실제로 예전부터 몇몇 고수들이 2차 예선에서 떨어지는 불상사가 있어왔다고 한다..
2차 예선날에는 오전 9시부터 오후 9시까지 12시간동안 5문제(부분점수 있음)를 풀어야 한다. 나는 이때 계절학기가 종강하고 백수같은 수면패턴으로 살고 있었기 때문에 오전8시쯤 일어나는 것은 매우 힘든 일이었다. 물론 일어나려면 가능했겠지만, 12시간 대회인 만큼 체력이 매우 중요해서 한시간 더 자는 게 오히려 이득이라고 생각했다. 그래서 적당히 9시쯤 일어나서 학교 중앙도서관에 가서 10시부터 대회를 쳤다.
1, 2, 3번은 적당히 구현하다가 몇번 틀리고 고치고 해서 풀었다. 1번은 몇달전 KOI 버추얼에서 풀었던 문제와 거의 똑같은 DP, 2번은 오프라인 쿼리+이분 탐색+세그먼트 트리, 3번은 식정리 후 투포인터+std::multiset으로 풀었다. 중간에 점심 먹는 것을 포함하여 3문제를 풀고 나니 14시 20분이었다.
1~3번을 풀고 만점자수를 보니 3번 만점이 26명이었다. 본선에 최소 60명은 간다고 생각했기 때문에 4~5번에서 부분점수를 적당히 긁으면 무조건 본선을 가겠다고 생각했다.
그런데..거의 아무것도 긁지 못했다...
사실 시간이 많이 남은 만큼 4번이나 5번 중 한문제의 만점 풀이를 생각하고 있다가 잘 안 돼서 시간을 많이 날렸고, 5번은 ABC가 연속해야 하는 걸로 문제를 잘못 읽어서 나만의 다른 문제를 푸느라 시간과 체력을 많이 소모하였다.. 시간이 얼마 안남아서 아쉬운대로 일단 풀이가 보이는 4-1번과 5-2번 서브태스크를 긁기로 했다. 5-2번은 range add update와 range max query를 지원하는 레이지 세그먼트 트리를 이용해 괄호 문자열의 누적합을 관리해주어 풀 수 있었다. 사람들 말로는 세그먼트 트리는 필요없고 내 풀이는 오버킬이라고 한다.
이제 4-1번을 풀면 되는데, O(N^2M^2+N^3M)으로 구현했음에도 계속 시간초과로 0점을 받았다. 그래서 상수최적화가 필요한가 싶어서 계속 커팅을 했는데 똑같이 0점을 받았다.. 알고보니 각 테스트케이스마다 따로 채점되게 하려면 "cout.flush();" 나 "cout << endl;"을 해주거나 서브태스크별로 조건 분기를 이용해 분리하는 코드를 써줘야 하는데 해주지 않아서, 모든 테스트케이스가 한번에 채점되었고 N이 큰 서브태스크로 인해 당연히 시간 초과가 났던 것이다. SCPC 환경에 익숙하지 않아 생긴 일이었다.
그걸 깨달았을 때는 이미 제출횟수 제한 10번 중 8번을 채워 2번밖에 더 제출을 못하는 상황이었다. 일단 수정해서 제출해보니 시간초과가 아닌 오답 판정을 받았고, 잘못된 부분을 조금 고쳐서 제출했는데 또 0점을 받고 제출횟수 제한 10번을 채워버렸다. 이건 아마 구현을 어딘가에서 실수해서 그런 것 같다. 사실 2번정도 틀리는 건 자주 있는 일이기 때문에, 시간초과로 제출 8번을 낭비하지 않았다면 디버깅 적당히 하고 풀 수 있었을 것이다. 그런데 그러지 못했고... 이젠 시간도 안남아서 4번0점 5번42점으로 마무리하게 되었다.
약간 멘탈이 나갔는데 그래도 붙을수도 있다는 희망은 있었다. 그런데 3번 만점자가 82명이고 1~2번은 그거보다 많았으며, 4번 평균점수도 99점으로 매우 높았다. (위 사진 참고) 즉 나보다 점수높은사람이 매우 많은 것이다. 전체 80등쯤 될 거라고 생각했다. 다른 사람들이랑 얘기해보니 나보다 점수가 낮은 사람을 거의 찾아볼 수 없었고, 내 점수보다 본선 진출컷을 높게 잡는 사람들도 있었다. 원래 본선을 100명 넘게 뽑기 때문에 80등쯤이면 당연히 붙지만, 이번엔 이례적으로 오프라인 본선이고 수상자 인원수도 줄어 본선 인원수가 줄 수도 있다는 말이 많았다.
그래서 본선도 못 가보고 이대로 끝나는거 아닌가 해서 상당히 쫄렸다.
하지만! 삼성에서 본선 인원을 대략 110명이나 뽑아주었고, 아마 커트라인이 4xx점으로 널널하게 본선에 갈 수 있었다. 감사합니다!
3. 본선 준비
본선에 무사히 진출하였다. 그러나 이번에 2차예선 결과를 보고 정신 안 차리면 큰일난다는 걸 깨달았다. 예선 80등한 실력으로 어떻게 본선 18등을 하겠는가? 하지만 나는 상을 정말정말 받고싶었기 때문에 2차예선 결과가 나온 날부터 8월 중순~말 동안 SCPC만을 위한 준비를 열심히 했다. 사실 공군준비를 위한 헌혈, 봉사활동과 본가 방문 등으로 PS에만 집중하지는 못해서 약간 아쉬운 점이 있지만, 그래도 짬짬이 최대한 시간을 내서 어느정도 할 만큼은 한 것 같다.
문제점 분석
나는 대회를 망하는 경우 문제 풀이가 안떠올라서 보다는 어디선가 말려서 망한 적이 대부분이다. 이런 경험을 바탕으로 내가 부족하다고 생각하는 것은 크게 2가지였다.
(1) 나는 발상력에 비해 구현력이 매우 약하다. 웰노운(well-known) 알고리즘도 빨리 짜지 못하고, 인덱싱이 헷갈리는 스위핑이나 DP 등을 짤 때 짧은 코드여도 상당히 오래걸린다. 또한 원래 파이썬만 쓰던 사람이기 때문에 C++로 구현하면 구현시간이 여기서 2~3배 어난다. 그런데 SCPC는 파이썬을 지원하지 않아 C++ 구현을 잘 해야 했다.
(2) 대회 후반에 집중력이 급격하게 감소한다. 오프라인 대회에서 스코어보드 프리즈 (대부분의 대회는 재미를 위해 대회종료 1시간 전쯤 순위표가 프리즈된다.) 이후 점수를 올린 적이 거의 없다. 프리즈 후 점수를 올린 기억은 2023년 5월에 있었던 참가자 7명인 SCSC대회가 마지막이고..그거 말고는 모르겠다. 그만큼 후반에 뭔가 집중이 안되고 남들은 4시간대회를 치면 나는 3시간대회를 친다는 느낌이 자주 들었다. 올해 열린 월간 향유회 오프와 KAIST RUN SPRING에서도 그랬다. 초반에 계속 잘하다가 마지막 1시간에 순위가 떡락하였다. 작년 SNUPC에서는 끝나기 1시간 전까지 1등(블루투스 이어폰)이었는데 11등(보조배터리)으로 마무리하는 일도 있었다.
구현 연습
문제점 (1) 에 대한 해결책으로는, 풀이는 알지만 구현량은 어느정도 있는 문제들을 최대한 많이 구현해보는 것이 좋겠다고 생각했다.
내가 예전에 풀었던 문제 중 난이도가 플레티넘5~3이고 웰노운인 100문제를 골라 C++ only, 템플릿 모두 금지(코드그라운드 노트의 Network Flow는 사용가능)로 모두 풀기를 도전하였다. 이렇게 하는 게 구현력을 단기적으로 올릴 수 있는 가장 좋은 방법이라고 생각했다.
그런데 본계정으로 이미 푼 문제를 또 풀면 재미가 없어서, 부계정을 만들어 티어, 태그 다 끄고 처음푸는것처럼 다시 풀었다.
결과적으로 100문제중 97문제를 9일만에 해결하였다. 후술할 SCPC기출 버추얼도 같이 하고있는 상태였기에 이정도면 열심히 한 것 같다.
풀지 않은 3문제는 MCMF(최소비용최대유량) 문제였는데 이건 나오면 버리자는 마인드로 유기해버렸다. 결국 안나왔으니 아무튼 좋은 선택이었음 ㅇㅇ
이러한 연습을 통해 LCA, O(1) RMQ, 레이지 세그먼트 트리, 트라이, 이분매칭 등 대부분의 골드~플레티넘 하위 난이도 알고리즘들을 눈감고도 1~2분 이내에 짤 수 있게 되었고, DP문제의 구현도 빨라진 것 같다. 또한 이 과정에서 O(NlogN) Suffix Array, LCP, Manacher, SCC, 2-SAT을 완벽하게 외웠고, 코드그라운드 노트의 Network Flow 템플릿 쓰는 법을 많이 연습하였다.
추가로 대회 며칠 전에 저 문제 리스트에 없는 PST, BCC, 랜덤 정수 생성 코드를 외웠다.
구현연습은 이정도면 할만큼 했다고 생각했다. 사실 100문제 더 뽑아서 풀고 싶었지만 시간이 부족했다. ICPC 전에 한두번 더 할 것 같다.
SCPC 기출 버추얼
그리고 대회 후반 운영이 딸리는 문제가 있었는데, 이는 내가 Codeforces/Atcoder만 열심히 하고 3~4시간셋을 평소에 많이 안 돌아서 그런것 같다고 생각했다. 그래서 4시간셋 도는 연습을 많이 하는 게 좋겠다고 생각했다.
마침 내가 SCPC 기출이 하나도 안 풀려 있었고, 2차 예선과 같은 불상사를 피하려면 SCPC 대회 사이트의 채점 방식에 익숙해질 필요도 있었다. 그래서 2021~2024년 대회 기출을 모두 4시간씩 실제 대회와 거의 같은 환경으로 버추얼(가상 대회)을 돌았다. 다만 실시간 만점자 수를 볼 수가 없어서 그냥 만점자 수를 보지 않기로 하였다. 따라서 본대회보다 약간의 패널티가 있었다고 할 수 있다.
결과는 다음과 같다.
- 2021년 : 200+130+250+143+99 = 822점 (2등상?ㅁㄹ)
- 2022년 : 100+100+88+0+0 = 288점 (4등상)
- 2023년: 100+200+200+0+0 = 500점 (4등상)
- 2024년: 100+200+39+120+0 = 459점 (4등상)
점수를 보면 대부분 앞문제를 열심히 풀어 고득점을 받고 뒷문제에서 거의 0점을 받는다. 이는 뒷문제를 열심히 긁지 않았다기보다는 앞문제 만점을 받기 위해 시간을 너무 많이 소모하여 시간이 남지 않은 것이다. 22~24년 모두 4등상인데, 앞문제를 조금만 더 빨리 풀어서 뒷문제를 조금 긁었다면 3등상도 노려볼만한 점수였다. 어쨋든 이런 전략으로 했는데 결과가 나쁘지 않았기 때문에, 이번 대회에서도 일단 앞문제 만점을 최대한 노리고, 시간이 남으면 뒷문제를 열심히 긁기로 하였다.
그리고 셋을 돌면서 의식적으로 후반에 집중하려고 노력했는데, 이렇게 노력했기 때문인지는 모르겠지만 끝나기 10분쯤 전에 100점 정도 올리는 일이 가끔 있었다. 대회때도 이런다면 맨날 프리즈후+0점받는 트라우마를 극복할수 있을 것 같았다.
물론 준비 기간 동안 위 2가지만 한 건 아니고, 틈틈이 백준에 들어가 어려운 문제나 구현해볼만한 문제들을 풀어주었다.
결론적으로 준비도 많이 하고 연습에서 4등상이 잘 나와서, 정배는 4등상, 정말 잘하면 3등상 받는 것을 목표로 대회를 보러 갔다. 3등상을 사실 많이 받고 싶었지만 아직 수상이 없었기 때문에 4등상 받아도 행복할 것 같았다.
4. 오프라인 본선 ( 08.29 )
4-1. 대회 전날 밤 ~ 대회 시작
나는 단기간에 쓸 수 있는 뇌의 총량이 정해져 있다고 생각한다. 그래서 대회 이틀 전까지는 위에 나온대로 열심히 대회를 준비하였지만, 대회 전날과 당일 오전에는 그냥 PC방가서 뇌빼고 롤을 하거나 넷플릭스에서 오징어게임을 보며 놀았다.
그리고 대회 전날부터 대회 당일 새벽까지 23:35~02:35에 Codeforces 라운드가 있었는데, 재밌어보여서 하고 싶었지만 꾹 참고 일찍 잤다. (현재 2405점이라 점수를 떨궈 오렌지인 상태로 SCPC를 치기 싫었던 것도 조금은 있다..)
디스코드에서 같은 대회 치는 사람들이랑 노가리 좀 까고 Codeforces 구경을 좀 하다가 1시반쯤 잠들었고, 오전 10시쯤 일어나 매우 푹 잤던 것 같다.
아침에 일어나 대충 씻고 11시쯤 출발했다. 대회장은 삼성전자 서초R&D캠퍼스였는데, 생각보다 가깝지는 않아서 버스 2개를 탄 뒤 12시쯤 대회장에 도착했다. 먼저 등록을 하고 대회장에 들어갔다. 티셔츠, 마우스, 키보드 등 기념품들을 받을 수 있었다.
일단 등록은 했지만, 점심을 먹지 않은 상태였기 때문에 swoon, pgggggggggh와 근처 분식집에 가서 밥을 먹었다. 밥먹는데 식당 앞에 leinad2 같은 사람들이 서있는 것 같았지만 평균레이팅이 2800인 집단 같아서 무서워서 말은 못걸었다.ㅠㅠ
그러고 다시 대회장으로 가서 동아리 사람들, 포스텍, 연세대 사람들이랑 인사좀 하고 노가리좀 까다가, 1시가 되니 자리에 앉으라고 했다. (대회시작은 1시 반이었다.) 그때부터 뭔가 안내를 해주고 컴퓨터에 로그인하여 세팅을 할 수 있었다.
여기서 매우 큰 문제가 있었다. 내가 사용할 줄 아는 유일한 IDE(코드 돌리는 프로그램)인 VSCode에서 C++가 컴파일이 되지 않았다! 처음에는 C++확장 자체가 깔려있지 않았는데, 안내하시는 분이 깔려있는 확장 외에 쓰지말라고해서, ??그럼어카라는거지 라고 생각했다. 그런데 C++확장 설치버튼을 이미 눌러버려서 설치를 기다리고 있었는데, 설치가 안 되고 있었다. 일단 대회가 시작하고도 컴파일이 안되는 불상사는 피해야 하니까, 6년 전에 C언어 처음 배우면서 딱 한 번 써 본, 사용법도 모르는 또다른 IDE인 CodeBlocks를 켜 세팅을 했다. 어떻게 하는지 몰라서 대충 뜨는거 아무거나 눌렀는데, 다행히 실행이 잘 되었다. 얘는 아무거나 눌러도 실행이 잘되는데 VSCode는 왜이러냐? 이러는 도중 한번 직원을 불러 도와달라고 했는데, 잘 모르겠다고 다시 오겠다고 하신 뒤 사라졌다. 그리고 그 사람은 대회가 끝날 때까지 다시는 볼 수 없었다...
그런데 갑자기 VSCode C++ 확장이 설치되었다. 기억이 맞다면 10분정도 걸렸는데 안되는 게 아니라 그냥 느렸던 것 같다. 어쨋든 확장 설치가 되었으니 이제 되겠지? 했는데 똑같이 컴파일이 안 되었다. 아마 컴파일러 경로가 지정이 안돼있어서 그랬던 것 같다. 주위를 보니 다들 비슷한 문제를 겪고 있길래 대회측에서 공지를 해 줄 거라 믿었지만..아무일도 없었다. 다시한번 손을 들어 직원에게 도움을 요청하니, 그 사람도 모르겠다고 다시 와서 알려주겠다고 하신 뒤 사라졌다. 이때가 아마 1시 20분(대회 시작 10분 전)쯤이었는데, 대회가 이대로 시작해 VSCode를 쓸 수 없을까봐 너무 쫄렸다.
그러던 중 대회가 1시35분으로 5분 연기되었다. 그래서 아하 나같은 사람들을 위해 연기해줬구나 다행이다..라고 생각했는데 아까 다시오겠다고 했던 직원분이 오시더니, "경로 지정 문제인거같은데 이건 도와줄수없고 알아서하셔야한다" 라고 말씀하시는 것이다.. 이때가 대회시작 5분 전인 1시 30분이었다.
아니 그러니까, 직원분한테 도움 요청하니까 도와주실 것처럼 얘기했다가 사라지고, 다른 직원분한테 도움 요청하니까 도와주실 것처럼 얘기했다가 대회시작 5분전에 오셔서는 알아서 하라고 말했다는 것이다.. 차라리 처음부터 못도와준다고 했다면 스스로 세팅하는 법을 알아보거나 아는 참가자에게 도움을 요청하거나 CodeBlocks의 사용법을 연습했을 것인데, 한동안 안 오다가 대회시작 5분전에 와서 갑자기 안된다고하면 진짜 뭐 어쩌라는 것인가? 정말 이해가 되지 않는 부분이었다.
그런데 지금 중요한건 그게 아니었다. 어쨋든 이 사람들은 날 도와줄 생각이 없었고, 나는 5분뒤에 이때까지 참가한 대회중 나에게 가장 중요한 대회를 쳐야 했다. 아는 참가자에게 달려가 도움을 요청할까도 생각해 보았지만 대회 5분전에 갑자기 불러서 도와달라고 하는 건 그사람의 대회퍼포먼스를 떨어뜨릴 수 있는 이기적인 행동인 것 같아 포기하였다. 디스코드에도 긴급하게 질문했지만 답을 얻을 수 없었다..
그나마 CodeBlocks가 실행이 되었지만 그냥 helloworld 코드를 테스트해본 정도였고, C++버전이 몇인지도 몰랐고 내가 VSCode에서 사용했던 기능들이 똑같이 잘 작동할 것이라고 확신할수는 없었다. 게다가 남은 시간에 CodeBlocks를 조금 써 보니까, 단어별 색깔도 내가 쓰던 거랑 너무 달라 헷갈리고.. 글자가 너무 작은데 ctrl +를 눌러도 글자가 안커지고..tab이 4칸이 아니라 2칸이고.. 몇개의 중괄호 안에 들어와있는지에 따라서 엔터칠때마다 들여쓰기가 자동으로 되었으면 좋겠는데 안해주고.. 내가 평소 코딩하던 습관이랑 하나도 맞지 않아서 여기서 코딩하면 코딩시간이 10배는 걸리겠다고 생각하고 절망했다. helloworld 코드를 짤 때도 한 2~3분 정도 걸렸던 것 같다. 바꾸는 설정 같은 걸 찾아보았는데 다 처음 보는 버튼이라 도저히 찾을 수 없었다. 오히려 더 망쳐서 컴파일도 안 될까봐 아무 버튼이나 누를 수 없었다.
이때 멘탈이 완전히 나가 있었다. 이 중요한 대회를 연습했던 환경에서 칠 수 없다고? 말도안돼... 현실감이 없었다. 그래도 일단 대회 시작 1분 전이라 어떻게든 대회를 치긴 해야겠으니 최대한 정신을 붙잡고 좋은 방법이 뭘까 고민했다. 내가 생각하기에 최선의 판단은 익숙한 환경인 VSCode에서 코드를 다 짠 뒤 CodeBlocks에 복붙을 하고 거기서 컴파일하고 테스트를 하는 것이었다. 이러면 코딩할 때의 불편함은 거의 없고 테스트할 때만 시간이 좀 더 걸리는 방법이었다. 지금 생각해 보니 짧은 시간에 아주 좋은 판단을 내린 것 같다. 만약 CodeBlocks에서 처음부터 끝까지 코딩을 했다면 대회 중간에 포기하고 잠이나 잤을 것 같다.
실제로 대회가 끝날 때까지 그렇게 왔다갔다 하며 진행하였는데, 불편했던 점은 다음과 같다.
- VSCode와 CodeBlocks, 대회 문제 사이트를 왔다갔다 해야 하다보니 매우 어지럽고 자잘한 시간 소모가 많았다. Alt+tab을 몇초에 한번씩 계속 연타하는 일이 빈번하게 발생했다.
- VSCode의 컴파일러 설정이 안되어 있다 보니 코딩할 때 오타가 있어도 빨간줄로 에러를 보여주지 않았다. CodeBlocks로 옮긴 뒤 실행해보고 그제서야 컴파일 에러를 알 수 있었다.
- CodeBlocks에서 코드를 실행하면 VSCode처럼 아래의 터미널 칸에서 실행 결과가 보여지는게 아니라 새로운 콘솔창이 열려서 보여주고, 이 콘솔창을 직접 꺼야 다음 실행이 가능해서 매번 꺼 주어야 한다. (처음엔 이것도 몰라서 콘솔창 안끄고 아니왜실행이안되지??하고 얼타다가 알아냄)
- 코드를 VSCode에서 CodeBlocks로 옮길 때와 예제 입력을 불러올 때 모두 ctrl+c, ctrl+v를 이용하다 보니, 복사된 텍스트가 계속해서 갱신된다. 평소같았으면 예제를 한번 복사해둔 뒤 코드를 고치며 ctrl+v만 눌러서 테스트할 수 있었겠지만, 코드를 고치고 테스트할 때마다 매번 대회 사이트에 다시 가서 예제를 다시 복사해야 했다.
- 코드에 사소한 오타가 있으면 CodeBlocks에서 수정할 때도 있었고 VSCode에서 수정할 때도 있었는데, 이러다 보니 뭐가 가장 최신 수정본인지 헷갈려서 가끔 최신 수정 이전 코드를 제출하였다. 이 문제로 컴파일에러 패널티를 2번 받는 일이 있었다.
생각나는 건 이 정도가 있는 것 같다. 대회중에는 생각안하고 그냥 어쩔수없지 하고 했었는데, 이렇게 적어보니 심각한 문제는 없었지만 사소한 문제들이 쌓여 시간과 패널티를 조금조금씩 갉아먹은 것 같다. 사실 시간 손해보다는 멘탈에 피해가 좀 더 컸다. 뭐 이런걸로 멘탈이 나가냐 라고 생각할 수 있지만, 최고의 환경, 최고의 컨디션이더라도 평소만큼 하는것조차 어려운 게 대회인데 최악의 환경에서 대회를 쳐서 잘 할 거라고 생각할 수 있는 사람은 별로 없을 것이다. 어떻게 정신 안나가고 계속 코딩을 했는지 모르겠다.
어찌됐든 이런 상황에서 상당히 불안한 상태로 대회를 시작하였다.
4-2. 대회 중 (풀이는 자세하게 쓰지 않고 어떤 일이 있었고 그때 어떤 생각을 했는지를 중점적으로 썼다.)
환경설정에서 멘탈이 완전히 갈렸던 것과 별개로, 문제풀이 자체는 생각보다는 순조롭게 진행되었다.
시작하자마자 1번을 읽었는데, 왼쪽위부터 오른쪽아래 점까지 보면서 그 점과 같은 2*2 정사각형에 포함되지 않는 왼쪽위 점들로부터 갱신을 받아오는 DP를 하면 되겠다고 생각했다. 처음에 구현한 뒤 CodeBlocks에서 실행해서 예제를 복붙해 보니 갑자기 프로그램이 종료되고 콘솔창이 꺼져버렸다. 한두번 더 실행을 해 봐도 똑같이 돼서, 아니 CodeBlocks는 입력을 못 받나? 하고 다시 절망에 빠질 뻔 했는데, 코드를 보니 입력 배열을 선언만 해놓고 입력받는 코드를 까먹고 안 써 놓았다는 걸 발견했다. 그걸 쓰니 다행히 잘 실행이 되었다. 근데 예제가 안나와서, 코드를 다시 보니 DP를 잘못 구현한 부분이 있어서 두어 번 고친 뒤 예제가 나와 제출하니 만점을 받았다. (100점, +11분, 제출1회)
2번은 딱봐도 나 애드혹해구성이에요 광고를 하는 문제였다. 평소에 이런 문제를 즐겨 풀기 때문에 잘 할 수 있겠다고 생각했다. 처음에는 세그먼트 트리 느낌으로 분할정복을 해서 푸는 게 아닌가 생각했지만, 뭔가 잘 안되어 포기했다. (실제로 그렇게 푼 사람도 몇 명 있다고 한다.)
N개를 k개씩 묶은 뒤 각 묶음에 대해 2^k개의 모든 조합을 전처리해두고 묶음 하나씩 더해주는 풀이를 생각하였다. 이렇게 하면 연산이 대략 N/k*(2^k+N)만큼 필요하다. N이 최대 1000이므로 k=10이면 20만 정도의 연산이 필요하다. 문제에서 요구하는 것은 156,000 이하의 연산이었으므로 약간 부족했다.
k가 몇이어야 N/k*(2^k+N)이 최소가 되는지 모르겠어서 k에 대해 미분하고 근을 구하는 것을 시도하였으나 잘 되지 않았고, 일단 k=10으로 한 뒤 코드를 짜고 나서 생각하기로 했다. 하지만 k=10이 최적이라는 확신은 없었기 때문에 모든 부분에 10이 아닌 k를 적어 두고 맨 위에 "const int k = 10;" 으로 선언하여, 이 값만 바꾸면 자동으로 다른 k를 쓰는 코드가 될 수 있게 하였다. 근데 문제가 구현이 꽤 귀찮아서 시간이 좀 많이 소요되었다. 일단 구현을 마치고 k=10인 코드를 제출하니 38점을 받았다. (138점, +51분, 제출2회) (이전에 연습하면서 버추얼 돌 때 보니까 패널티로 갈리는 경우는 거의 없길래 제출 횟수 패널티는 신경 안 쓰기로 하였다.)
계산해보니까 38점 정도 받는 게 정상이어서 구현이 틀리지 않았구나 하고 안도하였다. 이제 다른 k에 대해 시도해봐야 하는데, 하나씩 제출해보긴 좀 그러니 k를 입력받아 N/k*(2^k+N)를 출력하는 코드를 짜서 이를 각각 계산해보고, k=8일 때 157,000으로 최소임을 알 수 있었다. 일단 k=8로 하고 제출했는데 갑자기 0점을 받았다. 코드를 보니 k가 아니라 상수10을 쓴 부분이 하나 있었다. 10을 k로 고치니 만점을 받았다. 157,000은 제한인 156,000보다 높은 연산횟수이긴 하지만, 사실 초기값을 1000개정도를 줘서 그건 계산할 필요가 없고, 그거 말고도 조금씩 줄어드는 부분이 있다는 것을 알고 있었어서 그런가보다 했다. (300점, +56분, 제출4회)
300점을 받고 순위표를 보니 1등부터 15등정도까지 300점이었고 나는 15등이었다. 18등까지 4등상이고 이미 수상 횟수를 채운 사람들(상을 2회 이상 받은 사람은 2~4등상 수상에서 제외된다.) 때문에 실제로는 약 25등까지 4등상을 받을 수 있어서, 15등 정도면 나쁘지 않은 출발이라고 생각했다. 그런데 3~4번에서 점수를 받은 사람이 없어서 뭘 풀어야 할지 모르겠는 상황이었다. 일단 3번과 4번이 모두 300점짜리 문제길래 난이도가 비슷할 것이라 생각해 두 문제 모두 읽었다. 그런데 4번은 문제를 이해하는 데 조금 시간이 걸릴 것 같아 보였고, 마침 3번에서 15점을 받은 사람이 나오길래 일단 3번을 시도하기로 했다.
3-1번 서브태스크인 15점짜리 문제부터 풀어보기로 했다. 1, 2, 3으로 이루어진 배열의 매칭이 존재하는지 판정하면 되는 문제였는데, 2들 중 몇개를 3과 매칭하고 몇개를 1과 매칭할 지는 개수에 따라 유일하게 결정할 수 있었다. 그리고 그런 2들 중 3과 매칭하는 2가 1과 매칭하는 2보다 오른쪽에 있을 이유가 하나도 없다는 관찰을 할 수 있었고, 매칭이 존재한다면 2들 중 왼쪽 몇개는 3과 매칭하고, 오른쪽 몇개는 1과 매칭하는 게 가능해야 한다는 사실을 발견하였다. 그래서 이를 판정하는 것을 구현하였다. 구현이 15점치고는 상당히 귀찮고 실수할 부분이 많아서, 구현 실수로 3번 틀린 뒤 15점을 받았다. (315점, +98분, 제출7회)
이제 다른 서브태스크들을 읽었는데, 본문에 주어진 제한 이외의 추가적인 제한이 없는 서브태스크가 존재하지 않는다는 사실을 발견했다. 또한 4~5번 서브태스크가 K=3이고 N제한도 작아 의외로 쉬울 수 있겠다는 생각을 했고, 마침 스코어보드에 서브태스크 1, 4, 5를 풀고 141점을 받은 사람이 한 명 있길래 이를 먼저 생각해보기로 했다. 서브태스크 4는 N<=20, 5는 N<=200이기 때문에 15점 풀이를 확장하여 DP를 하면 되지 않을까 했다. 2들 중 왼쪽 몇개는 3과 매칭하고, 오른쪽 몇개는 1과 매칭하면 된다는 사실을 이용해, 왼쪽부터 보면서 초반에는 2를 오른쪽 3과 매칭하기를 기다리게 해 두다가 특정 점부터는 2를 왼쪽 1과 매칭시켜주는 DP를 하기로 했다.
구체적으로는 DP[왼쪽부터 몇개 봤는지(0~2N)][왼쪽의 매칭되지 않은 1개수(0~N)][왼쪽의 매칭되지 않은 2개수(0~N)][2를 왼쪽으로 매칭하기를 시작했는지 여부(0~1)] = 해당 경우의 수 이다. (대회 12일 전에 풀었던 문제가 떠올라 식을 빨리 세울 수 있었다.) DP 전이식은 조금 더 생각해봐야 하는 부분이 있지만 이렇게 큰 그림을 잡고 나면 할만하다. 시간 복잡도가 O(N^3)이기 때문에 서브태스크 4와 5를 한번에 긁을 수 있을 것이라 생각하고 바로 구현했다.
구현하고 디버깅하고 예제가 나와 제출했지만 Segmentation Fault로 0점을 받았는데, 디버깅을 해봐도 도저히 왜인지 모르겠어서 N<=20일 때만 DP를 하고 나머지는 0을 출력하게 했더니 갑자기 15점을 받았다. 뭔가 이상해서 N<=200일때만 DP를 하기로 바꾸니까 72점 (서브태스크 1+4)을 받았다. (372점, +140분, 제출10회)
알고보니 내가 생각한 N이 문제에서 2N이라 코드 기준 N<=400으로 했어야 맞는 풀이었다. 그런데 N<=200으로 생각해서 DP배열도 D[200][100][100]를 잡아 문제가 생긴 것이고, 서브태스크 분리도 N<=400으로 해야 했다. 이 두 개를 알아내는 데 각각 몇 번씩 더 틀리고 마침내 141점을 받을 수 있었다. (441점, +140분, 제출13회) (1분이 안 되는 시간동안 제출을 4번이나 했다.)
441점을 받고 순위표를 보니 전체 8등이었다. 그래서 대충 뒷 문제로 가서 부분점수를 몇점 더 긁으면 4등상은 받을 것 같다고 생각했다. 그래서 뒷문제 부분점수 긁기 vs 3번 만점 노리기 라는 선택의 기로에 놓였다. 연습할 때 만점을 노린 경우가 많았고 결과가 나쁘지 않았기 때문에 3번 만점을 받고 나머지를 긁어 3등상을 노리기로 했다.
3-2번과 3-3번을 보니 3-1번의 풀이에서 2를 1, 3에 매칭하는 걸 2, 3을 1, 4에 매칭하는 걸로 확장시켜 생각하는 게 좋아 보였다. 그런데 2를 오른쪽으로 매칭하다가 왼쪽으로 매칭하기 시작하는 지점과, 3을 오른쪽으로 매칭하다가 왼쪽으로 매칭하기 시작하는 지점이 일치한다는 보장이 없었다. 그러나 대충 예제를 몇 개 써보니 그렇게 가정해도 되는 것처럼 보여서, 그냥 그렇다고 믿기로 하고, 각 매칭 방향 변화 지점에 대해 한 번씩 가능한지 확인해 보는 O(N^2) 풀이를 구현해 제출했으나 점수를 받지 못했다. (441점, +187분, 제출14회)
이때 순위표가 프리즈되어 더이상 사람들의 점수를 확인할 수 없었다. 수정을 반복하며 계속 제출해봐도 틀려서 가정이 틀렸음을 의심하게 되었다. 가정이 틀렸다면 (2의 매칭 방향 변화 지점, 3의 매칭 방향 변화 지점)에 대해 한 번씩 가능한지 확인해 보는 O(N^3) 풀이가 가능했으나, 서브태스크 2가 N=5000(아마?)이었기 때문에 점수를 얻을 수 없었다. 그런데 조금 더 생각해보니 2의 매칭방향 변화지점이 결정되면 3의 매칭방향 변화지점이 유일하게 결정된다는 것을 알 수 있었다. 그래서 O(N^2)풀이를 구현할 수 있었고, 제출하니 192점을 받았다! (492점, +198분, 제출19회)
이제 3-3번을 생각해보았는데, 도저히 위 풀이를 O(N)으로 최적화할 방법이 생각나지 않았다. 그렇다고 새로운 풀이를 찾자니 시간이 40분밖에 남지 않았고, 이미 머리를 많이 써서 집중이 잘 되지도 않았다. 그래서 프리즈되기 전에 사람들이 많이 풀었던 5-1번과 5-2번을 마지막으로 풀고 끝내자고 생각했다.
5번을 읽어보니 5-1번은 TSP를 그대로 짜면 되는, 거의 공짜 점수였다. 그래서 이걸 짜고 24점을 받았다. (516점, +215분, 제출20회)
서브태스크 2는 그래프가 완전그래프 느낌으로 주어지는 문제였는데, 간선이 충분히 많으니 반드시 길이 N인 경로가 존재하지 않을까 생각했다. 그래서 SCC를 구한 뒤 거기서 그리디하게 정점을 찾아주면 된다고 생각했고, 맞는 풀이라고 착각했다. 그런데 구현해서 제출해보니 틀렸다. (516점, +233분, 제출21회)
다른 예제들을 넣어 보다가 풀이가 틀린 부분이 있음을 알게 되었고, 남은 시간 7분동안 다른 방법들을 생각해 보다가 제대로된 방법을 찾지 못하고 대회가 종료되었다.
최종 점수는 다음과 같다. (516점, 패널티 215+7*21분)
4-3. 대회 후
잘 본 대회에서 가장 떨리는 순간은 대회가 끝나고 시상식이 진행되기 전까지이다. 참 오랜만에 느껴보는 기분이었다.
내 점수와 프리즈 전의 스코어보드를 생각하면, 3등상이나 4등상을 받을 것이라고 예상했다. 다만 3등상 인원이 많지는 않아서 4등상이 조금 더 가능성 높다고 생각했다.
하지만 내가 4번을 시도해보지 않아서 4번이 쉬운지 어려운지 잘 몰랐고, 사람들이 프리즈 후 4번에서 점수를 많이 올렸다면 내가 상 못받는것도 불가능은 아니라고 생각해서, 약간 불안하기도 했다. 매 대회마다 프리즈 후 떡락하는 일을 겪어왔기 때문이다.
무슨 상을 받을지, 상을 못받을지 아직 몰라서 너무 쫄렸고, 그래서 사람들에게 점수나 잘 봤는지 이런 것들을 거의 안물어보고 그냥 혼자 짱박혀서 기도나 하고 있었다.
생각보다 다른 일정들이 굉장히 빨리 끝나서, 바로 시상식이 진행되었다. 먼저 AI 부문의 시상이 진행되었다.
다음으로 알고리즘 부문의 시상이 시작되었고, 특별상 수상자들이 먼저 호명되어 상을 받았다.
이제 4등상 수상자를 부를 차례가 되었고, 이때 손을 떨면서 기도하고 있었는데, 4등상에 내 이름이 있었다!
그래서 최종적으로 4등상을 수상하였다. 상금은 무려 200만원이나 준다고 한다. 사실 3등상이었으면 좋겠다고 기도한 것도 있긴 하지만, 4등상을 받았는데도 기분이 매우 좋았다. 알고보니 1/2/3/4등상 컷은 1015/빠른960/630/390점으로, 내가 516점이니 이러나 저러나 4등상 받을 점수였던 것 같다.
앞에 나가서 상장도 받았다. 4등상 받으러 가니까 SCPC 수상이 2번째이신 leo020630님과 ystaeyoon113님이 계셔서 반갑게 인사하였다. 이분들과 같은 상을 받을 수 있다니 정말 기뻤다.
대회가 끝나고 수상자 OT라는 게 있다길래 뭐 재밌는 게 있나 하고 기대했는데, 그냥 "등록 데스크 가서 계좌번호 적고 동의서에 사인하세요~~" 하는 거였다.
대회가 끝나고는 사람들이랑 치킨집을 가서 치킨을 먹고, 술을 많이 마신 뒤 집에 가서 잤다.
5. 후기
솔직히 3등상을 기대했기에 4등상 받으면 그냥 적당히 그런가 보다 할 줄 알았는데, 막상 받고 나니 기분이 매우 좋았다. 사실 지금도 좋다. 이때까지 연습때 잘 하다가 대회때 망해서 상 못받고 마무리하는 패턴을 약 2~3년 동안 반복했기 때문에, 이번에도 그러는거 아닌가 걱정했다. 그리고 대회 시작 전 세팅하면서 말렸을때 진짜 그렇게 되는 미래가 보여서 멘탈이 나갈 뻔 했었다. 근데 드디어 극복하고 상을 받았다! 상도 받고 돈도 받고 SW멤버쉽 가입도 할 수 있으니, 드디어 3년동안 꾸준히 열심히 공부한 것의 대한 결과? 보상?을 하나씩 받을 수 있게 된 기분이다. 3년을 꼬라박아야 결과물이 나온다니 이 얼마나 가성비 딸리는 일인가? 근데 뭐 재밌었으니 됐다.
하지만 3년을 꼬라박아서 SCPC 4등상 하나 받고 이렇게 호들갑 떨고 끝? 이건 말이 안 된다. 이번 수상은 시작일 뿐이고, 앞으로 계속 성장해서 더 높은 곳까지 올라가고자 한다. 낮은 곳에서 시작해서 이때까지 계속 올라왔고, 이번에 내가 꽤 높이 올라왔다는 것을 증명했다. 그렇다면 더 높이 올라가지 못할 이유가 뭐가 있겠는가?
이번 대회에서 잘 한 부분도 많지만 부족했던 부분도 많다. 뭔가 대회 전체적으로 집중이 잘 안 되었다. 아마 많이 긴장해서 순위표를 계속 쳐다보고 딴생각을 하는 등 문제에 온전히 집중하지 못했던 것 같다. 이것 때문인지 모르겠지만 구현할 때 삽질을 너무 많이 하고 제출할 때마다 계속 틀려서 패널티를 예상보다 훨씬 많이 적립하였다. 별개로 후반에는 체력이 딸려서 후반 집중력이 아직 많이 부족한 느낌도 들었다.
하지만 반대로 말하면 이런 문제점들을 극복하면 훨씬 더 좋은 결과를 낼 수도 있다는 것이다. 그리고 아직 공부하지 않은 내용들도 아주 많다. 따라서 이번에 느낀 문제점들을 잘 피드백하고 다시 앞으로의 대회들을 잘 준비해서, 좋은 결과를 내 보도록 하겠다.
올해 남은 대회는 당장 다다음주에 열리는 SNUPC, 10월에 열리는 KAIST RUN 대회(확정아님), ICPC 예선, 11월에 부산에서 열리는 ICPC 본선이 있다. 사실 다른 대회는 즐겜하는 느낌이고 ICPC를 1년동안 열리는 대회 중 가장 중요하다고 생각하고 있기 때문에, 남은 시간 동안 ICPC 준비만 할 계획이다. 수상하고 다시 후기로 돌아오겠다.
긴 글 읽어주셔서 감사합니다 !