오랜만에 블로그 글을 씁니다! 곧 24년 현대모비스 알고리즘 경진대회가 열린다는 소식을 듣고, 23년 대회 후기는 적어도 24년 대회가 시작하기 전에는 완성해야 하지 않나 싶어서 호다닥 글을 써 봅니다. 대회에 출제하거나 참가할 때마다 후기글을 쓰겠다고 다짐하지만 다른 일을 신경쓰느라 바빠서 못 쓴 글이 많습니다. 이 글을 시작으로 밀린 후기글을 조금씩 써 나가려고 합니다…
인생 처음으로 대회에서 1등을 했는데 그 기록을 남기고 싶기도 했고, 본선 대회 경험이 다이나믹하고 박진감 넘쳤기에(?) 여러분께 공유해 드리고 싶었습니다. 재밌게 읽어 주세요!
21, 22년 이후로 세 번째 열리는 23년 현대모비스 알고리즘 경진대회에 참가했다. 22년에는 학생부로 나갔는데 이번에는 졸업하고 회사에 다니게 되어서 일반부로 출전했다.
예선
- 예선은 6월 23일 14시부터 17시까지 진행되었다. 예선 문제 보러가기
22년 예선 때와 달라진 점은 플랫폼이 구름에서 프로그래머스로 바뀌었다는 점이다. 로컬 환경을 못 쓰고 웹에서 코딩을 해야 한다는 점은 같았지만, 웹 에디터가 구름보다는 사용하기 편했던 것 같다.
22년에는 예선날 컨디션이 안 좋기도 했고, 문제 하나를 복잡하게 생각해서 구현을 다 못하고 예선에서 떨어졌다. 이번에는 컨디션도 괜찮고 실력도 좀 늘어서 만점을 목표로 생각하고 대회에 임했다.
그런데 문제가 생각보다 어려웠다. 1번에 조금 까다로운 백트래킹 문제가 나와서 더 간단한 풀이가 있는지 의심했고, 구현에 시간이 좀 걸렸던 것 같다. 2번에 에어컨 온도 조절하는 문제가 있었는데 그리디하게 접근하다 케이스워크가 엄청 복잡하게 나와서 한참 시간을 썼다. 아무리 생각해도 2번 문제라기엔 너무 어려운 것 같아서 접근을 바꿨고 다행히도 DP로 접근하니 쉽게 풀렸다. 아마 그리디로 접근하면 DP 풀이보다 효율적인 시간복잡도로 해결이 가능할 것으로 보인다.
3번은 행렬 거듭제곱 DP, 4번은 적당한 자료구조 설계 문제였다.
1, 2번에서 시간을 많이 쓴 나머지 4번 문제의 풀이를 떠올렸지만 구현을 마무리하지 못하고 대회가 종료되었다. 다행히도 세 문제 만점을 받아서 본선 진출에는 성공했다. 본선에는 학생부와 일반부 각 50명씩 진출했다.
본선
- 본선은 7월 7일 13시부터 16시까지 코엑스에서 진행되었다. 본선 문제 보러가기
예선과 본선 모두 하필 금요일이라 휴가를 내고 대회에 참가했다.
서울 일러스트레이션 페어
대회 당일 마침 코엑스에서 서울 일러스트레이션 페어가 열리고 있어서 아침 일찍 출발했다. 서일페 참가는 두 번째인데, 매번 그 긴 줄이 빠르게 줄어드는 것을 보며 티켓 배부 방식이 매우 효율적이라는 생각이 들어 감탄이 나왔다.
서일페에 참가한 목적은 내가 카카오톡 놀자곰 이모티콘을 만든 메밀 작가님의 팬이어서 놀자곰 부스를 방문하기 위함이었다. (ㅋㅋ) 추가로 놀자곰 굿즈와 망붕이 굿즈를 요청한 친구들이 있어서 빠르게 부스를 돌고 왔다.
넙죽이 굿즈와 꿈돌이 굿즈를 파는 부스도 있어서 신기했다. 도구리가 주최자 사무실에 들어가려는데 머리가 커서 문에 끼는 재밌는 광경도 목격했다.
대회 시작 전
함께 본선에 진출한 친구(goodgood123)와 만나서 점심을 때우고 대회장에 들어갔다.
학생부와 일반부 각 1명씩, 2인 1책상을 사용했는데 앉고 보니 koosaga님 옆자리였다. 대회 출제하면서 몇 번 만난 적이 있어서 가벼운 잡담을 했다. “1등 하러 오셨군요~” 라고 하니까 그런 말 하지 말라고 하셨다. ㅋㅋㅋ
대회 시작
본선 대회가 시작됐다. (스포일러 주의, 타임라인은 부정확할 수 있음)
1번 문제부터 숨이 턱 막혔다. 배열의 순서를 잘 섞어서 이웃한 원소 차의 최솟값을 최대화하는 문제였다. 비슷하게 생긴 문제를 본 적 있어서 대충 그리디하게 배열하면 될 줄 알았는데, 배열 길이가 홀수일 때의 풀이가 생각나지 않았다. 정말 이것만 붙잡고 한참을 고민했는데, 어쩔 수 없이 길이가 짝수인 경우의 풀이를 변형해서 부분점수(10.2/15점)만 긁었다. 이때까지 한 40분 넘게 썼다. 1번 문제부터 만점을 못 받아서 좌절하며 다음 문제로 넘어가기로 했다…
이미 시간을 많이 허비해서 일단 풀 수 있는 것부터 푸는 것으로 전략을 바꿨다. 남은 2, 3, 4번 문제를 대강 읽어봤는데 2번이 제일 생각하기는 편해 보였다.
2번 문제는 일단 최단 경로 그래프를 만들어서 푸는 유형이라는 게 보였다. 풀이를 완성하지 않고 바로 구현에 들어갔는데, 구현하면서 보니 생각보다 케이스워크도 많이 필요하고 구현량도 많았다. 이 문제만 잡다가는 3번을 고민할 새도 없이 대회가 끝날 것 같다는 생각에 잠시 3번 문제를 고민하러 갔다.
3번 문제는 어디선가 본 듯한 문제였다. 우선 SCC를 압축하면 Path cover 문제가 되어 이분 매칭으로 풀면 될 것 같았다. 종이에 몇 가지 예제를 그려 봤다. SCC와 이분 매칭 코드가 잘 기억이 나지 않아서 헤맸지만 바로 구현을 시작했고 2번보다 먼저 코드를 완성했다.
그런데 예제에 대한 답조차 나오지 않았다. 자세히 보니 Path cover 문제와는 약간 다른 형태였다. Path cover에서는 경로끼리 겹치지 않아야 하는데, 이 문제에서는 경로가 겹쳐도 되기 때문이다. 예제를 단순화한 반례 데이터와 그 옆에 물음표 두 개를 그려 놓고 이걸 어떻게 해결해야 하나 고민하다가 포기하고 2번으로 돌아갔다.
스코어보드 프리즈
그렇게 2시간째, 스코어보드가 프리즈됐다. 나는 1번 부분점수만 긁은 채 50명 중 32등에 위치해 있었다… 목표인 아이패드를 받으려면 25등 안에 들어야 하는데, 이대로 문제를 더 풀지 못하면 40등 밖으로 밀려나 장려상인 갤럭시 버즈 프로조차 받지 못할 위험에 처했다.
선택과 집중을 해야 할 때가 왔다. 우선 아이디어가 떠오르지 않는 3번 대신 풀이가 대강 보이는 2번을 구체화했다. 예외 케이스들을 다 처리하고 나면 단절선을 구해서 간단하게 해결할 수 있을 텐데, 문제는 단절선 알고리즘을 실수 없이 빠르게 구현할 자신이 없었다. 그래프의 특성상 스위핑 한 번으로 단절선을 구할 방법이 있을 것이라고 생각해서 그 방향으로 접근을 바꿨다.
그렇게 열심히 구현을 완성했고 다행히도 한 방에 만점(20/20점)을 받았다! 이제 남은 시간은 40분.
다시 3번 문제를 보니, 경로들이 겹쳐 있다면 겹친 정점들을 건너 뛰어서 새롭게 경로를 구축할 수 있을 거란 생각이 들었다. 그러면 경로들이 겹치지 않게 되므로 Path cover 문제로 환원할 수 있다. 이렇게 하기 위해서는 각 정점에서 도달 가능한 정점들에 전부 간선을 이어 주면 되고, 이건 Floyd-Warshall 알고리즘으로 간단하게 해결할 수 있는 문제이다.
다행히도 코드의 나머지 부분은 완성되어 있었고, 다른 곳을 건드릴 필요도 없이 Floyd-Warshall 알고리즘만 추가하면 됐기 때문에 빠르게 만점(30/30점)을 받을 수 있었다! 이제 남은 시간은 30분.
남은 시간동안 4번 문제를 푸는 건 불가능했기 때문에 빠르게 부분점수만 긁기로 했다. 딱 보니까 세그트리를 쓰는 어려운 스위핑 문제로 보였는데, 2차원 누적합을 쓰면 작은 입력에 대해서는 해결이 가능하기 때문에 빠르게 짜고 부분점수(4.9/35점)을 받았다.
남은 15분 동안 안도의 한숨을 내쉬며 4번 문제의 부분점수를 더 긁을 방법을 고민하다 대회가 끝났다.
대회 종료
시상식 전까지 쉬는 시간을 가졌다.
일단 목표했던 아이패드는 받을 수 있겠다는 생각에 마음 놓고 돌아다녔다. 대회 출제나 기타 등등으로 알게 된 kdh9949님, leo020630님, man_of_learning님, serin님, sait2000님을 만났다. 푼 문제를 공유하다 보니 내가 생각보다 잘 푼 것 같아서, 높은 등수까지도 기대할 수 있겠다는 희망이 생겼다…!
koosaga님은 1번을 긁고 나머지를 다 풀었다고 하셨다. 역시 1번은 어려운 문제가 맞다…
현대모비스 홍보 세션 뒤에 시상식이 시작됐다. 학생부부터 발표를 했는데, 역시나 1번 빼고 올솔브를 하신 koosaga님이 1등을 차지하셨다.
그리고 대망의 일반부 발표가 있었다. 3등부터 발표를 했는데 3등, 2등에도 내 이름이 없었다. 기대 반, 설마 반이었다. 그리고… 1등으로 내 이름이 불렸다! 기대하지 않았던 결과라 믿기지 않으면서도 그동안의 꾸준함이 결실을 맺었다는 생각이 들었다.
koosaga님이 한 책상에서 1등 두 명이 나와서 치팅이라고 의심받을 거라는 농담을 했다. ㅋㅋㅋ
우수상과 장려상 수상자 발표까지 마치고, 우승자들은 다시 단상 위로 올라 트로피를 받고 사진을 찍었다.
진행자 분께서 1등 소감을 말해달라고 하셨다. 다들 알다시피 현대모비스 알고리즘 대회에서 1등을 하면 차를 주는데 (23년은 스포티지 하이브리드) 나는 면허가 없다. 짧고 굵게 “무면허 운전 잘 하겠습니다!” 라고 외쳤다.
시상식 이후
시상식이 끝나고 마무리로 단체 사진을 찍었다. 일반부와 학생부에서 각각 1등상을 차지한 나와 koosaga님은 따로 밖에 나와서 같이 트로피를 들고 사진을 찍었다.
알고 보니 koosaga님도 첫 대회 1등이라고 하셨다. 사진 찍는 게 어색하셨는지 사진사 분께서 좀 더 당당하게 포즈를 잡아보라고 하셨다. ㅋㅋㅋ 아쉽게도 트로피를 들고 찍은 사진은 기사에 안 쓰였지만 나중에 내 이름이 기사에 나왔다. 3등 이내 우승자들은 따로 모여서 상금 계약서 같은 걸 작성하고 대회 일정이 마무리되었다.
koosaga님을 따라 뒤풀이를 갔다. edenooo님, stonejjun03님, moraeduji님을 만났다. (몇 분 더 계셨는데 잘 기억이 안 난다…) edenooo님이 3번 문제 어디서 본 것 같지 않냐고 하셨는데, 알고 보니 예전에 참여했던 kyo20111님의 랜덤 플래티넘 디펜스 연습에서 비슷한 문제가 나왔고 풀이를 논의한 적이 있었다…! 3번을 푸는 데에 무의식 중에 도움이 되었을지도 모르겠다는 생각이 들었다.
대회 얘기, 출제 썰 등을 이야기하며 식사를 하고 나랑 koosaga님은 1등 기념으로 각자가 앉은 테이블을 쐈다. 그렇게 하루가 끝났다.
후기
현대모비스 알고리즘 대회가 처음 열릴 때만 해도 운영상의 문제로 욕을 좀 먹었는데, 이제는 대회 환경도 문제의 퀄리티도 많이 좋아진 것 같다. 그리고 무엇보다 이렇게 큰 규모의 상금을 주는 PS 대회도 드물고, 안 그래도 PS 대회나 기업 후원이 줄어가는 추세라 이런 대회가 꾸준히 열린다는 것만으로도 감사한 일이다. 그나마 학생이 아닌 일반인도 참가할 수 있었던 구글 코드잼마저 이제는 역사의 뒤안길로 사라져서 현대모비스 알고리즘 대회의 의미가 더욱 커진 것 같다.
개인적으로는 대회날의 경험도 아주 다이나믹했고 예상치 못하게 1등을 차지하게 되어서 기억에 남는 이벤트였다. 내가 이런 막대한 상금을 받는다는 건 상상도 못했던 일이었는데, 역대 대회 우승자 참가 금지와 일반부/학생부 구분 (매년 학생부가 더 치열하다), 평일 대회 진행 등의 요인이 겹쳐서 운 좋게 우승할 수 있었던 것이 아닐까 싶다. 물론 꾸준히 즐겁게 PS를 해왔던 경험도 큰 역할을 했을 것이다.
후기글을 끝내며, 24년 현대모비스 알고리즘 경진대회에 참가하는 모든 분들을 응원합니다!