[코테 후기] 2022 현대모비스 알고리즘 경진대회

 

날짜: 22.07.01 13:30 ~ 17:00

문제는 총 5문제에 3시간 30분이 주어졌다.

구름 IDE에서 진행되었으며, 처음 쓰는 IDE임에도 불구하고 적응에 어려움이 없었다.

경진 대회인 만큼 인터넷 사용이 불가하고, 채점 결과가 공개되지 않는 시스템이었다.

학생부 50명, 일반부 50명이 본선에 진출하는데 본인은 학생부로 지원했다.

 

 

---

 

문제 리뷰

 

메인 로고에 자율주행할 것 같이 생긴 자동차를 보고 그래프 탐색 문제 나오려나 했는데 5문제 중 3문제가 정말 그렇게 나왔다.

1번 문제

유형: 자료구조, 구현

차의 속도, 무게가 v, w로 N개 주어질 때, v가 서로 다른 차들의 인덱스들을 더해서 출력하되, v가 같다면 w가 가장 큰 차의 인덱스를 더해서 출력하는 간단한 문제다.

N은 최대 2,000,000이기 때문에 정렬보다는 v에 대한 Radix sort 느낌으로 우선순위 큐를 써서 구현했다.

약 20분 정도 걸렸던것 같다.

 

2번 문제

유형: 그래프 탐색, 우선 순위

P점, E점, 일반 점에 대해 우선순위가 존재하고, S에서 E점까지 가는 경로 중 얻어지는 위험 점수를 계산하여 출력하는 문제다.

지문이 약간 길었지만, 친절하게 그림으로 과정을 설명해주어 문제 이해에 어려움이 없었다.

베이스 알고리즘은 BFS로 두고, P점, E점, 일반 점, y좌표, x좌표에 대해 우선순위를 5개로 분류해서 방문해야 하기 때문에 우선순위 큐에 사용자 정렬을 더한 자료구조를 사용해 구현했다. 

실제 자율주행과 연관이 꽤 있어보이는 알고리즘 문제였고, 40분 정도 걸렸던 것 같다.


3번 문제

유형: 자료구조

대문자 문자열로 이루어진 N개의 생산 공정과 K개의 에러 공정이 주어질 때, 에러가 포함된 생산 공정 중 가장 길이가 긴 공정과 그 수를 출력하는 문제다.

다행히도 에러 공정은 생산 공정의 첫 글자부터 시작하기 때문에 (ABCD 중 BC를 찾는 것이 아닌 ABC를 찾는 식) 난도가 높지 않았다.

N이 최대 500,000, K가 최대 100,000이라 N*K 만 돌아도 시간 초과가 발생해서 map 자료구조로 한 쪽을 O(1)로 만들어 구현했다.

또한 가장 길이가 긴 공정과 길이가 같다면 사전순으로 출력해야 해서 또 우선순위 큐를 사용했다.

카카오 기출문제랑 비슷한 느낌이 들었고 40분 정도 걸렸다.

굳이 찾자면 아래 문제와 비슷하다고 볼 수 있다.

 

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42577


4번 문제

유형: 그래프 탐색

주차장이 주어질 때, 빈 공간의 점수를 매기는 쉬운 문제였다.

장애인 전용 주차 구역은 -2점, 일반 구역은 1점 이런 식으로 해서 가장 점수가 높은 구역을 출력하면 된다.

일반 BFS 쓰면 금방 푸는 문제라서 20분 정도 걸렸다.

아래 문제의 알고리즘과 매우 흡사하다.

 

문제 출처: https://www.acmicpc.net/problem/2667



5번 문제

유형: 그래프 탐색, Branch and Bound

주거 지구끼리 잇는 도로 비용과 주거 지구와 산업 지구를 잇는 비용, 산업 지구끼리 잇는 비용이 주어질 때, N개의 지구를 재개발할 때 총 도로 비용의 합의 최솟값을 구하는 문제다.

N이 최대 300이라 O(2^N)으로 구현할 순 없어서, DFS 완전 탐색 도중 현재 도로 비용이 지금까지 구했던 도로 비용 중 최솟값보다 커지면 Bound를 시키는 알고리즘으로 접근했다.

1~4번 다 풀고 남은 시간이 1시간 40분 정도였는데, 당시 도저히 알고리즘이 떠오르지 않아 1~4번 문제에 TC를 만들어 예외 케이스 처리를 더 꼼꼼하게 해 주거나, 최적화를 하러 갔었다.

부트 캠프 선발 코테도 아니고 그런 짓은 하지 말았어야 했다. (경험 부족이 원인)

다시 오니 40분 정도 남아있었고, 갑자기 예전에 알고리즘 수업의 과제와 유사하다는 것이 떠올라 앞서 말한 Branch and Bound 식으로 구현을 시작했다.

하지만 시간 부족으로 완성하지 못했고, 아쉬움이 좀 남았다.

 

 

---

후기

응시 인원 1233명 중 182등으로 본선 진출에 실패했다.

 

1, 2, 4번은 TC에서 거의 만점을 받았지만, 3번 생산 공정 문제에서 치명적인 오류가 있었는지 250점 중 25점이었다.

 

문제를 아예 잘못 읽은 경우 또는 로직에서 런타임 에러가 도는 경우일 것 같은데 2번이나 점검했음에도 불구하고 이런 결과가 나와서 유감이다.

 

곧 예선 문제가 올라온다고 하는데, 다시 풀어봐야겠다.

학교 게시판에서 5문제 다 푸는건 당연하고 얼마나 빨리 제출하느냐에 따라 본선에 진출하는 느낌으로 얘기하는 것을 보았다.

 

그래프 탐색 분야는 자신 있었지만, 5번같은 네트워킹 문제를 빠르게 구현하는 연습이 필요함을 느꼈다.

 

두 번째 코테의 좋은 경험으로 남았다.