UCPC 2022 출제 및 검수 후기

운 좋게도 UCPC 2022에서 문제 출제 및 검수를 맡았습니다. 5월 초에 처음 출제진에 합류해 약 2달 반 동안 활동했는데, 그 과정을 적어보겠습니다.

 

UCPC란 & 출제진이 된 계기

UCPC는 전국 대학생 프로그래밍 대회 동아리 연합에서 주최하는 프로그래밍 대회입니다. 매년 약 800명이 참가하는 규모 있는 대회이고, 올해 대회인 UCPC 2022에는 총 903명이 참가했습니다.

 

UCPC에는 Call for Tasks라는 문제 아이디어 모집 과정이 있습니다. 이러한 절차를 통해 UCPC에 출제할 만한 좋은 퀄리티의 문제들을 모으고, 동시에 선택된 문제의 출제자는 출제진에 합류해 출제 및 검수 역할을 맡게 됩니다.

 

UCPC 2022 Call for Tasks

 

저는 지금껏 혼자 problem solving을 공부해 왔습니다. 주변에 problem solving을 공부하는 사람이 적었고, 특히나 실력 있는 분들은 더더욱 적었습니다. 동시에 저는 실력을 키우고 싶었습니다. 지금의 실력으로는 애매하다는 생각을 자주 하곤 했습니다. 그래서 최고의 실력자들을 만나 그들의 노하우를 배우고 싶다는 생각이 항상 있었습니다. 그들의 사고 방식이나, 공부 습관, 태도, 공부해온 기간, 환경 등을 알고 싶었습니다.

 

출제진이 되면 다른 출제진들을 만날 수 있을 것이기에, Call for Tasks가 이러한 갈증을 해결할 좋은 기회라고 생각했습니다. 그래서 당시 생각해 둔 아이디어를 급하게 문제로 만들어 Call for Tasks에 제출했습니다. 사실 그렇게 많은 기대를 하지는 않았습니다. 객관적으로 그렇게 좋은 문제는 아니라고 생각했습니다. 그런데 놀랍게도 제 문제가 채택되었습니다. 새벽에 동아리방에서 메일을 확인하고 혼자 기뻐서 소리를 질렀던 기억이 납니다.

 

당시 받았던 메일

 

지금 생각해보면 기하 문제이고, 또 쉬운 문제라는 흔치 않은 조합 덕분에 채택되었던 것 같습니다.

 

문제 출제

저는 예선에서 1문제를 출제하고, 본선에서 1문제를 공동 출제했습니다. 저는 UCPC 2022 이전에 알고리즘 문제를 출제한 경험이 전혀 없습니다. 그래서 문제 세팅을 위한 모든 과정을 처음부터 배워야 했습니다. 문제 세팅은 크게 2가지 과정으로 나뉩니다. 데이터 세팅과 문제 지문 작성입니다.

 

데이터 생성

알고리즘 문제의 채점 방식은 일반적으로 다음과 같습니다. 채점 서버는 입력 데이터와 그에 대응되는 출력 데이터를 가지고 있습니다.^[각주:1] 제출한 코드가 모든 입력에 대해 시간 내에 올바른 출력을 낸다면 제출한 코드는 맞은 것으로 취급됩니다. 하나라도 올바르지 않은 출력을 낸다면 틀린 것으로 취급됩니다.^[각주:2]

 

입력 데이터를 생성하는 것은 까다롭습니다. 데이터가 부족하면 틀렸거나 시간 초과를 받아야 할 코드가 '맞았습니다'를 받곤 합니다. 데이터는 엄격한 형식을 지켜야 합니다. 데이터의 형식이 맞지 않을 경우 올바른 코드가 '틀렸습니다' 등을 받을 수 있습니다. 또한 데이터가 특정 조건을 만족해야 하는 경우, 데이터를 생성하는 것 자체가 하나의 알고리즘 문제가 되곤 합니다. 제 경우엔 아래와 같은 문제가 있었습니다.

 

최대 5000개의 점이 주어지는데, 어떤 세 점도 한 직선 위에 있어서는 안됩니다

 

제가 예선에서 출제했던 문제 N수매화검법의 입력 조건입니다. 요약하자면 최대 $2\,500$개의 선분이 입력으로 주어집니다. 하나의 선분은 두 개의 점으로 정의되니 $5\,000$개의 점들이 입력으로 주어지는 셈입니다. 그런데 주어지는 점 중 어떤 세 점도 한 직선 위에 있어서는 안됩니다. 이러한 조건을 만족하는 점 데이터를 어떻게 생성할 수 있을까요?

 

어떤 소수 $p$에 대하여 $0 \leq i < p$를 만족하는 모든 점 $(i, i^2 \mod p)$의 집합은 세 점이 한 직선 위에 있는 경우를 포함하지 않습니다. 따라서 적절한 소수 $p$를 찾아 $(i, i^2 \mod p)$ 꼴의 랜덤 데이터를 생성할 수 있습니다. 이렇듯 데이터를 생성하는 과정 자체가 하나의 알고리즘 문제가 되곤 합니다. 이 방법은 Hyperbolic님께서 제공해 주셨습니다.

 

데이터 세팅 과정은 데이터를 생성하는 과정과, 데이터를 검증하는 과정으로 나뉩니다. 두 과정을 한꺼번에 처리할 수도 있지만 데이터 세팅 과정에서의 실수를 최대한 줄이기 위해 두 단계로 나누어 처리합니다.

 

데이터 검증

앞에서 어떤 세 점도 한 직선 위에 있지 않도록 점들을 생성하는 방법에 대해 보았습니다. 그렇다면 임의의 점들이 주어질 때 어떤 세 점이 한 직선 위에 있는 경우가 있는지는 어떻게 검증할 수 있을까요?

 

먼저 나이브한 $O(N^3)$ 풀이를 떠올릴 수 있습니다. 모든 세 점 조합에 대해 세 점이 한 직선 위에 있는지를 검사하는 것입니다. 그러나 $N$이 최대 $2\,500$이므로 이 풀이는 너무 느립니다. Polygon^[각주:3] 상에서는 너무 느려 작동하지 않고, 로컬에서 검사한 후 검사한 데이터를 Polygon에 업로드해야 합니다. 가능한 방법이긴 하지만, 다소 귀찮고 오래 걸립니다. 더 나은 방법이 있을까요?

 

모든 점 $i$에 대해 $i$를 기준점으로 각도 정렬을 수행한 후, 어떤 인접한 두 점과 $i$가 한 직선 위에 있는지를 보는 것으로 충분합니다. $O(N^2 \log N)$의 시간복잡도를 가지는 보다 빠른 방법입니다. Polygon 상에서도 충분히 작동하게 됩니다. 이 방법은 functionx님께서 제공해 주셨습니다.

 

제 문제에서는 $N$이 최대 $2\,500$이기 때문에 $O(N^2 \log N)$의 시간복잡도로 충분하지만, 만약 $N$이 최대 $100\,000$이라면 어떻게 해결할 수 있을까요? 이런 경우에는 로컬에서 검사한 후 검사한 데이터를 Polygon에 업로드하는 방법을 사용한다고 합니다.

 

문제 조건 수정하기

제가 본선에서 공동 출제했던 커넥티드 카 실험은 문제 자체도 쉽고 데이터 세팅도 쉬웠지만, 독특한 이슈가 있었습니다.

 

이 문제가 처음 공개되었을 때, 출제진들 사이에서 처음으로 나온 풀이는 무려 구간을 하나의 정점으로 바꾸는 매우 어려운 난이도의 풀이였습니다. 이 풀이의 시간복잡도는 상수가 큰 $O(N \log N)$입니다. 출제자의 의도와 완전히 어긋나기 때문에 이 풀이를 막기 위해 $N$을 최대 $1\,000\,000$까지 늘렸습니다.

 

$N$의 범위를 늘리니 다른 문제가 있었습니다. 이 문제의 초기 버전에서는 $x_i$가 오름차순 정렬된 상태로 주어지지 않았습니다. 따라서 문제를 푸는 과정에서 $x_i$를 기준으로 커넥티드 카들을 정렬해야 했습니다. 파이썬에서는 정렬에 드는 $O(N \log N)$만으로도 시간초과에 가까운 시간이 소모되었습니다.

 

그래서 $x_i$가 오름차순 정렬된 상태로 주어지는 것으로 입력 형식을 수정했습니다. 입력이 $x_i$ 기준 오름차순으로 주어질 때 $O(N)$에 문제를 해결할 수 있기 때문에 파이썬으로도 이 문제를 해결할 수 있습니다. 이 아이디어는 kclee2172님께서 제공해 주셨습니다.

 

지문 작성

N수매화검법

N수매화검법은 무협 컨셉으로 쓰여졌습니다. 하지만 지문의 초기 버전은 달랐습니다.

 

초기 버전의 지문

 

초기 버전의 지문에서는 아무런 컨셉 없이 문제의 요구 사항을 적었습니다. 이대로 출제한다면 별로 기억에 남는 문제가 되지 못할 것 같아 컨셉을 추가했습니다.

 

고려했던 또 다른 컨셉으로는 조금 뜬금없지만 칸예 웨스트 컨셉이 있습니다. 저는 래퍼 칸예 웨스트의 광팬입니다. 최근에 본 칸예 웨스트 다큐멘터리 Jeen-yuhs에서 큰 감명을 받아 다음과 같은 컨셉의 지문을 작성해 보았습니다.

 

칸예 웨스트 버전의 지문

 

개인적으로는 칸예 웨스트 버전의 지문이 더 마음에 들지만, 참가자들이 힙합보다는 무협에 익숙할 것 같아 최종적으로 N수매화검법으로 결정했습니다.

 

커넥티드 카 실험

많은 기업에서 UCPC를 후원해주십니다. UCPC에서는 다양한 방식으로 스폰서들을 홍보하는데, 문제의 지문에 해당 기업을 홍보하는 내용을 넣기도 합니다. 커넥티드 카 실험은 현대오토에버의 스폰서 문제였습니다. 어떤 기업을 광고하는 문제라는 점에서 이 문제의 지문을 작성하는 것은 흥미로웠습니다. 현대오토에버에서 개발한 소프트웨어 플랫폼 모빌진, 현대차 그룹의 AI 기반 차량 OS인 ccOS 등 다양한 소재로 지문을 작성해 보았는데, 최종 버전은 아래와 같습니다. 최종 버전의 지문은 대부분 doju님께서 작성해주셨습니다.

 

최종 버전의 지문

 

대회 당일

엄청나게 기대를 한 나머지 대회장에 제일 먼저 도착했습니다

 

UCPC 2022 본선은 코로나 이후 약 3년 만에 다시 열리는 오프라인 대회였습니다. 개인적으로는 코로나 이전에 오프라인 대회를 참가해본 적이 없어 처음 경험해보는 오프라인 대회였습니다. 힘들긴 했지만 처음부터 끝까지 정말 재미있었습니다.

 

문제를 맞추면 풍선을 달아줍니다

 

유래가 무엇인지는 모르겠지만 많은 프로그래밍 대회에서 문제를 맞추면 풍선을 달아주곤 합니다. 대회가 시작되고 가장 힘들었던 것이 바로 이것이었습니다. 대회 초반 2시간 정도는 쉬지 않고 풍선을 날랐던 것 같습니다.

 

MOLOCO 스폰서 세션

 

대회가 끝나고 스폰서 기업들의 발표를 들었습니다. 전 스폰서 세션마저도 재미있었습니다. 저도 MOLOCO에 들어가고 싶네요.

 

참가자 단체 사진

 

스코어보드를 공개하고 참가자들끼리 찍은 사진입니다. 1등은 이변 없이 구사과님이 속한 ‘초비상!!’팀이 차지했습니다.

 

운영진 단체 사진

 

운영진끼리도 한 컷 찍었습니다. 다들 정말 고생 많으셨어요~

 

끝으로

모든 과정이 저에게는 의미 있고 좋았습니다. 상투적인 말이 아니라 정말로 그랬습니다. 다른 운영진분들에게 배운 것도 정말 많았고, 제가 앞으로 나아가야 할 길도 더 뚜렷해졌습니다. 다음에도 비슷한 기회가 온다면 다시 참가하고 싶습니다.

 

개인적으로 첫 대회 문제 출제라 부족한 점이 많았습니다. 부족한 실력임에도 잘 이끌어 주시고, 아낌 없이 조언해주신 운영진 분들께 진심으로 감사드립니다. 마지막으로 문제 출제 기회를 주신 혜아님께 한번 더 감사하다는 말씀을 드리고 싶습니다.

 

이상 후기 끝!

 

1. 스페셜 저지를 제외한 일반적인 채점 방식에 대한 설명입니다. [본문으로]
2. 엄밀한 설명은 아닙니다. [본문으로]
3. Polygon은 프로그래밍 대회 문제 출제를 위한 플랫폼입니다. [본문으로]