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

오늘은 국민대학교 알고리즘대회 예선을 봤다. 작년에도 봤었는데 여름학교 일정이랑 겹쳐서 예선만 봤었던 기억이 난다.

예선은 PS문제 2문제로 각각 100점씩 총 200점이고, 시간은 1시간을 준다. 하지만 온라인으로 진행되기 때문에 시험 시작 1시간 전부터 접속한 상태로 대기해야하며, 문제를 다 풀었어도 예정된 시각보다 먼저 종료할 수 없다. 프로그래머스에서 진행했다.

예선이다보니 문제 난이도는 쉬운 편이었고, 작년에도 쉬웠었지만 본선 진출 컷은 생각보다 낮았던걸 생각해보면 예선은 좀 가볍게 볼 수 있는것 같다.

 

대회가 14~15시에 진행되었으므로 시작 한시간 전인 13시까지는 프로그래머스에 접속해 있어야 했는데 내가 잘못 입력한 것인지 아니면 무슨 오류가 있었던 것인지 로그인이 계속 안돼서 하마터면 시험을 못보는줄 알았다. 다행히도 1시가 조금 넘었을 때 로그인에 성공했는데 응시할 수 있었다.

또, 시험 시작 약 5분쯤 전에 갑자기 연결이 끊겼다가 다시 연결된 것처럼 뜨면서 웹캠 연결과 화면 공유가 끊겼다고 떠서 다시 연결하고 돌아왔었다. 연결이 끊겼다는걸 빨리 발견해서 다행이라고 생각한다. 불안한 시작이었지만 대회 도중에는 이런 일이 없었어서 다행이다.

 

 

1, 2번 모두 문제에서 요구하는걸 그대로 구현해주면 되는 문제였다. 다만 2번은 시간의 효율성을 위해 priority_queue 정도의 자료구조를 사용해 log n만에 가장 작은 값을 찾을 수 있어야 했다.

 

1번은 2차원 배열에서의 구간합을 빠르게 구하는 프로그램을 짜라는 것이었는데(친절하게 누적합에 대한 설명도 적혀있었다.) 정확도 테스트가 50점, 효율성 테스트가 50점으로 구성되어있었다. 배열의 크기나 값들의 범위가 명시되어있지 않아서 좀 걱정이 많이 들기는 했지만 대충 눈치껏 짰더니 둘다 만점이 나왔다.

 

2번은 사탕을 가장 적게 가진 사람에게, 그러한 사람이 여러명이라면 그중에서 번호가 가장 작은 사람에게 사탕 1봉지(각 봉지마다 들어있는 사탕의 수는 다를 수 있다.)를 순서대로 주는 작업을 반복한 후, 모든 사탕 봉지를 다 줬을 때 각 사람이 가진 사탕의 수를 출력하라는 문제였다. 앞서 언급한 것처럼 '사탕을 받아야 할 사람'을 log n만에 찾아낼 수 있는 priority_queue를 이용해 풀었다. 1번과는 다르게 정확도/효율성 테스트가 따로 있진 않았다. 값의 범위가 전부 명시되어있었기 때문에 O((봉지 수)*(사람 수))의 시간복잡도로 풀면 시간초과가 난다는게 확실하기 때문인걸까?