2024 SCSC 서울대학교 프로그래밍 경시대회 (Onsite) 후기
(*Open Contest 종료 시각인 24.06.01 19:00 이후에 발행된 글입니다.)
(*본 대회는 24.05.25에 진행되었습니다.)
0. 프롤로그
세 번째 휴가가 생각보다 조금 늦어졌습니다. 5월 19일~5월 30일이 휴가 기간인데, 운이 좋게도 5월 25일에 열리는 경희대학교 교내 프로그래밍 경시대회와 겹쳤습니다. 처음 응시했던 22년도 경시대회 때는 ps를 시작한지 얼마 되지 않아서 거의 망치다시피 했기 때문에 아쉬운 마음이 많이 들었었습니다. 그래서 이번 24년도 경시대회 때 만회하고자 하는 생각이 있었는데, 제가 휴학생 신분인 게 마음에 걸려 확인해보기로 했습니다. 그런데..
어쩔 수 없이 교내대회 복귀전은 내년 25년도로 미루기로 했습니다. 그렇게 낙담해하고 있었는데, 어느 날 공지가 하나 올라온 걸 보게 되었습니다. 대학 대회인데 외부인 참가 가능에 온사이트? ps 하시는 분들은 다 아시겠지만.. 이런 건 정말정말 귀한 기회이고 경험이기 때문에, 공지를 보자마자 바로 신청했습니다.
Div. 1과 Div. 2를 선택해서 신청할 수 있었는데, "서울대학교"와 "Div. 1"을 서로 붙여놓으면 무시무시한 타이틀이 되기 때문에 얌전히 Div. 2를 신청하기로 했습니다. Div. 2의 상품 공지를 보니 25등 안에만 들면 상품을 탈 수 있었습니다. 지난 번 그랜드 아레나 파티 때와는 달리, 참가자 명단도 모르고 참가자 수도 모르고 있었기 때문에 상품을 타기는 저번보다 조금 힘들지 않을까 하는 생각이 들었습니다. 그래도 목표가 있으면 좋기 때문에 25등 안에 들어서 상품을 타는 것을 목표로 하기로 했습니다.
1. 대회장으로
서울대학교는 지금까지 총 2번 와봤습니다. 한 번은 대학 탐방 느낌으로 가족들과 함께 와봤고, 또 한 번은 고3 지균 면접 때문에 와봤습니다. '서울대학교' 하면은 아직도 면접 당일의 새벽공기, 어슴푸레한 분위기, 그때의 긴장감이 떠올라서 서울대학교 정문에 도착하니 뭔가 오묘한 느낌이 들었습니다. 그래서 원래는 5513번 버스를 타면 대회장 건물 바로 앞까지 갈 수 있지만, 다른 버스를 타고 서울대학교 정문에서 내려서 조금 걸어서 가기로 했습니다. (서울대학교 캠퍼스 라이프는 이런 것이구나..) 대회장 건물 근처까지는 생각보다 금방 도착했는데, 28동을 못 찾아서 조금 (많이) 헤맸습니다. 22동부터 27동 건물까지 한 번씩은 본 것 같은데 28동만 안 보여서 같은 자리를 몇 번 돌다가, 어찌저찌 28동을 찾아 대회장 안으로 시간 안에 도착할 수 있었습니다.
대회 시작 30분 전에 본인인증 시간 및 대회 계정 수령이 시작되었고, 동시에 참가 기념품들도 받았습니다.
여담으로, 예정대로라면 14시에 대회 시작이었지만, 워낙 많은 인원이 대회에 참가하였고 본인인증 시간이 조금 길어져서 대회가 15분 연기되었습니다.
2. 대회 타임라인
[00:05:02] A AC
보통 A번은 종이랑 펜을 안 쓰고 바로바로 코딩하는 편인데, 문제를 보니 도저히 그럴 수 없다는 판단이 들었습니다. 어차피 사각형이 이루어지는 경우의 수가 얼마 안 되기 때문에 하드코딩하는 쪽을 택했고, AC를 띄웠습니다.
[00:11:10] B RTE
[00:15:17] B AC
처음엔 너무 쉽게 생각해서 바이러스에 감염된 컴퓨터가 처음 나타난 시간대만 찾으면 되는 줄 알았는데 그게 아니었습니다.. N, M 제한이 다소 작았기 때문에 M개의 로그를 t에 대하여 오름차순 정렬한 다음, N개의 컴퓨터를 하나씩 처음 감염된 컴퓨터로 설정한 뒤 시뮬레이션을 돌렸습니다. (RTE 코드는 배열 크기도 잘못 잡았고 사풀이기도 해서 그렇게 크게 아쉽지는 않았습니다.)
[00:24:51] C AC
단순 BFS 풀이가 가장 먼저 떠올랐는데, 문제가 너무 쉬운 감이 있어서 구현할 때 조금 머뭇거려졌습니다. 개인적으로 아이디어를 떠올리는 난이도가 B번보다 훨씬 쉬웠기 때문에 무슨 함정이 있는 게 아닌가 싶었습니다. 다른 풀이를 찾아볼까 싶었는데 N, M, X의 제한이 모두 작아서 그냥 에라 모르겠다 하고 제출했고 AC를 띄울 수 있었습니다.
[00:53:07] E WA
[00:55:32] E WA
[00:59:07] E WA
[01:16:08] E AC
다음으로 D번을 봤는데, '확률'이라는 말에 겁부터 먹고 시작했습니다. 예제 입출력 3번이 이해가 안 가서 일단 GG를 친 다음, E번을 먼저 해결해보기로 했습니다. 처음에 "?는 최대 하나 존재한다."라는 문구를 보지 못해서 도대체 어떻게 풀지 하는 생각이 들었는데, 알아차리고 나니 풀이 가닥을 잡을 수 있었습니다. ""dp[l][r][change][turn] = 현재 문자열 s[l..r]만이 남았고, 누구의 차례인지 turn이 주어질 때, turn이 이길 수 있는가? (change는 ?를 0이나 1로 바꾸었는지 여부를 나타냄)"" 이라고 dp식을 잡았고, 지금껏 풀었던 게임 dp를 떠올리면서 구현을 했습니다.
그런데 turn에 따라서 리턴값을 어떻게 해야 하는지, dp 값을 어떻게 채워나가야 하는지가 헷갈려서, 구현에 시간이 많이 걸리기도 했고 WA를 누적시키기도 했습니다.(에디토리얼에도 나와있듯, turn 인자를 빼버리는 게 훨씬 깔끔한데 이때는 그걸 생각할 겨를이 없어서..) 세 번째 제출 때는 거의 확신을 하고 제출을 했는데도 틀려서 마음이 조급해졌습니다. 곰곰이 생각해보니 문자열에 ?가 없으면 change 인자를 계속 같은 값으로 고정시켜야 된다는 것을 빼먹고 있었습니다. 그 결과 거의 1시간 정도 걸려서 AC를 띄울 수 있었습니다.
[01:26:45] D WA
스코어보드를 보니 D번이 꽤 많이 풀려있었습니다. 그런 만큼 쉬운 풀이가 존재하지 않을까 하는 생각이 들어 다시 D번을 잡았고, 요상한 풀이를 내어 제출한 후 그대로 WA를 맞았습니다. E번을 풀어서 기분이 좋아졌었는데 다시 안 좋아졌습니다. (ㅠ)
[01:37:08] F WA
..그래서 우선 F번을 한 번 고민해보기로 했습니다. 결국 트럭들이 가는 경로들을 모두 모아보면 트리가 되고, 제한이 N <= 200 000으로 다소 컸기 때문에 풀이가 MST와 관련이 있지 않을까 하는(정말 뜬금없는) 생각이 들었습니다. 우선 MST를 찾고 트럭들을 각각 분배해주는 방식으로 코드를 짰는데, 내고 보니 완전히 잘못된 풀이라는 것을 깨달았습니다. 트리 결과가 꼭 MST여야 된다는 것도 증명하지 않았을 뿐더러, MST를 이루는 간선이 다르게 구성될 수도 있기 때문입니다.
[02:21:09] F TLE
D번과 F번을 왔다갔다 하면서 고민해 보았는데, D번은 아무리 생각해도 모르겠어서 그냥 F번을 쭉 잡기로 했습니다. 예제랑 그림을 계속 들여다보다가 문제 제한으로 시선을 돌렸습니다. 왜 하필 N <= 200 000일까? O(N) 아니면 O(NlgN) 풀이를 의도했다고 판단하고 그런 시간복잡도를 가지는 알고리즘들을 고민해 보았습니다. O(N)이면 DFS 한 번이거나 DP쪽으로 기울어지는데, DFS도 DP도 어느 것 하나 딱 감이 오는 게 없었습니다. 한편 O(NlgN)이라면, 문제가 그래프 문제이기 때문에 데이크스트라가 아닐까 하는 생각이 들었습니다. 그 순간에 문제에서 놓치고 있었던 부분, "각 트럭은 목적지까지 최단 거리로 이동한다"라는 문구를 다시 보고 데이크스트라 풀이를 설계해나가기로 했습니다.
[02:22:41] F TLE
[02:23:42] F TLE
[02:25:08] F AC
아무리 생각해도 TLE가 날 부분이 없었는데, 계속 TLE가 뜨자 마음이 조급해졌습니다. 아예 풀이를 잘못 잡은 건가 하는 생각이 들었는데, 풀이를 폐기하기 전에 다시 한 번 코드를 뜯어보기로 했습니다. 아.. 데이크스트라를 구현할 때 우선순위큐에서 뽑은 원소가 현재 최단거리가 맞는지를 확인하는 작업을 해주지 않았다는 게 보였습니다. 요즘은 잘 하지 않는 실수인데, 마음이 조급해지기도 했고 '이따가 구현해야지'하고 넘긴 다음 데이크스트라의 다른 부분 먼저 구현하느라 까먹어버린 게 패착으로 작용해버렸습니다. TLE 3틀이 너무 아쉽게 느껴졌습니다..
[02:49:51] D WA
E, F를 풀었는데 D번을 못 푼 사람은 제가 유일했습니다. 4솔 중에서도 ABCD 4솔이 가장 많았기 때문에 D번은 꼭 풀어야 된다는 생각이 들었습니다. 제한을 작게 해서 끄적거려보기도 하고, '사다리타기'를 키워드로 서칭도 해봤는데, 도저히 풀이가 떠오르지 않았습니다. 그러다가 문득(무슨 계기가 있었는데, 까먹었네요..) dp가 떠올라 dp쪽으로 방향을 잡아보기로 했습니다. ""dp[i][j] = 가로줄을 i개 그었을때, j번에 도달하게 되는 확률"" 로 설정하니, 식이 예쁘게 나오는 것을 확인할 수 있었습니다. 드디어 풀었구나 하고 생각했는데 WA가 나왔습니다.
[02:50:42] D WA
[02:54:49] D WA
[02:56:34] D WA
[02:59:42] D WA
dp 식 전개에서 실수가 여러 개 보여서 계속 고쳤습니다. 마지막 1~2분 정도 남았을 때, 양 끝 세로선에서는 dp식이 달라져야 한다는 걸 깨달았지만, 시간이 너무 없어서 뇌도 꼬이고 손도 꼬여 그대로 폭사하고 말았습니다.. 풀이를 너무 늦게 떠올린 게 아쉽게 느껴졌습니다.
[03:00:00] 대회 종료
3. 대회 마무리
프리즈 전 순위가 17위였고, 프리즈 동안 D를 풀어내지 못했기 때문에 25등 안에 들기가 간당간당해 보였습니다. D번을 못 푼 게 너무 아쉬워서 조금 울적해진 채로 쉬는 시간을 보냈습니다.
쉬는 시간이 끝나고 바로 현대 모비스 홍보 세션이 이어졌습니다. 주어진 시간이 짧아서 현대 모비스에서는 어떤어떤 일을 하는지를 자세하게 알기는 어려웠지만, 회사 복지가 좋다는 것만은 확실하게 알게 되었습니다. 또 하나 반가웠던 소식은 대회 개최 예정 소식이었습니다. 원래 작년 이맘때쯤에 현대 모비스 알고리즘 대회 공지가 올라왔었는데, 올해는 무소식이여서 이제 열리지 않는 건가 싶었습니다. 그런데 올해 6~7월 중 대회가 열린다고 하니 뭔가 다행(?)이라는 생각이 들었습니다. (! 현재 공지가 올라왔습니다! https://career.programmers.co.kr/competitions/3980)
다음 시간은 문제 해설 시간이었습니다. 예고되었던 대로 Div. 1 문제의 난이도 분포가 살벌했고, 풀이 슬라이드를 보기가 거북해질 정도였습니다.. (특히 Div. 1의 C번..) 전체적으로 문제와 해설의 퀄리티가 굉장히 높았습니다. 특히 정해 외에 별해도 여러 개 제공되었던 점이 인상적이었습니다. 한편, 제가 못 풀었던 D번의 해설이 나왔을 때는 또다시 울적해졌습니다. 진짜 거의 다 왔었는데.. ..
대망의 스코어보드 오픈 시간. 공지되었던 상품들 외에도 특별상들이 여러 개 준비되어 있어서 재밌게 지켜보았습니다. 아쉽게 특별상에는 당첨되지 못했지만, 18등을 차지하면서 상품을 탈 수 있게 되었습니다 !
그냥 집에 돌아가긴 아쉬워서 서울대학교 랜드마크도 한 컷 찍었습니다.
+) 그리고 아메리카노 참가상까지.. 감사합니다 !!
