2025 경인지역 대학 연합 프로그래밍 경시대회 shake! 후기

우승했습니다..!

1. 대회 전

어찌저찌 기말고사를 끝내고 종강을 하고 보니 shake! 본선을 준비할 수 있는 시간이 2~3주 정도 남았었다. 대회 자체는 2026년에 열리지만, 2025 타이틀을 달고 있는 2025년의 마지막 대회이니만큼 열심히 준비해서 좋은 성적을 내보고 싶었다. 그래서 시험 기간으로 인해 사라진 ps 감을 다시 찾고자 앳코더, 백준 대회 버추얼을 최대한 돌렸다.
 
(앳코더)  
251221 - ABC 386
251222 - ABC 389
251223 - ABC 390
251224 - ABC 394
251226 - ABC 398
251228 - ABC 405
260107 - ABC 411
 
(백준)
251222 - 2025 IamCoder Qualification Test
251224 - Hello, AlKon! 2025

251225 - 2025 아주대학교 프로그래밍 경시대회 APC
251226 - 제5회 숙명여자대학교 프로그래밍 경진대회(SMUPC)
251229 - 2025 서강대학교 K512컵
251231 - 2025 하반기 전남대학교 PIMM 알고리즘 파티
260103 - 2025 연세대학교 프로그래밍 경진대회
 
처음엔 업솔빙까지 열심히 돌렸는데, 26년도가 되고부터는 다시 해이해져서 ps 연습이 뜸해졌다.. ㅠ 나름 ps 감은 다시 찾았지만 연습 과정에서 크게 만족할만한 결과가 나오지 않아서 본대회에서 좋은 성적을 낼 수 있을까 걱정이 많이 되었었다.
 
 
교내에 아는 사람이 별로 없어서 대회장에 혼자 갈까 하다가 전에 연락을 몇 번 나눴었던 dodobow님이 생각이 났다. 같이 점심도 먹고 대회장도 같이 가자고 연락을 드렸는데 흔쾌히 받아주셔서, 대회날 대회 시작 전까지 이런저런 얘기들을 하면서 즐거운 시간을 보낼 수 있었다 ㅎㅎ 사실은 겸사겸사 26년도 팀을 함께하고 싶기도 해서 직접 만나뵙고 같이 할 의향이 있으신지 물어보고 싶었었는데, 이 부분도 얘기가 잘 이루어져서 정말정말 다행이었다. 언젠가 한 번쯤은 같이 팀을 해보고 싶었는데, 좋은 기회에 같이 팀을 하게 되었으니 올해 함께 재밌는 팀대회를 할 수 있었으면 좋겠다..!
 
다른 대회들이랑은 특이하게 기업 홍보 세션이 대회 전에 이루어졌는데, 대회 후에 힘이 다 빠진 채로 듣는 것보다는 집중해서 들을 수 있어서 개인적으로는 조금 더 좋았던 것 같다. 이번 shake!에서는 현대모비스, 넥슨 알고리즘 연구팀에서 좋은 말씀들을 해주셨다:)
 
 
 

2. 대회 시작

문제 세트
[00:02:05] A AC
공지된 난이도 분포 하한이 실버여서 A번 문제를 긴장된 상태로 열었다. 다행히 1, 2, 3이 나온 횟수를 카운트하기만 되는 간단한 문제여서 빠르게 짤 수 있었다. 제출 직전까지 스코어보드가 비어있는 상태여서 혹시 퍼솔을 딸 수 있지 않을까 했는데, 아쉽게도 퍼솔은 아니었다 ㅠㅠ
 
 
[00:06:47] B WA
[00:10:35] B AC
B번은 뜻하지 않게도 지금 하고 있는 수학학원 알바가 도움이 됐다. 직전 학기에 경우의 수, 확률 부분 진도를 나갔었는데 그 때 학생들에게 "확률 문제에서 '적어도'라는 말이 나오면 사건을 뒤집고 1에서 빼라"라는 말을 많이 했었던 게 떠올랐다. 그래서 풀이 자체는 빠르게 나왔지만 연산 과정에서 오버플로우가 나게 구현해버리는 바람에 1틀을 적립했다.. 초반부터 페널티가 쌓이면서 시작이 좋지 않다는 생각이 들었다.
 
A, B번을 제외한 나머지 문제의 배치는 랜덤이어서 C번부터 찬찬히 읽어보기로 했다. 풀 수 있을 것 같아 보여도 일단은 모든 문제를 숙지하자는 방향으로 갔다. 그런데 문제는 어느 것 하나도 감이 오지 않는다는 것이었다.. 그나마 C번에서 N^2M 값의 상한을 주어서 이 상한에 맞추어서 풀이를 구상해보기로 했다. 게자리 사각형의 대각선 위치에 있는 두 점을 N^2으로 순회하는 방법을 고민했는데, 생각해본 대로 코드를 짜보니 예제조차도 돌지를 않았다. 뭐가 문제일까 했는데 게자리 사각형에 있는 점들이 인접 정점을 공유할 때를 처리하지 않았다는 것이 보였다. 풀이의 틀린 점을 찾고 보니 이제 어떻게 짜야 될지가 보이질 않아서 접어두고 스코어보드를 체크했다.
 
시간을 많이 낭비한 게 아닌가 했지만 다른 참가자들도 비슷한 상황인 것 같아서 살짝 안심한 뒤에 어떤 문제들에 제출이 있었는지를 살펴봤다. D, E, G, J번에 시도들이 있어서 다시 한 번 문제를 훑어봤는데, 내가 자신 있는 유형도 아닌 것 같고 풀이가 빠르게 나오지도 않을 것 같아서 눈여겨둔 H번을 고민해보기로 했다. 


[00:46:51] H AC
처음에는 앞쪽 인덱스부터 순회하면서 dp 방식으로 구간을 쪼개는 방식을 구상했다. 이 문제는 그렇게 쪼개야 하는 구간이 4개인지라 그대로 짜기에는 쉽지 않았고, 그러다가 분할 정복하듯이 절반을 쪼갠 뒤 각각의 절반을 다시 반으로 쪼개는 방식을 떠올렸다. 이제 문제는 어떤 구간을 최적으로 자르는 지점이 어디인지를 어떻게 빠르게 찾을까 하는 것이었다. 예제 배열들을 몇 번 끄적여보니 어떤 구간의 최댓값은, 구간이 쪼개질 때 반드시 어느 한 쪽에 속해야 하므로 최댓값이 속한 구간은 항상 최대여야 함을 관찰했다. 최댓값은 누적합 방식을 이용하면 빠르게 구할 수 있지만, 대회여서 긴장이 되는 바람에 실수할 여지를 줄이고자 그냥 세그를 짰다. N이 커서 시간 제한에 걸릴까 살짝 걱정하긴 했는데 다행히 AC를 받았고 퍼솔을 먹었다. 


[01:01:00] J RTE
[01:01:25] J AC
J번이 많이 풀려있길래 J번을 다시 봤다. 어려운 문제라고 생각했는데 꽤 풀려 있길래 의아했다. 알고 보니 내가 문제를 잘못 읽고 더 어려운 버전으로 풀려 했다는 걸 깨달았다. 예제 2번의 경우 internationalization을 119로 줄일 수 있는데, 나는 119를 또다시 3으로 줄일 수도 있는 줄 알고, 만약 그런 입력이 들어오면 어떻게 해야 할지를 고민했었다. 문제를 다시 보니 "연산을 단 한 번만"과 "서로 겹치지 않는" 문구가 눈에 띄었고 그제야 dp 풀이가 떠올랐다. 재귀 dp를 짜다가 리턴 조건을 잘못 설정하는 바람에 RTE를 한 번 먹은 게 아쉬웠다 ㅠ


[01:21:06] E WA
[01:26:37] E AC
스코어보드 상 건드려볼 만한 문제는 E, G(D는 솔브 수가 상대적으로 더 낮았던 것으로 기억)였다. G는 단절점/단절선 문제(ㅋㅋ)이지 않을까 싶었고 내 하드카피에는 단절점/단절선이 없었기 때문에 어쩔 수 없이 E를 풀기로 했다. 처음에는 예제 1번의 답이 (1, 3)을 추가해서 이루어지는 줄 알았는데, (1, 2), (2, 3)과 같이 추가해도 비용이 동일하다는 걸 보고, 인접 수들끼리 정수 쌍을 추가하는 것이 더 이득임을 알게 되었다. 원래 배열과 정렬된 배열을 비교하면서 어떤 수들끼리 자리를 바꾸어야 하는지를(순열 사이클 분할하듯이) 체크하였고, 그 수들의 집합에서 최댓값과 최솟값의 차이의 합을 계산해나갔다.
 
그러다 보니 WA를 한 번 받았다. 반례를 고민해보니, 최댓값과 최솟값 구간을 좀 더 세밀하게 조정해야 했다. 예를 들어 만약 예제 2번의 입력 두 번째 줄이 10 7 3 1이었을 때, 내 코드는 1과 10 / 3과 7이 자리를 바꾸어야 하므로 (10-1)+(7-3)을 계산했고 이는 최적이 아니다. (10-1)에서 이미 (1, 3), (3, 7), (7, 10)이 추가된 것으로 간주해야 하기 때문에 (7-3) 계산은 제외되어야 한다. 이러한 부분들을 고쳐주니 맞을 수 있었다.

 
[01:35:29] G AC
단절점/단절선 템플릿이 없는 내가 뭘 할 수 있을까.. 했는데, 템플릿이 필요해 보이는 어려운 문제인 것 치고는 솔브수가 꽤 나왔다는 생각이 들었다. 그래서 그래프를 여러 개 그려보면서 다른 풀이를 구상해보기로 했다. 주어진 그래프가 항상 연결 그래프로 주어지므로 연결 그래프에서 트리 하나를 뽑아내면서(크루스칼-MST 뽑아내듯이), 남는 잉여 간선의 수에 따라 으악그래프인지 아닌지를 판별해주었다.
 
정해보다는 물론 어렵게 풀었지만 그래도 풀었으니.. ㅎㅎ. 사실 이 G번도 중간에 문제를 잘못 읽는 사고가 있었는데, "임의의 서로 다른 두 간선"을 "어떤 서로 다른 두 간선"으로 이해해버리는 바람에 문제를 또 잘못 풀 뻔했다.
 
 
[02:52:52] D WA 
[02:57:22] D AC
D번은 문제를 이해하는 데도 좀 걸렸다. 이해하고 나서도 머리엔 물음표가 가득했지만.. 최종 결과값을 가장 크게 만드는 것이 목표이므로 우선 최상위 비트를 살려보고, 그게 가능하면 다음 비트도, 또 그 다음 비트도, 하는 방식으로 계속 고민해보았다. 그런데도 답이 잘 보이지 않았고 계속 0과 1만 보다보니 나중에는 간단한 xor, and 계산도 잘 되지 않았다 ㅠㅠ G번까지 풀었을 때 6솔브로 굉장히 안정적인 상위권이었는데 여기까지 오다보니 우승에 욕심이 났고, 안심하기 위해서는 D번도 풀어내야 할 것 같았다. 그래서 한참 시간이 지난 뒤에는 간절한 마음으로 작은 N에 대해서 나이브를 돌려서 규칙을 찾아보기로 했다. N이 홀수일 때는 N 그대로, N이 짝수일 때는 2^k-2의 경우에만 조심하면 되는 간단한 규칙이 나왔다. 정말정말 다행히도 규칙이 쉬워서 프리즈 전에 7솔을 띄울 수 있었다.


[03:14:52] F WA
[03:59:31] C WA
[04:00:00] 대회 종료
기억 상으로는 뒤에 바로 6솔, 5솔 분들이 붙어서 따라오고 있었기 때문에 7솔을 띄웠음에도 많이 불안했다. 그래서 프리즈 후에 블러핑을 한 번 치기로 했다. 남은 문제가 C번, F번, I번이었는데 그 중 F번이 문제 숙지가 가장 덜 되어있었기도 하고, 내가 생각하기에는 가장 어려워 보여서 F번에 단순 return 0; 코드를 냈다. "아무나 걸려주세요 ㅠ" 하는 심정으로 내긴 했는데 영향이 있었는지는 잘 모르겠다..
 
I번은 다익 + 알파.. 같았는데 알파가 도저히 뭔지 모르겠어서 대회 초반부에 짰었던 C번을 고쳐보기로 했다. 겹치는 인접 정점을 어떻게 처리해야 할지가 도무지 떠오르지 않았고, 지금 내가 짜고 있는 코드가 정말 상한(N^2M)에 맞는지도 확신이 들지 않아서 고생을 좀 했다. 막바지에 "포함-배제를 써야 하는 건가?"까지는 갔는데, 식 정리도 제대로 안 됐고 포함-배제에 익숙하지도 않아서 결국 프리즈 동안엔 솔브를 하지 못하고 대회를 종료했다. 
 
 
 
 

3. 대회 종료 

최종 스코어보드

4시간을 내리 앉아서 문제를 푸니 많이 피곤했다. 그럼에도 뒤에 진행되는 세션들을 재밌게 진행해주셔서 즐겁게 마무리할 수 있었다. 4솔~프리즈 직전까지 계속 1위를 유지하고 있었지만 프리즈 시간 동안 솔브를 더 띄우지 못하기도 했고, 교내 선발전에서도 프리즈 동안에 역전을 당해서 1위를 하지 못했던 것이 떠올라 안심하기는 어려웠다. 스코어보드를 살펴보았을 때 5솔 중 프리즈 동안에 3문제 제출하신 한 분의 결과 때문에 우승을 확정짓기 어려웠다. 원래 한 번 틀리면 패닉 제출을 많이 해서 페널티를 한아름 쌓는 경향이 있는데, 이번 대회에서는 페널티 관리가 엄청 잘 되어서 솔브 수가 차이나는 것만 아니면 역전 당하는 경우의 수는 없어 보였다. 결과적으로 우승이라는 뜻깊은 성적을 받게 되었고, 함께했던 dodobow님도 우수상을 수상하셨다.(다시 한 번 축하드려요!!) 

ps에 대한 회의감이 많이 들던 때에 이런 큰 상을 받게 되어서 그 의미가 남달랐다. 어느 대회에서든지 1등은 커녕 수상권, 순위권에 들어보지도 못한 때가 많았고, 오프라인 대회의 경우에는 수상자 분들을 축하드리는 박수만 치고 오는 시간들이 많았다. 이렇다 할 특별한 성적 없이 시간만 흘러가는 것 같고, 또 학년이 높아질수록 취업을 걱정하게 되면서 언제까지 ps를 해야 할지, 할 수 있을지를 진지하게 고민해야 하지 않나 하는 생각들이 들었었다. 재미로 시작했던 ps에서 그 재미가 빠져나가는 듯한 기분이어서 이런저런 고민들이 많았는데, 그런 시점에서 정말로 예상하지 못했던 결과를 받게 되어서 사실 아직까지도 꿈인가 싶다.. ㅎㅎ 이때까지 했던 것들이 완전히 의미없는 것은 아니었구나 하는 생각이 들어서, 나름 위로받는 기분이기도 하다.
 
(shake!는 역대 대회 3위 이내 수상자들의 참가가 불가능해서 나는 더이상 참여할 수 없지만, 앞으로 있을 shake! 대회들에서도 경희대 분들이 좋은 성적을 낼 수 있으셨으면 좋겠다 ㅎㅎㅎ. ps를 하는 모든 분들도 화이팅입니다!)