어제 2025 SNUPC에 참가하였다. 사실 결과와 별개로 과정이 만족스럽지 않았기 때문에 후기를 안 쓸까 하다가, 그냥 망한 것도 경험이고 그 과정에서 얻은 것도 꽤 있었다고 생각해서 후기를 쓰게 되었다. 그냥 앞으로 참가하는 모든 대회에서 후기를 쓰면 좋겠다.
0. 배경
서울대학교에서는 매년 2종류의 PS 대회가 열린다. 5월에는 중앙 컴퓨터 동아리 SCSC에서 여는 SCSCPC가 있고, 9월에는 컴퓨터공학부 PS동아리 SNUPS에서 여는 SNUPC가 있다.
SCSC 대회는 내가 2년째 운영/출제/검수를 하고 있기 때문에 참가할 수 없고, 그래서 SNUPC에만 매년 열심히 참가하고 있다. 올해도 역시 9월에 SNUPC가 열렸고, 이번 9월 13일에 2025 SNUPC에 참가하였다.
SNUPC는 학교에서 하는 동아리 대회인 만큼, 공식 대회인 ICPC/SCPC와 달리 상을 받아서 얻는 이득이 작은 상품(+기분좋음)밖에 없다. 그래서 큰 부담 없이 친구들끼리의 경쟁을 즐길 수 있는 대회이면서, 앞으로의 큰 대회들을 위한 연습 및 실력 테스트 느낌으로 생각할 수 있는 대회이다. 따라서 최대한 열심히 하되, 또 재미있게 하자!는 생각으로 참여하고 있다.
SNUPC는 초심자들을 위한 Division 2와 고인물들을 위한 Division 1로 나뉘어져 있고, Codeforces 2100+ 또는 서울 리저널 본선 진출 기록이 있으면 Division 1로 참여하게 된다.
나는 2023, 2024년에는 Division 2로 참가하였고, 각각 4, 11등을 했다. 작년에는 사실 Division 2에서 상위권을 해야 하는 실력이었던 것 같은데, 스코어보드 프리즈 전(끝나기 1시간 전)까지 1등이다가 F(골드1)를 패싱하고 G(플레티넘2)에 모든 시간을 태우는 기적의 판단(...)으로 멸망하였다. 뭐 그런 판단도 실력이다. 그때는 경험 부족으로 판단 능력이 모자랐던 것이다. 그리고 당시 1등은 F와 G를 둘 다 풀었기 때문에 완벽한 실력패이기도 하다.
그런데 이번에는 Division 1 기준을 충족하여 고인물들 사이로 끌려가게 되었다. 그래서 1~2등을 해서 매우 좋은 상품을 받는 것은 힘들다. 그래도 높은 등수를 받으면 기분도 좋고 남들이 인정해주기도 하고, 열심히 한 대회 경험으로써의 의미가 있기 때문에, 열심히 해서 최대한 높은 등수를 받아보고자 했다.
1. 대회
대회 전
원래는 대회때 잘 하고 싶어서 기출문제도 풀고 준비를 열심히 하려고 했는데, 대회 4일 전에 매우 심한 감기에 걸렸다.. 그래서 준비는 따로 하지 못했고, 대회날도 컨디션이 좋을 것 같지는 않았다. 그래서 올해 마지막 남은 개인 대회인데 제대로 하지 못할 것 같아 많이 아쉬웠다.
대회날 아침에 일어났을 땐 컨디션이 괜찮았다. 그래서 감기 다 나았나? 싶었는데 점심을 먹고 대회장으로 가니 갑자기 머리가 많이 아프고 어지러웠다. 그리고 감기약 부작용인지 머리가 뭔가 멍하고 생각이 잘 안되는 상태였다. 그래서 그냥 대충 뇌빼고 해보고 잘 풀리면 열심히 풀자고 생각했다. SCPC때는 긴장해서 어느정도 뇌빼고 풀었는데 잘 풀렸기 때문에, 오히려 뇌빼고 푸는 게 너무 많이 생각하는 것보다 더 나을 수도 있겠다는 생각도 있었다. (실제로는 그렇지 않았다.ㅠ)
대회 시작 전까지는 아는 사람들이랑 인사좀 하고 "오늘1등할게요" "님1등하면밥사주셈" 같은 의미없는 말이나 하며 시간을 떼웠다. 원래 대회 시작은 1시였는데 1시 10분으로 연기되었고, 1시 10분에 대회가 시작하였다.
대회 중
A번을 읽었는데 브루트포스를 열심히 하면 되는 문제였다. 백트래킹으로 풀 수도 있지만 비트마스킹과 6진법 비트마스킹(?)을 이용해 간단하게 구현할 수 있었다. Python으로 빠르게 짜서 한 번에 맞았다. (1솔브, 0:07, 6등)
그리고 B를 봤는데 여기서 매우 큰 문제가 발생했다. 문제를 읽어보니 Digit DP를 하면 되는 것 같아 아무 생각 없이 짰다. 근데 짜고 나서 읽어보니까 O(N^3)인 것이다. N=1000이었기 때문에 N^3이면 안 돌 것 같아서, 이걸 N^2 * 10(숫자 개수) 로 줄여야하는 것 같았다. 생각해보니까 어떤 그리디한 성질이 성립하는 것 같아서 그걸 이용한 조금 복잡한 풀이를 시도해볼까 했다.
그런데 이건 대회에서 2번째로 쉬운 문제이고 많은 사람들이 빠르게 풀었는데, 그런 풀이가 답은 아닐 꺼라고 생각했다. 문제는 감기 때문인지 감기약 때문인지 아니면 원래 내가 이런 문제에 약한 것인지 모르겠지만 머리가 하나도 돌아가지 않았다. 도저히 다른 풀이를 생각할 수 없어서 그냥 울며 겨자먹기로 그리디 성질을 이용한 DP를 구현하기로 했다. 연산량이 1000만이 넘기 때문에 C++로 구현했다. 구현하고 제출했지만 6번 연속으로 WA(Wrong Answer)를 받았다. (놀랍게도 5번은 구현 실수이고 마지막 1번이 내가 생각한 풀이의 제대로 된 구현이다. 왜그렇게 구현을 못했는지는 잘 기억이 나지 않는다.)
6번째 WA를 받고 도저히 어디가 틀렸는지 모르겠어서, 처음에 짜둔 O(N^3) 코드와 함께 스트레스 테스트를 돌렸다. 반례가 바로 나왔는데, 반례를 보니 내가 생각한 그리디 성질이 틀렸다는 것을 알게 되었다. 이때가 대략 80~90분쯤이었고, 참가자 26명 중 19등이었다. 망한 것 같다고 생각했다. 처음부터 대충 치기로 했으니까 별로 신경은 안 썼고, 그냥 다른 문제나 풀자 하며 뒤로 넘어갔다. 평소처럼 머리가 그렇게 안돌아가지 않았다면 B를 버리고 C로 넘어가는 판단을 좀 더 빨리 했을 수도 있었겠다. (했어야 한다.)
그런데 C를 읽어보니까 좋은 풀이가 생각났다. 투 포인터를 하면서 두 포인터 사이에 있는 구간에 대한 DP 테이블을 관리하는 것이다. 이때 DP 테이블은 DP[x] = (A[p1...p2]의 부분수열 중 합이 x인 것의 개수) (0<=x<=100)이다. 그런데 DP테이블 값이 지수적으로 커질 수 있어서 long long 범위를 벗어날 수도 있었다. 만약 해싱 느낌으로 modulo를 잡아 준다면 저격데이터가 없는 한 괜찮을 것이라고 생각했다. 대충 출제자가 예상하지 못할 것 같은 상수 하나를 잡고, DP값은 그 상수로 나눈 나머지로만 관리하였다.
바로 구현을 했는데, 왼쪽 포인터가 움직여 한 원소가 사라지면 이에 따른 테이블 업데이트를 하는 방식에 문제가 있었다. 처음에는 원소를 추가할 때처럼 큰 수부터 전이해주면 된다고 생각했는데, 예제가 안 나와서 생각해보니 그렇게 하면 안 된다는 걸 깨달았다. 그래서 원소 삭제 업데이트를 어떻게 할 지 생각해야 했다. 애초에 안 되는 풀이였나 하고 이 문제도 망하는건가 했지만, 계속 생각해 보니 그냥 똑같이 하되 작은 수부터 전이해주면 된다는 것을 알 수 있었다. 마찬가지로 연산량이 1000만이 넘기 때문에 C++로 구현했고, 한 번에 맞았다. (2솔브, 1:47, 19등 → 17등)
문제를 풀었는데도 17등이라니 진짜 망했다고 생각했다. D를 읽었는데 해구성 문제였다. 처음에는 삼각형들로 이루어진 트리를 만들어야 한다고 생각했지만(비슷하게 풀리는 문제를 풀어본 적 있다.) 그냥 트리 안 만들고 무지성 BFS하면 알아서 잘 된다는 것을 생각해냈다. Python으로 매우 간결하게 구현할 수 있었고, 제출했는데 한 번 틀렸다. 테스트케이스를 손으로 몇 개 만들어 넣어 보니 반례를 찾을 수 있었는데, 알고보니 구현에서 신경쓰지 않은 부분이 하나 있었다. 수정해서 제출하니 맞았다. (3솔브, 2:16, 17등 → 16등)
1문제 더 풀었는데도 16등이었다. 스코어보드를 보니 15등까지 4솔브 한 사람들 줄이 쭉 세워져 있었고, 극소수만이 5솔브인 상태였다. 그래서 일단 4솔브를 해야 한다고 생각했다.
그리고 이때쯤 컨디션이 상당히 괜찮았다. B를 풀때만 해도 머리가 어지러워서 엎드려 자고 싶었는데, C와 D가 잘풀리니 멘탈이 괜찮아져서인지 아프다는 느낌은 별로 안들었다. C를 푼 뒤 감기약을 한 번 더 먹었는데 이것 때문일 수도 있겠다. (아침에 늦게 일어나서 아침 약을 못 먹고, 점심에 아침약을 먹어서 3시쯤 대충 대회장에 있는 과자로 점심약을 떼웠다.) 사실 감기약 먹으면 졸릴까봐 원래는 대회 끝나고 먹을 계획이었는데, 이미 자포자기 상태였어서 먹은 것이고, 이게 오히려 도움이 된? 것 같다.
그러고 B를 다시 보러 갔는데, 그냥 내가 이전에 짜둔 O(N^3) DP는 시간 안에 안 도나? 하는 생각을 했다. N=1000이고 /2가 되는 부분이 한 번 있어서 총 연산량이 N^3/2+O(N^2) = 5억 정도 되었다. 가벼운 5억이면 1초에 도는 게 정배 아닌가? 하는 생각을 했고, 캐시히트를 고려하기 위해 코드를 약간 수정한 뒤 제출했다. 그런데 480ms/1000ms로 매우 넉넉하게 돌았다. (4솔브, 2:35, 16등 → 14등)
그래서 O(N^3)이 정해인 줄 알고, 내가 문제 제한이 이상해서 2시간 가량을 1문제에 날린 줄 알고 머릿속으로 출제자 욕을 엄청 하며 화장실을 갔다 왔다. 알고보니 정해는 10*N^2의 간단한 풀이가 있다고 한다. 욕해서 죄송합니다ㅠㅠ
어쨌든 4솔단에 합류하였다. 내 위로도 매우 많은 사람들이 4솔브였고, 소수의 사람들만이 E와 G를 풀어놓은 상태였다. 남은 시간이 둘 중 하나는 풀 수도 있는 시간인 것 같아 5솔브로 4솔단들을 역전해 상위권을 노려볼만 하다고 생각했다.
E와 G를 둘 다 읽었는데 처음에는 둘 다 잘 모르겠었다. 그래도 E는 자료구조 문제로 구현에 매우 많은 시간이 걸릴 것 같은(스코어보드 상위권도 실제로 그러했다) 반면 G는 애드혹/해구성 문제라 풀이만 잘 내면 남은 시간 80분 안에 풀어볼 만한 것 같아 G를 보기로 하였다.
작은 케이스에 대해 손으로 열심히 적어봤는데 손으로 계산하기에는 무리가 있어서, 나이브 코드를 짜서 테스트해보기로 했다. 2^(r-l-1)*(r-l)^2번의 반복문으로 그런 l, r에 대해 유효한 defense가 존재하는지 판정하는 코드를 짰다. (원래 더 비효율적으로 짰으나, 큰 케이스에서 오래 걸리길래 최적화했다.)
테스트 결과, l=1일 때는 r=6까지, l=2,3일 때는 r=13까지, l=4,5,6,7일 때는 r=27까지만 유효한 defense가 존재한다는 것을 알 수 있었다.
이로부터, 각 l에 대해 l이하인 가장 큰 2의 거듭제곱수를 l0라 하면 r<=7*l0-1이어야 유효한 defense가 존재한다는 강한 추측을 할 수 있었다. (저 숫자를 보고 바로 7*l0-1을 바로 찾진 못했고, 숫자가 6->13->27로 *2+1씩 커지길래 이걸로 계차수열 점화식을 풀었다. 7*l0-1정도면 바로 찍을 수도 있었을 것 같은데 왠지 모르게 잘 안 됐다.)
이제 attack과 defense 전략을 생각해야 했다.
attack을 먼저 생각했는데, 각 2의 거듭제곱수 l0에 대해 [l0, 7*l0]는 항상 attack이 가능하고 [l0, 7*l0-1]은 아니라는 점으로부터, 7*l0은 무조건 attack에 들어가야 한다는 것을 알 수 있었고, 좀 더 생각해 보니 l0, 2*l0, ..., 7*l0가 들어가면 반드시 attack이 가능하다는 것을 발견했다. 이는 1, 2, 3, 4, 5, 6, 7이 들어가면 attack이 가능하다는 나이브 결과로부터 당연하다. 다만 l>l0일 경우 l0를 넣을 수 없는 문제가 생기는데, x=l-l0(아니면 x=l0-1로 고정해도 된다.)라 할 때 l0+x, 2*l0+x, 3*l0, 4*l0, 5*l0+x, 6*l0+x, 7*l0을 넣으면 깔끔하게 해결되었다.
다음으로 defense는 1, 2, 3, 4, 5, 6만 있으면 defense가 가능하다는 나이브 결과를 이용하였다. r<=7*l0-1이라면 l~r의 수는 모두l0로 나눈 몫이 1~6이고, 이에 따라 수를 분류하면 (몫이 a인 수)^(몫이 b인 수)=(몫이 a^b인 수)가 되므로 1, 2, 3, 4, 5, 6과 똑같은 defense를 적용하면 된다. 손으로 대충 써보니 RBBRBR이 1~6의 유효한 defense중 하나길래, 몫이 1인 수는 R, 몫이 2인 수는 B, ...으로 할당해주었다.
위 전략을 그대로 Python으로 구현하였다. 인터랙티브 세팅이기 때문에 테스트가 약간 귀찮았는데, 대회 종료 10분 전이어서 테스트하고 디버깅할 시간이 많이 없는 상황이었다. 그런데 생각해보니 패널티가 이미 망한 상태여서 일단 제출해봤는데, 한번에 맞아버렸다! 채점이 오래 돌다가 '맞았습니다!'가 나왔을 때 속으로 소리를 질렀고, 대회를 기분좋게 마무리할 수 있었다. (5솔브, 3:50, 16등 → 10등)
대회 종료 30분 전부터 스코어보드가 프리즈되어 내가 종료 10분 전에 G를 풀었다는 사실을 아무도 모를 것이었다. 남은 10분 동안 한 문제 더 푸는 건 불가능하기 때문에, 그동안 할 게 없어서 EFG에 한두개씩 제출하며 G를 맞은 사실을 숨기는 동시에 대회 출제진인 dadas08에게 편지를 썼다.
대회 후
대회가 끝나고는 그냥 조용히 있었다. 많이 피곤하기도 했고 주변 사람들 중 망한 사람들이 많은 것 같아서 그랬다.
대충 사람들이랑 수고했다고 인사하고 누가 문제 어케 풀었냐고 물어보길래 대충 얘기하다가, 자리에 앉으라고 하길래 앉았다. 심심해서 디스코드에서 7솔을 했다고 주장했으나 아무도 믿어주지 않았다.ㅠㅠ G를 푼 사실은 스코어보드를 깔 때 재미를 위해 얘기하지 않고 있었다. 대충 dadas08에게 편지 쓴 이야기와 B에서 2시간 말린 이야기 등등을 했다.
후원사 세션과 스코어보드오픈 및 시상식이 초고속으로 진행되었다. 1시간만에 다 끝난 것 같다. 빠르게 진행되어 마음에 들었다.
스코어보드를 깔 때는 각자 자리에 앉아 있었어서 디스코드에서 같이 중계를 하였다. 내가 제출한 G가 맞으며 스코어보드 위쪽으로 올라갈 때 사람들이 와~하는 소리가 들려서 기분이 좋았다. ㅎㅎ
최종 11등/24명 으로 마무리했다. 초반에 말려서 19등까지 떨어졌던 것 치곤 상당히 만족스러운 결과였다.
스코어보드는 여기에서 확인할 수 있다.
대회가 끝나고는 고깃집을 가서 공짜 고기를 먹고, 사람들과 대회 후일담을 이야기하였다. 같은 테이블에 잘하는 사람들이 많이 앉아서 재미있었다. 그리고 SCSC 사람들이랑 설빙을 가서 2차로 또 노가리를 깠고, 이후 피곤해서 집에 갔다.
3. 후기
B를 빠르게 푼 세계선에서는 몇 등이었을까 하는 생각은 조금 했지만, 일단 컨디션도 안 좋았고 크게 중요한 대회는 아니었기 때문에 결과에 대한 아쉬움은 없다. 기대했던 것보다 더 재미있게 즐기고 온 것 같다.
문제 퀄리티도 전체적으로 좋은 것 같아서 풀면서 재미있었다. 특히 G번 문제는 어떻게 이런 걸 냈지 싶을 정도로 잘 만들어진 문제라 생각한다. 역시 믿고보는 SNUPC다.
이번 대회를 앞으로 있을 큰 대회들의 연습으로 생각했던 만큼, 얻은 것이 꽤 있다.
- 문제를 뇌빼고 풀지 말자. 대회 초반에 풀이가 대충 나왔는데 머리가 안돌아가니 일단 구현하자 라는 전략을 계속 썼는데, 이거때문에 B에서도 망하고 C에서도 망할 뻔 했다. '구현하기 전에 모든 풀이를 구체화해놓고 애매한 부분이 없는 상태로 구현에 들어가야 한다'를 지켜야겠다고 생각했다. 사실 예전에는 일단 구현부터 하는 게 일상이었는데, 그렇게 하니까 ICPC에서 계속 망하기도 했고, 풀이를 다 정리한 뒤 구현하는 게 좋다는 말을 고수들에게서 많이 들어서 바꾸게 된 것이다. 다시 한번 왜 그것을 지켜야하는지 경각심을 가지게 되었다. 이를 많이 의식하며 문제를 풀어야겠다.
- 한 문제에서 1시간 이상 말리면 너무 오래 붙잡고 있지 말고 다음 문제로 넘어가는 습관을 들이자. 예전에 수능 공부할 때도 이게 꽤 중요했다. 한 문제만 계속 보면 같은 생각밖에 안 나지만, 다른 문제들을 풀고 오면 갑자기 생각이 잘 나는 경우가 많다. 또한 사람들이 생각하는 난이도순과 내가 느끼는 난이도순은 다르다. 너무 믿지 말자.
- 내가 참여한 모든 대회 경험 중, 대회에서 말렸을 때 후반에 복구한 가장 좋은 예시가 되었다. 오늘은 처음부터 별 기대가 없었어서 망했는데도 별 생각 없이 문제를 계속 풀었고 결과가 잘 나왔는데, 평소에 이렇게 망했을 때는 멘탈이 나가서 그대로 멸망하는 경우가 많았다. 이번 기회로 망해도 멘탈이 안 나가고 침착하게 풀어나간다면 꽤 좋은 결과를 낼 수 있다는 자신감을 얻었다. 앞으로도 망했을 때 이번 대회처럼 침착하게 행동해보려고 해야겠다.
- Python과 C++을 모두 써본 몇 안 되는 오프라인 대회이다. 두 언어 모두 쓸 수 있으면 한 언어만 쓰는 사람보다 좀 더 좋은 퍼포먼스를 낼 수 있다고 생각한다. 나는 원래 Python만 했었는데 최근에 C++을 잘 다룰 수 있게 되면서, 둘을 알맞게 섞어서 쓰는 것을 연습하고 있다. 이번에 이것을 잘 적용해볼 수 있었다. 나쁘지 않았다.
- 대회에서 처음으로 solved.ac 기준 다이아몬드 난이도의 문제를 풀었다! 연습에선 원래 많이 풀었지만 실전에서는 한 번도 풀지 못해서 연습과 실전 사이의 괴리를 계속 느껴왔다. 그것을 이번에 극복하여 자신감을 얻었다고 할 수 있겠다. 원래는 UCPC 2025의 34089번: Wildcard and Query 가 실전에서의 첫 다이아몬드가 될 뻔 했지만...(중략)
스코어보드 블러핑 방법에 대해 자세히 테스트할 수 있었다.
어쨌든 SNUPC가 끝났다. 이제 남은 대회는 KAIST ICPC Mock Competition과 ICPC 서울 예선과 ICPC 서울 본선(과 해외 리저널?). 사실상 ICPC 하나 뿐이다.
ICPC는 1년 동안 열리는 가장 큰 대회이고, 가장 잘 하기 어려운 대회이고, 내가 가장 잘 하고 싶은 대회이고, 가장 열심히 준비하고 있는 대회이다. 이번엔 진짜 잘 해서 좋은 결과를 냈으면 좋겠다. 아직 한 번도 팀 대회에서 잘 해본 적이 없는 만큼 이전의 어떤 대회보다도 더 열심히 준비해야 할 것이다. 지금부터 11월까지 꾸준히 열심히 해서 좋은 결과 가져오도록 하겠다.
긴 글 읽어주셔서 감사합니다 !