Search
💮

2021 대경권 대학생 프로그래밍 경진대회 후기

Date
2021/06/10
Tags
PS
Contest
Created by
"나는 내 실수를 찾으려 할 때를 제외하고는 절대로 뒤돌아보지 않는다. 당신이 자랑스럽게 여기는 것들을 되돌아볼 때, 나는 그 행위에서 오로지 위험만을 볼 뿐이다." - 엘리자베스 노엘레 노이만
Table of Contents

"대경권"

내가 대학교에 입학한 이후 "대경권 대학생 프로그래밍 경진대회"라는 것이 매년 최소 한 번씩은 개최되고 있다. 말 그대로 대경권 소재 대학교의 학생들만 참가할 수 있는 프로그래밍 경진대회로, 주 종목은 Problem Solving이나 2020년에는 "대경권 대학생 AI 프로그래밍 경진대회"라는 이름으로 Data Science Competition 형식의 대회가 딱 한 번 열린 적이 있다.
2018년에 첫 대회가 열렸고 (나는 당시 실력이 안 된다고 판단하여 참가하지 못했다), 2019년에는 동일한 이름으로 여름, 겨울에 각각 한 번씩 개최되었으며, 2020년에는 PS 대회 하나와 상기했듯이 Data Science Competition 형식의 대회가 하나씩 열렸다.
지금까지의 대회와 내 성적은 다음과 같다.
2019.05 2019 대경권 대학생 프로그래밍 경진대회
최우수상(2등상)
2019.11 2019 대경권 대학생 프로그래밍 경진대회
최우수상(2등상)
2020.06 2020 대경권 대학생 프로그래밍 경진대회
우수상(3등상)
2020.11 2020 대경권 대학생 AI 프로그래밍 경진대회
최우수상(2등상)

2021 대경권 대학생 프로그래밍 경진대회

2021년 여름에도 예상대로 "대경권"이 개최되었다. 결과만 먼저 말하자면, 대상(1등상)을 수상했다.
2021.05 2021 대경권 대학생 프로그래밍 경진대회
대상(1등상)

대회 준비 과정과 내가 유념했던 것

올해도 대회가 개최될 것을 어느 정도 알고 있었으면서도, PS에서는 이미 몇 개월동안 손을 놓은 상태였다. 대회 공고가 뜨기 전까지는 solved.ac 기준 실버 문제도 간신히 푸는 수준으로 PS 실력이 내려앉아있었던 것 같다.
이대로는 시상 중 제일 하위격인 우수상(3등상)은 고사하고 수상권에 들지 못할지도 모른다고 생각했다. 그래도 다행인 것은, 이 때의 나는 열정만으로는 아무것도 이루어지지 않는다는 것을 잘 알고 있었다.
열정이 우리를 들뜨게 하거나 가라앉게 하는 반면 목적은 우리의 감정을 휘두르지 않고 그 자체로 존재한다. 성공을 원한다면 목적을 가져야 한다.
그래서 "실질적인" 대회 준비 플랜을 세웠고, 대회 준비를 도와줄 멘토를 구했다. 대회 2주일 전부터 매일매일, 단 하루만 빼고 빠짐없이 난이도별 문제 4~5개를 풀어치웠고, 푼 문제들과 풀지 못한 문제들을 멘토와 같이 리뷰했다.
이 때의 내가 또 하나 유념하고 있던 것은 "성공에서 배울 것은 많이 없다. 실패에서 배워야 한다"이다. 푼 문제보다 풀지 못한 문제를 더 집중해서 보았다. 풀지 못한 문제는 왜 풀지 못했는지, 내가 더 겸손했다면 볼 수 있었던 것은 무엇이었는지, 실패 원인을 확실하게 분석하고, 힘들더라도 마저 풀어냈다.
사람은 누구나 자기보다 잘난 사람이 있다는 사실을 달가워하지 않는다. 같은 맥락에서 배워야 할 것들이 아직 많이 남아있다는 사실 또한 쉽게 인정하지 않는다. 자기는 이미 모든 학습과정이 끝났고, 무엇이든 할 수 있도록 준비된 사람이기를 바란다.
나는 '나는 아직 배울 것들이 많이 남아있는 사람임을 스스로 인정하는 것'으로부터 시작했다. 아는 유형의 문제였다면 내가 놓친 생각의 연결다리는 무엇이었는지, 무엇이 이 아이디어를 떠오르지 못하게 했는지를 생각했고, 모르는 유형의 문제였다면 이와 비슷한 문제들을 살펴보았고, 최대한 빠른 시간 내에 생각해내는 방법을 익히려 문제 유형을 외웠다.
내 티어가 얼마고 내가 지금까지 얼마나 PS를 했고, 내가 지금까지 얼마만큼의 대회 수상을 이루었는가와 상관없이, 꾸준히 배우겠다는 자세를 유지했다. 겸손을 유지했다.
또한, 말은 사람을 고갈시킨다는 것도 잘 알고 있었다.
그 일에 대해서 생각하고 설명하는 데에 많은 시간을 보내고 나면 마치 그 일을 거의 다 이룬 것처럼 느끼기 시작한다. 게다가 주어진 일이 어려우면 어려울수록 결과는 그만큼 더 불확실해서 자꾸 얘기를 하게 되고, 또 그만큼 실제 행동에서는 점점 더 멀어진다.
나는 멘토와 동기 1명 정도를 제외하고 내가 대회를 준비한다는 사실을 그 누구에게도 알리지 않았다. 기존 계정을 놔두고 새로운 BOJ 계정을 만들어 매일매일 셋을 돌았다. 내가 대회를 준비한다고 떠벌리고 다니면 마치 내가 모든 것을 이룬 것처럼 느끼게 될까봐 일부러 떠벌리고 다니지 않았다.

문제들과 내 실수

대회들이 다 그렇듯이, 문제에도 저작권이 있기 때문에 문제의 자세한 디스크립션까지는 적지 않는다. 최대한 기억나는 대로 문제의 개요와 내 접근법과 내가 범했던 실수들, 대회 당시에 느꼈던 심리적 상황들을 남겨보려 한다.
문제는 총 5개, 시간은 3시간이었다.

1번 (100/100)

기억이 나지 않는다. 쉬운 문제였던 걸로 기억한다. 순탄하게 풀고 2번으로 넘어갔다.

2번 (100/100)

문제 디스크립션이 장황했고, 문제도 별다른 생각을 요구하지는 않지만 장황했다. 덕분에 3번을 먼저 풀었다. 기업 코딩 테스트 스타일이라고 보면 될 것 같은데, 그렇다고 쌩 구현 문제는 또 아니다.
std::map을 써서 풀었고, 별다른 아이디어는 떠오르지 않았다. 얼핏 보면 O(N2)O(N^2) 같은 코드지만 문자열에서 읽어들인 글자 수만큼 건너뛰기 때문에 거의 선형에 가까운 시간 복잡도가 된다. 이런 시간 복잡도 계산이 조금 어려워서 내 코드가 AC가 나올지 판단하기 조금 어려웠다.
나중에 알게 되었는데 https://programmers.co.kr/learn/courses/30/lessons/17684와 문제가 비슷하다고 한다. 지금 보니 완전히 동일한 문제 같다.

3번 (100/100)

보자마자 풀 수 있는 쉬운 그래프 문제였다. 그래프와 priority queue가 쓰였다.
나중에 후배에게 듣고 보니 위상 정렬이라고 했고, 듣고 보니 맞는 말 같았다. 풀 당시에는 이게 위상 정렬이라고 생각하지 못했다.

4번 (6.8/100)

문제를 환원하면, "단 한 문자만 빠진 올바른 괄호 문자열이 주어졌을 때, 빠진 문자를 끼워넣어 올바른 괄호 문자열을 만들 수 있는 경우의 수 (빠진 문자를 끼워넣을 수 있는 위치의 개수)를 구하라"이다.
결과적으로는 풀지 못한 문제이다. 억지 솔루션으로 그나마 점수를 아주 조금 건졌다. 다른 사람의 말로는 스택 시뮬레이션으로 AC를 받을 수 있다고 한다.

5번 (50/100)

문제를 환원하면, "f(n)f(n)nn을 이진수로 나타냈을 때 1 오른쪽에 위치하는 0의 개수라 하자. ll, rr이 주어졌을 때, f(l)+f(l+1)++f(r)f(l)+f(l+1)+\dots+f(r)의 값을 구하라"이다.
앳코더에서 볼 법한 문제였다. 우선 값은 의외로 쉽게 구할 수 있었다. 정해는 잘 모르겠지만, 나는 늘상 하던 대로 f(1)f(1), f(2)f(2), ...부터 값을 쭉 늘어놓고 규칙이나 주기성이 있는지 눈으로 찾았다.
지금 생각해보면 짧은 시간 내에 충분히 테스트 케이스 제너레이터를 만들 수 있었을 것 같은데, 결국 이번에도 시간에 쫓겨 그렇게 하지 못했다. 반성 포인트 +1.
어찌어찌 f(n)f(n) 값은 구한다 쳐도, ll, rr 범위가 10억 정도였기 때문에 어떻게 해도 구간 합을 시간 내에 구하지는 못했다. prefix sum이나 segment tree + lazy propagation을 생각해 봤지만 길이가 너무 커서 안 됐었고, 나중에 다른 사람에게 문제를 알려주니 sqrt decomposition처럼 bucket으로 나눠서 관리할 수도 있겠다고 말했었고, 나도 그렇겠다고 생각했다.

후기

맨 처음에도 말했듯 대상을 수상했다. 스코어보드 등수는 2등이다. 하지만 여기서 그치지 않고, 조금 더 나아가 생각을 해 보고 싶다.
4번을 풀지 못한 이유가 무엇이었을까? 문제를 보고 겁에 질려 "이건 내가 풀 수 없는 문제야"라며 스스로 단정짓고 5번으로 넘어가지는 않았는가? 심지어 그렇게 도망친 5번에서마저도 AC를 받지 못하고, 4번을 푼 1등에게 밀려 결국 2등을 기록했다. 부끄럽지 않은가?
대상이지만, 대상이 아니다. 표면적인 스코어보드에서 멍드립은 2등이지만, 내면의 스코어보드에서 멍드립은 2등을 차지할 자격이 없다. 나는 최선을 다하지 못했다.
준비 과정만큼은 자랑스럽게 여긴다. 앞으로의 대회에서는 준비 과정에서 지금 그대로의 겸손한 마음가짐으로 임하되, 본대회에서 조금 더 도전적일 필요가 있다고 생각한다.
끝으로, 대회 준비에 도움을 준 shiftpsh에게 이 글을 빌려 다시금 감사의 인사를 전한다.
내 정신적 지주와도 같은 독서 노트와 대상 상장
따핫