2024 현대모비스 알고리즘 경진대회 후기

작년 여름에 SCPC, UCPC는 본선까지 갔으나 현대모비스만 예선에서 탈락했던 기억이 있다. 결론부터 말하자면 올해는 본선 진출에 성공했다! 오늘은 현대모비스 후기를 풀어보도록 하겠다.

---

[예선]

작년 예선 광탈의 경험으로 깨달은 점은 "여유를 부리면 안 된다"였다. 대충 이 정도면 이 문제 구현이 끝나고 다음 문제로 넘어가겠지 싶은 시점에 의문의 맞왜틀이 시작되면 멘탈이 흔들리면서 아예 망할 수 있기 때문이었다. 그래서 이번에는 풀이가 생각나면 이걸 짤 수 있을까 고민하기도 전에 구현에 들어갔다.

---

1번)

유향그래프가 주어질 때, 몇 개의 정점에 말을 놓는다. 말은 매시간 간선을 따라 최대 한 칸 움직인다. 단 첫 번째 시간에는 무조건 한 칸 움직인다. 이때 어떻게 해도 충분한 시간 후에 한 정점에 두 개 이상의 말이 놓이는 상황을 피할 수 없게 만들기 위해 처음에 놓아야 하는 말의 최소 개수를 묻는 문제였다.

 

문제를 읽고 처음에 들었던 생각은 SCC였다. 한 SCC 내에서는 말을 원하는 대로 굴릴 수가 있고 다른 SCC로의 간선이 존재하는 SCC의 경우에는 그쪽으로 말을 보내버리면 되므로 정점에 비해 말이 많아지게 만들기 힘들다. 따라서 주어진 그래프를 SCC들의 DAG로 나타냈을 때 리프에 해당하는 SCC들에 말을 꾸겨 넣어야 한다는 것을 알게 되었고, 그렇다면 가장 크기가 작은 리프 SCC에 말을 전부 놓고, 그 SCC로의 간선이 존재하는 외부 정점 하나에 말을 놓는 것이 내 처음 풀이였다.

 

하지만 이는 틀렸다. 리프 SCC로의 간선이 존재하는 정점이라 하더라도 그 정점에서 또 다른 정점으로의 간선이 존재한다면 처음에 말을 그쪽으로 보내버리면 되기 때문이다. 예제에 이런 케이스가 없었던 것이 문제였다. 그리고 생각해보니 만약에 모든 SCC의 크기가 2 이상이라면 애초에 각 SCC 내에서 말을 돌리면 되므로 생각보다 불가능한 케이스가 많았다. 그렇게 나온 풀이는, 크기가 1인 SCC들에 대해, DAG 상에서 해당 SCC보다 아래에 있는 모든 정점에 말을 놓고 해당 SCC에도 말을 놓는 것이었다. 최소 사이즈를 구하는 것은 대충 DP 비슷하게 처리했던 것 같다.

 

사실 정리해보면 애초에 SCC는 필요하지 않은 문제였다. DAG 상에서의 단절점을 찾는 문제와 유사하다고 볼 수 있는데, 이는 그냥 그래프 탐색으로 충분히 해결 가능했다. 하지만 올바른 풀이를 내기 전에 이미 SCC 코드를 짜놓은 상태였기에 그냥 SCC 베이스로 코드를 완성했다.

 

온라인 검색이 실질적으로 가능했던 대회였지만, RUN 중급반 스터디를 진행했던 경험 덕분에 어떤 자료도 참고하지 않고 SCC 구현을 한 번에 성공했다는 점이 뿌듯했던 문제였다.

 

2번)

큰 레고 판 위의 몇 가지 점에 1*1짜리 브릭이 끼워져 있다. 이때 1*k 형태의 길다란 브릭을 어떻게든 사용해서 3층까지 쌓을 수 있는지 판별하는 문제였다. 조금 더 자세하게는, 1*k 형태의 브릭을 끼우기 위해서는 축에 평행하게 배치해야 하고, 브릭의 양쪽 끝이 아래층의 서로 다른 브릭에 끼워져 있어야 했다. 처음에 주어진 브릭 외에는 1층에 브릭을 놓을 수는 없다.

 

3층을 만들기만 하면 되므로 3층에 브릭을 단 하나 꽂을 수 있는지만 판별하면 되는 상황이었고, 즉 2층에 브릭 두 개를 잘 놓아 3층에 브릭을 놓을 수 있는 상태인지 판별하기만 하면 되었다. 그리고 1층을 구성하는 브릭 개수가 10~20개 정도로 굉장히 작았던 것으로 기억한다. 따라서 1층의 브릭에서 4개를 순서까지 고려해 고른 다음 이를 a, b, c, d라 할 때 a와 b를 끝점으로 하는 브릭, c와 d를 끝점으로 하는 브릭을 2층에 놓을 수 있으며 해당 두 브릭이 교차하지 않고, 두 브릭이 같은 행 또는 열의 칸을 공유하는 케이스가 있는지 하드코딩과 브루트포스를 이용해 구해주면 되는 문제였다.

 

3번)

0, 1, 2가 채워진 보드와 1, 2로 이루어진 문자열이 주어진다. 이때 보드 위에서 한 손으로 1 또는 2가 위치한 칸을 짚고, 0 위에서 이동하며 짚고 있는 칸에 적힌 문자를 기록한다. 이렇게 만들어지는 문자열이 주어진 것과 같게 만들 수 있는 시작점을 모두 구하는 문제였다.

 

1 혹은 2로 이루어진 모든 덩이에 대해 테두리를 훑으면서 읽히는 문자열을 미리 기록해 두고 주어진 문자열과 KMP를 통해 비교하면 되는 문제였다. 이때 방향 혹은 순환 때문에 살짝 구현이 더러운 처리 과정을 거쳐야 한다는 점만 빼면 크게 어려운 점은 없었다. 한 덩어리 주변을 계속 빙글빙글 돌 수 없다는 조건 때문에 난이도가 훨씬 낮아진 기분이었다. 만약 그 조건이 없었다면 SA-LCP까지 구현해야 했다.

 

문제를 보고 굉장히 놀랐던 점이 있다. 얼마 전 카이스트 에타에 올라온 글 중 하나가 알고리즘 문제를 대신 풀어달라는 것이었는데, 그 문제가 아마 프로그래머스에 올라왔었으며 이 문제의 정확히 제한만 작은 버전이었기 때문이다. 방에서 롤 하고 있는 동안 다른 사람이 먼저 풀어주었긴 하지만, 어떻게 구현하면 될지 이미 생각해 둔 상태였기에 조금 수월한 구현이 가능했던 것 같다. 제한 때문에 KMP를 써야 한다는 점만 빼면 아예 동일한 문제가 나왔다는 점에서, 예전이 이 문제를 본 사람이 제한을 늘릴 수 있을 것 같아 이번 대회에 냈을 것 같다고 예상한다.

 

이 문제도 1번의 SCC와 마찬가지로 KMP라는 다소 구현이 헷갈리는 알고리즘을 필요로 했다. 그러나 이번에도 RUN 중급반 스터디에서 가르치느라 공부한 기억을 토대로 KMP를 구현해 냈고, 개인적으로 SCC보다도 뿌듯했다.

 

4번)

3번까지 풀고 나니 시간이 그렇게 많지 않았다. 대충 40분쯤 남았던 것으로 기억한다. 그래서 풀이를 떠올리고도 구현이 시간 내에 힘들 것 같아 서브태스크만 긁기로 결정했다. 그래서인지 문제가 잘 기억이 나지 않는다. 대충 쿼리당 뭔가 처리해야 하는 것이 있는데 그걸 슬로프 트릭 비슷하게 그래프 모양을 관리하면서 오프라인으로 처리해 주면 되는 문제였다. 끝나고 solved.ac 디스코드에서 사람들과 대화해보니 풀이는 대충 맞는 것 같았다.

---

솔직히 끝내고 나오면서 400점이 굉장히 많을 줄 알았었다. 본선권 실력을 가진 분들이라면 1번은 20분 내에 풀었을 것이고, 풀이를 떠올리는 것보다 구현이 발목을 잡는 문제인 2번과 3번은 나보다는 일찍 풀었을 것 같았기 때문이다. 그렇게 되면 남는 4번은 나도 시간이 한 20분만 더 있었으면 100점이 나왔을 것 같으니 다른 분들은 무리 없이 해결했을 것 같았기 때문이다. 그러나 끝나고 다른 사람들과 점수 공유를 해보니 생각보다 300점이 많았다. 왜인지 살펴보니 3번 구현이 꽤나 오래 걸리기 때문에, 일단 4번으로 넘어가서 풀고 온 사람이 많았고 3번은 최소한의 긁기를 위해 짜야 하는 코드의 양이 다소 많아서 부분점수를 못 받은 사람이 많았던 것이다. 고수들 중에서도 그런 식으로인지 나보다 점수가 낮은 분들이 좀 보였고, 이번에는 본선 진출을 할 수 있겠구나 싶었다. 컷이 빠른 300이었던 것으로 기억하는데, 3번을 4번보다 먼저 풀면 4번은 아주 낮은 점수라도 긁을 수 있기 때문에 300을 넘게 된다. 내가 딱 그 케이스이고, 아무래도 전략 이슈가 컸던 라운드인 것 같다.

---

[본선]

첫 개인 오프라인 대회였던 작년 헬로BOJ 이후로 두 번째 오프라인 개인 대회였고, 본선 진출자 50명 중에 20명이나 최소 아이패드를 받아 가는 대회였던 만큼 꽤 신나서 대회를 치러 갔다. 예선 등수가 꽤 높은 편이었기에 주사위가 5~6이 떠준다면 아이패드를 받을 수도 있을 것 같아서 사실 좀 기대도 하고 있었다.

 

대회장에 가는 도중, 갑자기 재학증명서가 필요하다는 사실이 기억났다. 이미 온라인으로 재학증명서를 발급받은 적이 많기 때문에 아주 당황하지는 않았고, 핸드폰을 보여줬을 때 1층에서 지류로 출력해 오라는 얘기를 들었을 때나 조금 당황했다. 재미있는 점은 현재 이수 학점이 69학점이라 이제 재학증명서를 뽑으면 3학년으로 뜬다는 점이었다. 만 18세 3학년은 그렇게 이상한 일이 아니긴 한데... 왜 대학교지

 

아무튼 대회장에 들어가서 이것저것 둘러보는데, 다과가 마치 뷔페처럼 쌓여 있고 접시에 덜어가는 형식이었다. 몇 번이나 덜어가서 먹었다. 개인적으로 녹차맛 쿠키가 굉장히 맛있어서 내가 1/10은 먹은 것 같다. 또 참가자들 자리 배치도를 보면서 누가 왔나 구경하는데, 아는 이름이 많아서 신기했다. numbering이나 benedict0724처럼 고등학교 때부터 알던 친구들부터 junie님이나 ainta님처럼 얼마 전 RUN-SNUPS MT에서 알게 된 분들, 이외에도 yclock님이나 blackking26 형처럼 이런저런 경로로 알게 된 PS러들의 이름을 보며 꽤 반가웠었다. 그중에서 가장 반가웠던 건 imeimi2000 형과 79brue였다. 특히 79brue는 고등학교는 졸업했고 카이스트는 자퇴, MIT는 입학 전인 상태라 일반부 응시자였다. 그래서 우연히도 내 바로 옆자리에 앉게 되었다.

 

반가운 건 반가운 거지만, 본선 진출자들 명단을 보다 보니 생각보다 20등이 빡세다는 것을 느꼈다. 주사위 5~6이 아니라 확실한 6이 떠야 수상이 가능하겠다고 생각하며, 본선이 시작되었다.

---

1번)

문제도 기억이 나지 않는, 그냥 나이브 돌리면 되는 문제였다. 제한이 살짝 빡세 보여서 스코어보드가 없었다면 더 오래 걸렸을 것 같기는 하다. 실제로 한 5분 동안 최적화 고민하다가 다른 사람들이 너무 빨리 AC를 받길래 믿음의 제출을 했더니 나도 AC를 받았다.

 

2번)

초기 신선도가 제각각인 음식 여러 개를 하루에 하나씩 먹는데, 몇 개는 냉장고에 넣어서 하루에 신선도가 K 감소하고 나머지는 그냥 보관해서 신선도가 K+1 감소하는 상황에서 최대한 많은 음식을 신선도가 0 이상일 때 먹는 문제였다. 이런저런 관찰을 한 결과 그리디한 접근이 가능했고, 결국 배열의 정렬성을 유지하면서 임의 원소 추가와 구간 1 감소가 가능한 자료구조를 설계하는 문제로 환원되었다. 구간 1 감소는 레이지 세그에 이분탐색을 섞으면 가능했지만, 임의 원소 추가까지 하려니 스플레이를 짜야 할 것 같았다. 그렇다기엔 너무 많이 풀린 문제인 데다 스플레이 구현을 까먹었기에 다른 풀이를 생각해 보려 했다. 하지만 결국 풀이를 내지는 못했다.

 

수상권을 가르는 문제였기에 대부분의 시간을 이 문제에만 박았다. 지금까지는 대회에서 이상한 맞왜틀에 시간을 박거나 아무런 진전도 없이 벽에 막힌 듯한 느낌으로 시간을 흘려보낸 경험이 많았는데, 이번에는 결국 풀지 못했어도 의미 있는 문제에 시간을 박을 수 있었어서 왠지 기분은 좋았다.

 

끝나고 바로 79brue에게 풀이를 물어봤는데, 그리디의 축을 다르게 잡으면 임의 원소 추가가 필요해지지 않는다는 것을 깨달았다. 따라서 레이지 세그와 이분탐색으로 풀 수 있는 문제였고, 관찰을 조금만 더 잘했더라면 풀 수 있었을 것 같아 아쉬웠다.

 

3, 4번)

2번을 풀지 못한 상태로 일단 섭테를 긁긴 했는데, 꽤 오랜 시간이 지났음에도 아무도 섭테를 많이 긁지 못하는 모습을 보고 2번을 AC받지 못한다면 어차피 수상권에 들 수 없다고 판단했다(실제로 그 예측은 맞았다). 그래서 거의 고민할 시간이 없었고, 문제가 기억이 나지 않는다.

---

최종 등수가 나오지는 않았지만 프리즈 시점 이후로 2번 풀태스크만 노리느라 점수에 상승이 없었고, 아마 40등 근방으로 마무리하지 않았을까 싶다. 아이패드를 놓친 것이 아쉽지만 무상들을 위한 참가상이 존재했고, 대충 30만원 근방의 스피커였다. 아마도 작년에 35등이었나 40등까지 줬다는 버즈가 사라지고 생긴 것 같았다. 나에게는 태블릿보다 필요한 제품이었기에 왠지 럭키비키 엔딩이 되었다. 죽어도 필기를 안 하는 사람이라 내가 아이패드를 받았다면 집 밖이라서 TV로 유튜브를 볼 상황이 아닐 때 사용하는 큰 화면 유튜브 재생기기 정도로만 쓰였을 반면, 스피커는 요즘 매일 방에서 상시 음악 재생용으로도 쓰고, 연습실 잡고 댄스 연습할 때도 쓰고 있다.

 

아무튼 수상 빼고 모든 점이 성공적이었던 대회였다. 본선 진출자 선물이었던 과일바구니는 아직도 하나씩 꺼내먹고 있고, 전국 50등 내에 들었다는 점도 만족스럽다. 그렇지만 수상에 실패했다는 점이 계속 아쉽기에, SCPC에서 좋은 결과를 위해 노력해야겠다.