서론

서울시립대학교의 정보기술관을 사용하는 학생으로서 UOSPC라는 시립대의 알고리즘 대회의 존재를 풍문으로 들었는데, 이번에 정보기술관에 해당 포스터가 붙어서 참가를 결정하게 됐다.

2022년 12월 3일에 정보기술관에서 진행하는 대회였는데, 하필 이때 쯤에 바쁜 행사 준비가 있었고, 최근에는 알고리즘 문제 풀이보다 개발 위주로 하고 있었다. 백엔드의 인프라 쪽을 공부하고 있었고, 인프라 내용으로 발표 준비나 글을 포스팅해야 했기 때문에 도저히 알고리즘을 공부할 시간은 없었다.

하지만 그동안 간단하게라도 파이썬으로 알고리즘 문제를 풀면서 감을 잊지 않게 해두었기 때문에 참여해서 어느 정도의 문제를 풀 수 있지 않을까? 싶었고, 무엇이든 도전해보는 것을 좋아하기 때문에 참가를 결정하게 됐다.

본론

UOSPC 2022 문제 링크

대회의 진행 시간은 무려 세 시간이었고, 8문제가 있었고, 대회를 진행할 때 쓰는 문제 풀이 사이트에 랭킹 기능도 있었다.

랭킹을 보니 대부분 사람이 1번과 2번 문제를 빠르게 풀고, 3번부터 시간이 꽤 걸렸던 것 같다. 내가 속해있는 파트는 Division 2였는데, 1번부터 4번까지 네 문제를 푼 사람이 랭킹의 1등이었다. ( 대회 종료 30분 전 기준 )

1번과 2번은 적당한 난이도의 구현 문제였고, 3번은 복잡한 구현 문제, 4번도 복잡한 구현 문제였던 걸로 기억한다. 5번은 4번을 변형한 이진탐색과 관련된 문제였던 것 같고 다른 문제들은 DFS, BFS 등등 있었던 것 같다. 나에겐 어려웠던 알고리즘 대회였기 때문에 5번 문제까지만 대략 살펴봤다.

#1 ALL SOLVE

간단한 구현 문제였다.

#2 C언어및컴퓨터및프로그래밍및개론및실습및입문 (15학점)

적당한 난이도의 구현 문제였다.

#3 정현이의 레이팅 변화

어려운 난이도의 구현 문제였는데, 맨 처음에 문제를 보고 어떤 느낌으로 해야 할 지 대충 감은 왔지만, 직접 구현하려고 했더니 굉장히 어려웠던 기억이 있다. 중간에 필기가 필요할 것 같아서 아이패드를 꺼내서 필기하였더니, 감독하시는 분이 종이와 펜을 가져다주었던 기억이 있다.

중간에 집중이 끊겨 문제 풀이 사이트의 랭킹을 눌러봤더니 다들 1번과 2번을 재빠르게 풀고 3번 문제에서 시간이 꽤 많이 걸렸던 것 같다.

구현 문제 같은 경우에는 시간을 투자하면 보통은 푸는 편이었는데, 이번 경우에는 문제 풀이 사이트의 오류 케이스가 똑바로 출력이 안 되는 점이 있었고, 런타임으로 pypy3과 python3을 선택할 수 있었는데, pypy3을 기본으로 설정했지만 pypy3은 안 되고 python3으로 하면 되는 등 다양한 케이스가 나왔다.

종이와 펜으로 필기를 열심히 해가면서 리스트를 사용해서 구현했다. 시간 복잡도를 고려하여 리스트를 사용하지 않고 구현하는 방법을 생각해봤지만, 딱히 떠오르는 방법이 없어서 시간 관계상 리스트를 사용해서 구현했는데, 약 60개의 테스트 케이스에서 21번째 테스트 케이스에서 딱 막혔다.

해당 케이스에서 Error가 나왔는데, 좀 더 구체적인 이유는 없어서 정확한 오류 확인이 불가능하여 진행하기 어려웠다. 평소에 알고리즘을 좀 더 열심히 공부했다면 오류에 부드럽게 대응했을 텐데, 적당한 난이도의 구현 문제만 풀었던 나는 이 문제에서 시간을 많이 소비했던 기억이 있다. 결국 테스트 케이스 1/3 정도만 통과했다.

#4 A+B 세일 EASY

조합을 이용하면 아주 간단히 풀 수 있는 문제였다. 그러므로 구글링을 통해서 파이썬 itertools에서 combinations를 import하여, 그대로 가져다 썼는데, 영문 모를 에러가 났다. 분명 개인적으로 IDE에서 테스트할 때는 정상 작동하는데, 이상하게 NameError가 나는 것이었다.

찾아보니 선언하지 않은 변수를 썼다고 하는데, IDE에서 정상 작동하는 것도 그렇고 뭔가 이상하다고 생각하고 삽질을 좀 오래 했는데, pypy3에서 python3으로 런타임을 바꾸니 정상 작동하는 것이다.

그렇게 많은 시간을 날려 먹고 조합을 통해서 구현했는데, 두 번째 테스트 케이스에서 TLE를 받았다. 모든 케이스를 조합으로 구현하였기 때문에 시간 초과가 나는구나 싶어, 정답이 되는 케이스가 나오는 순간 프로그램을 종료시키게 만들어 TLE를 피하려고 했으나, 4번 문제 또한 절반 정도의 테스트 케이스만 통과하고 결국 풀지 못했다.

#5 A+B 세일 HARD

4번 문제에서 조금 진화한 문제이다. 4번 문제에서 TLE를 받은 것을 생각하면 이진 탐색이나 DP를 통해서 공간 복잡도와 시간 복잡도를 줄여야만 통과할 수 있을 것 같은 문제였다.

결론

원래는 알고리즘 문제를 푸는 것을 좋아했지만, 최근에 개발의 세계에 푹 빠져서 개인 프로젝트로 제작하고 있는 것이 있어서 알고리즘 풀이를 게을리했던 것 같다.

사실 DFS나 BFS, DP, 이진탐색과 같은 코딩 테스트를 한다고 하면 알아야 하는 기본적인 테크닉 또한 공부를 안 한 지 오래되어 가물가물했는데, 인터넷 검색이 된다고 해서 각오하고 갔다. 하지만 막상 문제를 만나니 부족함이 크게 느껴졌다.

이번 학기는 남은 학생회의 행사 준비나 다양한 행사 준비와 개발 위주로 공부했기 때문에 상당히 바빠서 알고리즘 준비는 많이 못 했던 것 같다. 행사 시작 몇 시간 전 까지만 해도 1시간 정도 거리인 마포에서 행사 준비를 하고 있었다. 이러한 핑곗거리가 있지만 어쨌든 결과적으로 매우 아쉬웠던 것은 사실이기 때문에 다음에 이러한 대회가 있다면 더 열심히 준비해서 참여할 계획이다.

이번 학기까지 마치면 다음 학기부터는 학점을 좀 적당히 들을 수 있어서 다양한 대외활동 위주로 진행하려고 한다. 다음 해부터는 개발뿐만 아니라 알고리즘도 열심히 공부해서 다양한 분야를 정복해보려고 한다. 내년에는 상금 도전!!