2021 제6회 국민대학교 알고리즘 대회 본선 후기

문제 유출에 주의하라는 얘기는 못 들은것 같긴 한데 다른분들이 쓰신 작년 후기들을 봤더니 내가 그동안 너무 저작권을 안 신경썼나 싶어서 문제에 관련된 얘기는 최대한 조심스럽게 해야겠다고 생각하게 되었다.

 

예선을 통과해서 오늘 오후 2시부터 4시까지 국민대에서 열린 본선대회에 참가하게 됐다.

시국이 시국인지라 코로나 검사를 미리 받았어야 했으며 KF94 마스크를 써야됐다. (습관적으로 비말차단 쓰고 가서 한번 교체당했다ㅈㅅ)

신분증으로 학생증은 사용할 수 없다는 점을 주의해야 한다. 나는 이미 예선때 입구컷 당해서 민증을 만들러 갔었었다.

 

오랜만에 오프라인으로 대회를 봐서 대회장에서만 느낄 수 있는 기분이 느껴져서 좋았다. 온라인은....뭔가 너무 긴장감이 없다....

 

대회는 2시에 시작하지만 입실 시간은 1시 10분까지라 일찍 출발했다. 여유있게 도착해서 차 안에서 간식같은 점심을 먹고 들어갔다. 한 고사실에 8명씩 배정되어있었다. 응시자간의 간격이 넓어서 좋았다.

자리에는 노트북과 응시자 유의사항이 적힌 종이와 연습장(A4용지) 2장이 있었다. 키보드가 따로 없어서 노트북 키보드를 써야되는 것이 좀 불편했다. 나는 프로그램을 짤때 home키와 end키를 많이 사용하기 때문에 더 불편했을지도 모르겠다. (응시자 입장에선) 자신에게 최적화된 공간에서 시험을 볼 수 있다는 것은 온라인이 갖는 최고의 장점인 것 같다.

 

1시 10분부터 응시자 유의사항을 설명해 주셨다. 시험시작 한시간 동안은 화장실 이용과 중도퇴실이 불가능해서 좀 놀랐다. 작년에 한 30분만에 다풀고 나가버린 사람도 있어서 그런가..?

---

문제는 총 2문제, 각각 100점씩해서 총 200점이었다. 예선처럼 프로그래머스에서 문제를 풀면 됐고, 외부 IDE는 사용할 수 없어 디버거를 사용할 수 없었다.

 

1번은 그냥 구현하는 문제였다. x좌표가 1 차이나는 경우를 잘 생각해서 구현해줘야 했다. 뭐 다르게 풀면 안 그럴지도 모르겠다. 만점자가 여러명 나올 것이고 동점자 처리규정은 제출 시간순이기 때문에 빨리 풀어야 된다는 압박이 은근히 있어서 그냥 생각나는대로 막 구현했는데(같은 x좌표상에서는 y값의 최소 아니면 최대인 위치만 고려하면 된다는 점을 이용해 간단한 DP를 해주었다.) 제출했더니 틀렸었다. 이것저것 고치다가 결국 버그를 못잡고 63점인가 뜬 상태에서 2번을 먼저 풀어 좀 진정한 다음 1번으로 돌아와야겠다는 생각을 했다.

 

2번은 사실 알면 쉽고 모르면 좀 어려운 문제였다. 문제를 읽어보면 결국 그래프 위상정렬을 하라는 얘기인데, 노드가 번호가 아니라 문자열이고, 사전순으로 가장 빠른 위상정렬을 출력해야 한다는 점이 좀 까다롭다.

나는 문자열을 사전순으로 번호를 부여하여 편안한 그래프의 형태로 바꿔주고, priority_queue로 사전순으로 가장 빠른 위상정렬을 찾은 뒤에 그 번호들을 다시 문자열로 바꿔주는 방식으로 풀었다. 방법이야 많겠지만 난 이게 구현하기 가장 편할 것 같았다. 자신이 짜고 싶은대로 짜면 될 것 같다.

다행히 빠르게 구현했고, 한번에 맞아 다시 1번으로 돌아왔다.

 

여기저기 헤매다가 헷갈려서 변수를 바꿔 썼다는걸 깨닫고 고쳐서 맞은 것이 한 50분정도 지난 시점이었다. 목표하던 상을 받기에는 너무 늦어버린 것 같아서 아쉽다...

 

그런데 1번이 내 생각에는 답이 int 범위를 넘어갈 수 있을 것 같다. x, y값의 범위가 100,000이고 점(?)이 50,000개까지 주어지므로 위쪽 아래쪽 위쪽 아래쪽.....이렇게 왔다갔다하게 만들면 대략 100,000 * 50,000 + 100,000 정도가 될 수 있을 것이라고 생각한다. (제가 잘못 생각하는 거라면 댓글로 바로잡아주세요) 하지만 국민대 대회는 main부터 짜는게 아니라 solution 함수에 구현해야 하는데 이 solution 함수의 리턴 타입이 int다... 그치만 난 solution 함수를 믿기로 하고 3시가 되었을 때 조기퇴실했다.

---

퇴실할 때 에코백과 필기구들을 기념품으로 받았다. 필기구를 줄거면 왜 가져오라고 한걸까.. 개인 취향에 맞는 필기구를 쓸 수 있도록 하기 위한 배려인건가

내가 시험본 고사실에서 나 외에도 1명이 3시가 되었을 때 조기퇴실했고, 나오면서 대충 둘러보니 꽤 많이 나오는 것 같았다. 예상은 했지만 만점이 많은가보다. 이러다가 상 못받는건 아닐지 걱정되기도 한다.