2023 현대모비스 알고리즘 경진대회 예선 후기

올해 후기는 쓰지도 않았는데 갑자기 작년 후기의 조회수가 뛰었길래 이왕 쓰게 될 거 빨리 써 봅니다. 어디까지 써도 되는지 모르겠어서 설명에 조금 부족한 부분들이 있더라도 양해 부탁드립니다.

 

대회 전

 

예선이기도 하고, 작년에 상을 타서인지 뭔가 별로 간절한 마음이 들지 않았다. 그래서 예비소집 세션도 들어가지 않고 그냥 당일날 프로그래머스 들어가서 대회를 바로 쳤다. 프로그래머스는 21 모비스 대회 이후로 처음이었는데, 별로 달라진 것은 없어 보였다. 굳이 매년 플랫폼을 바꾼 이유는 잘 모르겠다. 여러 주의사항들이 적혀있었는데, 정작 캠도 화면녹화도 없었다. 이럴 거면 그냥 캠을 키던 규칙을 바꾸던 하면 좋겠다는 생각이 들었다. 작년과 재작년 모두 예선 난이도가 막 어렵지는 않아서 그냥 다 풀겠다는 마인드로 대회를 쳤다.

 

1번

뭔가 지문이 길었다. 다 읽고 나니 왠지 제한이 작을 것 같았고, 실제로 그러해서 백트래킹을 잘 짜줬다. 예제가 잘 나오지 않아 디버깅을 열심히 했다. IDE를 못 쓰는데다가 segfault가 나면 출력 결과도 보여주지 않는 부분이 상당히 짜증났다. 열심히 보며 고쳤더니 예제가 나와서 냈고, 맞았다. 20분 정도 걸렸고, solved.ac 기준 난이도는 실버 상위~골드 하위 정도로 예상된다.

 

2번

대충 DP 문제이다. 골드 중위에 이런 문제들이 정말 많다. 제한도 적당히 작고 역추적도 없어서 그냥 하고 싶은 대로 짜주면 된다. 15분~20분 정도 걸렸던 것 같다.

 

3번

문제를 잘 읽고 제한을 보면 결국 행렬 거듭제곱 DP를 돌리라는 소리인데, 할 게 조금 많고 이런 문제에 익숙하지 않으면 여기까지 도달하기도 쉽지 않다. 1차로 DP를 돌려서 각 정점에서 다른 정점으로 갈 수 있는 경우의 수를 모두 구하고, 이를 바탕으로 크기가 \(N^2M^2\)인 행렬을 만들어서 거듭제곱을 시키면 된다. 20분~25분정도 걸렸다. solved.ac 기준 난이도는 P4로 예상된다.

 

4번

모두가 플로우일 것이라 예상했지만 보기 좋게 자료구조 문제가 나왔다. 소위 갖다 쓰면 풀리는 쉬운 문제는 아니었고, 생각을 좀 해야 했다. 뭔가 small to large를 쓰고 싶게 생긴 세팅이지만, 2번 쿼리 때문에 이를 쓸 수 없다. 1번 쿼리에서의 합치는 연산은 사실 진짜 합치는 것이 아니라서 정말 합쳐지는 게 언제인지 잘 생각해보아야 한다. 2번 쿼리의 조건을 잘 생각해보면, 집합에 들어온 순서가 동일해진 두 원소는 이후 연산들에서 분리되지 않는다는 것을 알 수 있다. 이는 1번 쿼리의 y 집합, 2번 쿼리 조건에 해당하는 모든 원소들에 적용된다. 따라서 이 연산들을 적용할 때에는 실질적으로 관리되는 대표 원소 1개만 남기고 나머지를 없애줄 수 있다. 따라서 2번 쿼리에서는 해당하는 원소들을 선형으로 탐색해도 amortized하게 시간 복잡도가 보장된다. 1번 쿼리나 2번 쿼리를 위해 자료를 선형으로 관리하는 것은 적절한 자료구조를 사용하면 된다. 나는 연결 리스트를 이용하였다. 예제가 나옴에도 코드에 오류가 있어 제출을 꽤 많이 했다. 1시간 10분, 총 시간으로 2시간 10분 정도에 만점을 받을 수 있었다. 가늠이 힘들긴 한데, solved.ac 기준 난이도는 P1~3 정도인 것 같다.

 

 

후기

 

재작년에는 본선에 가지 못했고, 작년에는 턱걸이였는데 올해는 편하게 결과를 기다려도 되어 다행인 것 같다. 2시간 10분 100점이 예선 탈락이라면 PS를 은퇴하면 되기 때문에 걱정이 없다. 대회 운영도 지난 대회들보다는 괜찮아진 것 같다. 치팅 이슈 대비가 하나도 되어 있지 않아 걱정했는데 (4번을 BBST로 푸는 경우가 아닌 이상) 팀 노트가 절실한 문제는 나오지 않았다. 물론 완벽한 해결책은 아니니 내년에는 더 완벽한 대비가 되어 있길 바란다. 물론 나는 내년부터는 대회에 참가조차 할 수 없다. 본선에서 유종의 미를 잘 거두고 올 수 있으면 좋겠다.