국내에서 가장 불꽃 튀는 알고리즘 대회 중 하나인 UCPC 2020 예선이 지난 7월 25일에, 본선이 8월 1일에 진행되었습니다. 저는 예선의 E번 감자 농장, H번 사과나무 그리고 본선의 G번 그건 망고가 아니라 고양이예요를 출제할 기회를 얻었습니다.
이 포스팅에서는 UCPC에서 문제를 제출한 순간부터 대회가 끝날 때까지 문제 개발이 어떻게 이루어졌는지를 다루어보고자 합니다. 테스트 케이스 제작에 초점을 두지만, 일반적인 검수 과정에 있어서도 길라잡이가 될 수 있으리라 생각합니다. 제가 만든 문제들을 해부하듯이 설명하기 때문에, 풀이도 서술되어 있음에 유의해주시길 바랍니다.
Call for Tasks
저는 Call for Tasks에 5문제를 제출했습니다. 원래는 개인대회에 서브태스크 형태로 낼 목적으로 만든 문제들이었습니다. 다만 solved.ac 기준 다이아 상위 이상의 어려운 문제들이 생각나지 않아 많은 사람들이 보고 즐길 수 있는 UCPC에 제안해보기로 했습니다. 작년에 열심히 활동했던 팀인 Powered by Zigui가 다른 팀원들의 졸업으로 활동이 어려워져서, 미련 없이 문제를 낼 수 있었습니다.
제안 메일은 5월 8일에 보냈으며, 답장은 Call for Tasks 모집 종료 이후 1주일쯤 뒤에 왔습니다. 예선에 2문제, 본선에 1문제, 예비로 1문제, 그리고 1문제 탈락이었습니다. 탈락된 문제는 조금 뻔하고 어딘가에 있을 법한 문제라서 그러려니 했습니다.
제안할 당시 사과나무 문제의 데이터는 완성되어 있었고, 나머지 두 문제는 C++ 정해만 있는 상황이었습니다. 다만 대회 준비를 이른 시간부터 시작했고 지문과 정해 코드까지는 틀이 갖추어져 있었기에 문제 제작 중 촉박하다는 느낌은 전혀 들지 않았습니다.
데이터 제작 흐름
데이터 제작은 보통 다음과 같이 진행됩니다.
- 출제자가 정해 코드 작성
- 다음의 과정들이 순서 없이 반복됨
- 오답 코드 예상 및 작성
- 일반/예외처리/반례 generator 제작
- 검수진의 다양한 코드 추가
- 문제 조건 변경으로 인한 코드 변경
- 문제 완성
오답 코드 예상은 출제자의 몫이지만, 다른 출제진 및 검수진와 토의를 하면서 다양하게 구체화됩니다. generator도 비슷하게 간단한 예외 케이스는 타인이 추가하기도 합니다. 검수진이 맞아야 하는데 틀리거나, 틀려야 하는데 맞는 코드나, 시간 초과가 나야 하는데 맞는 코드를 추가하며 문제가 더욱 견고해집니다.
토의는 Slack에서 진행되었으며, 데이터 제작은 Polygon에서 완성된 패키지를 다운받아 BOJ Stack에 옮기는 방향으로 했습니다. 가끔씩 Polygon이 서버가 다운될 때가 있어서 주기적으로 백업이 진행되었습니다.
사과나무
사과나무는 Call for Task로 모집된 문제 중 가장 쉬운 문제이면서 유일한 실버 문제였습니다. 쉬운 문제라 할지라도 테스트 케이스 제작이나 구상이 꽤 어려운 때가 있는데 사과나무가 여기에 해당되었습니다.
오답 코드 예상
정해는 변수 몇 개와 조건문 2개만 있으면 되기 때문에 다음과 같은 오답 코드를 예상할 수 있습니다.
- 조건문 2개 중 1개가 누락된 경우
- 조건문의 부등호 방향이나 등호 여부가 잘못된 경우
- 약간 다른 값을 이용해 조건문을 판별한 경우
- 첫 번째 수나 마지막 수를 무시한 경우
쉬운 문제에서 64비트 정수형의 사용을 강제하고 싶지 않아서 범위를 작게 잡았는데, 다음으로 쉬운 문제가 64비트 정수형 사용을 요구했다보니 괜히 그랬나 싶기도 합니다.
예제를 친절하게 넣어줬기 때문에 정해로 접근했다면 바로 통과할 수 있는 수준이었으나 그렇게 진행되지는 않았습니다.
Generator 제작
위에서 예상한 오답 코드를 저격하려면, 경계 조건에 해당하는 테스트 케이스가 많이 필요합니다. 그래서 generator를 여러 개 만들었습니다.
gen_all_zero: 사과나무의 높이가 전부 0인 generator입니다.gen_no_skew: 답이 2가 하나 모자라서NO인 generator입니다. 값이 skew되어 있지는 않은데 왜 skew라고 이름붙였는지는 잘 모르겠습니다. 흔히 일어나는 일입니다.gen_no_skew2: 답이 2가 하나 모자라서NO인 generator입니다. 이쪽은 값이 skew되어 있습니다.gen_not_3: 합이 3의 배수가 아니라서NO인 generator입니다.gen_yes_3: 합이 3의 배수인 generator입니다. 값은 랜덤으로 넣기 때문에 매우 높은 확률로 답이YES가 됩니다.gen_yes_skew: 답이YES인 generator입니다. 이 코드도 값이 skew되어 있지는 않은데 왜 skew라고 이름붙였는지는 잘 모르겠습니다. 기본적으로는 2의 개수가 딱 알맞지만 여유있게 줄 수도 있습니다.gen_yes_skew2: 답이YES인 generator입니다. 이쪽은 값이 skew되어 있습니다.
지금 돌아보니 1 1 1 1 1 1처럼 답은 NO인데 2가 조금 더 모자라는 케이스도 넣었으면 하는 아쉬움이 남습니다.
테스트 케이스 조절 및 검수
개인 대회 출제를 겨냥하고 데이터를 제작했을 때는 48개의 테스트 케이스가 있었습니다. 그러나 2번째로 쉬운 문제의 위치에 있는데 테스트 케이스가 너무 많으면 채점에 지장이 생길 수 있습니다. 때문에 여러 오답 코드들을 잘 걸러내는 24개만 남기고, YES 12개 NO 12개로 배치했습니다.
제안시에는 $N \leq 10^4$였는데 검수 과정에서 $\mathcal{O}\left(N^2\right)$풀이가 발견되면서 $N \leq 10^5$로 변경하였고 이 과정에서 generator를 손볼 일이 있었습니다.
쉬운 문제라서 검수 과정에서 큰 문제는 없었습니다.
결과
예선 대회가 부득이하게 거의 24시간 동안 진행되어서 테스트 케이스를 줄인 보람은 별로 없어졌습니다. 제가 생각했던 정해로 풀었던 팀도 다수 있었으나, 제가 예상하지 못한 방향으로 가는 팀들도 많았습니다.
- 매번 물뿌리개를 뿌리며 정렬을 하는 풀이 (시간 초과)
- multiset 등을 이용해 물을 조금씩 뿌려나가는 풀이 (시간 초과)
- multiset 등을 이용해 구성적 방식으로 물뿌리개를 효율적으로 뿌려나가는 풀이
- 조금 최적화된 $\mathcal{O}(\sum h_i)$ 풀이 (500ms 이상 걸리는 코드도 있었습니다)
- 각 나무 높이를 3이나 6으로 나눈 나머지를 이용해 따로 처리하는 풀이 (실수가 나기 쉬운 접근방법입니다)
- 높이가 1인 나무만 예외처리해서 구성적 방식으로 물뿌리개를 뿌린 풀이
오답이 나오는 대부분의 코드들은 gen_yes_skew 쪽 데이터에서 YES 대신 NO를 출력하였지만, 일부 코드는 gen_no_skew 쪽에서 NO 대신 YES를 출력하기도 하였습니다. 몇몇 코드는 1~2개의 테스트 케이스에서만 답을 잘못 내기도 하여서, 맞았습니다를 받는 코드 중에서도 사실은 틀린 코드가 있지 않을까 싶습니다. 그래도 틀린 풀이가 막 통과되는 ‘물데이터’는 아니어보여 다행입니다.
알고리즘 문제풀이에 익숙하다면 어렵지 않게 수학적 관찰을 해낼 수 있는 문제지만, 이런 접근이 생소한 분들에게는 난감했으리라고 생각합니다.
감자 농장
감자 농장은 누적합과 케이스 분류를 통해 풀 수 있는 문제지만 어느 정도의 난이도가 있습니다. 그중 구현과 식 구상이 상당한 지분을 차지합니다.
Call for Task로 모집하기 전에는 서브태스크가 있었으나 UCPC는 ICPC 스타일이므로 서브태스크가 필요가 없어졌고, 테스트 케이스도 $N = 10^6$ 언저리에서 만들면 되어 편했습니다.
오답 코드 예상
쿼리형 문제이기 때문에, off-by-one error보다는 구현 실수로 인한 미스가 많을 것으로 생각되었습니다. 정해를 짤 때도 예제로 나온 4개까지는 맞는데 실수가 있는 경우도 있었습니다. 다행히 이 문제는 naive 코드를 구현하기가 매우 쉽기 때문에, 반례를 찾자면 어렵지 않게 찾을 수 있으리라 생각합니다. 출제 과정에는 있었으나 대회에선 빼버린 예제 5번은 다음과 같습니다.
20 5
.PP.P.P...P.P...P.P.
4
8
12
16
20
Generator 제작
Generator도 나름 간단한 편입니다.
gen_no_rock: 바위(R)가 없는 농장 데이터를 만듭니다.gen_one_rock: 바위가 한 덩어리 있는 농장 데이터를 만듭니다.gen_two_rock: 바위가 두 덩어리 있는 농장 데이터를 만듭니다.gen_rp_random: 바위와 감자를 랜덤하게 배치합니다.
4개의 코드 모두 인자로 --potato-ratio 와 -n 을 받습니다. 최신 기능 중 하나로 testlib.h 에서 opt 함수를 통해 인자를 안전하고 편하게 받을 수 있습니다. 그 외로 --rock-ratio, 바위를 넣을 구간 정보 등을 인자로 넘겨줍니다. generator를 짤 때도 빈 칸을 1개는 남겨두는 등의 예외처리는 잘 해줘야 합니다.
교육적인 목적으로 gen_two_rock.cpp 를 공개합니다.
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> vans;
int main(int argc, char* argv[]) {
registerGen(argc, argv, 1);
int n = opt<int>("n");
int lpos1 = opt<int>("l1");
int rpos1 = has_opt("r1") ? opt<int>("r1") : lpos1;
int lpos2 = opt<int>("l2");
int rpos2 = has_opt("r2") ? opt<int>("r2") : lpos2;
double pp = opt<double>("potato-ratio");
string s(n, '.');
for(int i=lpos1-1;i<=rpos1-1;i++)
s[i] = 'R';
for(int i=lpos2-1;i<=rpos2-1;i++)
s[i] = 'R';
for(int i=0;i<n;i++) {
if(s[i] == 'R') continue;
if(pp > rnd.next(1.0)) s[i] = 'P';
else vans.push_back(i+1);
}
if(vans.size() == 0) {
s[0] = '.';
vans.push_back(1);
}
shuffle(vans.begin(), vans.end());
int q = min((int)vans.size(), 100'000);
cout << n << ' ' << q << '\n' << s << '\n';
for(int i=0;i<q;i++)
cout << vans[i] << '\n';
return 0;
}
이러면 gen_two_rock --potato-ratio=0.10 -n=950000 -l1=123456 -l2=456789 > $ 등의 스크립트로 Polygon에서 테스트를 만들 수 있습니다. r1이나 r2 를 인자로 주지 않고도 has_opt 함수를 이용해 프로그램 내부적으로 설정할 수 있습니다.
테스트 케이스 조절 및 검수
사풀이가 통과하기 힘든 문제라고 판단되어 테스트 케이스를 많이 만들 필요는 없었습니다. 원래는 $Q \leq 10^6$으로 하려 했으나 입출력으로 인한 시간 소모가 커질 것 같아 현재와 같이 바꾸었습니다.
검수 과정에서 sparse tree나 segment tree를 이용한 $\mathcal{O}((N+Q) \lg N)$ 코드도 나왔는데, 실제 대회에서도 이쪽으로 해결하거나 감자나 돌의 위치를 찾는데 이분 탐색을 사용한 팀들이 적지 않게 있었습니다. $N \leq 10^6$ 정도에서도 $\mathcal{O}(N)$과 $\mathcal{O}(N \lg N)$을 구분하기는 일반적으로 어려울 뿐더러 양쪽 모두 구현 난이도가 상당하기 때문에 괜찮다고 판단하였습니다.
결과
예선 대회가 엄청 길어지면서 난이도에 비해 많이 풀린 문제가 되었습니다. 특별한 자료구조가 필요하지 않고 문제의 요구사항을 이해하기 쉬운 편이라 그렇지 않았을까 싶습니다. 5솔브 팀 중 감자 농장을 해결한 팀도 있었습니다. 본선 진출과 하등 상관이 없음에도 많이 도전해주셔서 감사드립니다.
그건 망고가 아니라 고양이예요
BOJ Slack에서 밈이 되기도 했던 “그건 망고가 고양이예요” 문장으로 만든 문제입니다. 몇몇 분들은 맞춤법이 잘못된 것으로 오인하기도 하였으나 “-에요”가 아닌 “-예요”가 맞습니다.
오답 코드 예상
naive한 dfs 코드를 최적화해야 하는 문제라, 덜 최적화를 했음에도 통과되지 않게 데이터를 만들어야 했습니다. 때문에 다음과 같은 오답(시간 초과)을 예상했습니다.
- $k$를 줄이지 않고 dfs를 하는 코드
- 문자열의 위치를 찾을 때 이진 탐색을 쓰지 않는 코드
이 정도로도 충분할 줄 알았는데, 제 정해 코드에도 비효율적인 부분이 있어 다음을 추가로 고려하였습니다.
- $M_0$를 순회할 때 쿼리의 시작 지점까지 남은 문자를 하나하나 순회하는 코드
- $M_0$를 순회할 때 쿼리의 끝 지점까지 남은 문자를 하나하나 순회하는 코드
위 코드들은 시간 복잡도에 $\left\vert M_0 \right\vert$가 곱해지기 때문에 특정 데이터에서 느릴 수밖에 없습니다. BOJ 기준 5~15초 이상의 실행시간을 보였습니다.
또 정해가 사소한 부분에서 잘못된 답을 출력하고 있었는데, 해당 부분도 수정하면서 다음을 추가했습니다.
- 두 문자열의 길이가 현저히 차이가 나는 경우
검수 막바지에 문자열의 길이를 overflow 처리 없이 그냥 계산하는 코드가 통과되는 걸 확인했고, 이를 저격하는 데이터를 만드는 데 3시간 정도를 투자하여 만들었습니다.
Generator 제작
일반적인 generator는 다음과 같습니다.
gen_single: $S$에$가 1개 들어가 있는 케이스를 만듭니다.gen_mult: $S$에$가 여러 개 들어가 있는 케이스를 만듭니다.
이런 문제에서는 합이 $x$인 $n$개의 양의 정수들이 필요한데, 저는 구글링을 통해서 구현했으나 2020년 초반에 testlib.h에 rnd.partition(siz, sum[, min_part=0])이라는 함수가 추가되었으니 편히 이용하시면 될 것 같습니다.
그 외에 특별한 테스트 케이스를 출력하도록 하드코딩한 generator도 있었습니다. 예를 들어 $M_0$의 거의 처음 부분이나 끝 부분만 쿼리로 주는 데이터가 있습니다.
테스트 케이스 조절 및 검수
테스트 케이스는 40개 정도로 준비하였으며, 위에서 언급한 모든 코드들이 오답을 받는 것을 확인하였습니다. Java나 Kotlin은 좀 느려서 시간제한을 여유롭게 3초 정도로 주었습니다.
결과
난이도에 비해 많이 안 풀린 문제가 되어버렸습니다. 첫 AC도 상당히 느린 68분째에 나왔으며, 그 다음 AC는 3시간이 넘어서야 나왔습니다(182분).
끝나고 주변에서 의견을 듣고 분석해봤습니다.
- 디버깅이 어렵습니다.
- $k$를 줄일 때 간과하기 쉽지만 중요한 예외처리를 해야 합니다. 저는 이 부분이 문제가 안 될 것으로 생각하였으나 이 파트에서 막힌 검수진이 두 분 계셨고, 대회 때도 많은 팀의 발목을 잡은 것으로 추정됩니다.
- integer overflow를 조심해야 합니다.
a * b > m이랑a > m / b이 동치라는 성질을 이용해 처리하는 방법이 가장 간단합니다. - 문제가 구현 성격을 띄고 있기 때문에 구상을 잘 해야 합니다.
현재 이 문제는 solved.ac 기준 Diamond V로 분류되어 있습니다. 이 정도 난이도를 예상하진 못했는데 (검수한 출제진 중 이 문제를 다이아 급으로 본 분이 계시긴 했습니다) 조금 얼떨떨하기도 합니다.
결론
문제 준비가 학기중에 시작되어 바쁘기도 했지만 ‘내가 만든 문제를 수많은 분들이 도전한다’는 보람 덕분에 여기까지 올 수 있었습니다.
알고리즘 문제풀이를 몇 년간 하면서도 아직도 ‘좋은 문제’는 느낌만 올 뿐, 정의까지는 내리지 못하고 있습니다. 출제 과정에서도 느꼈지만 제 문제가 그렇게 좋고 참신한 문제로 생각되지는 않습니다. 그래도, 빛나는 최신 아이디어로 무장하지는 않았을지라도 누군가에게는 괜찮은 교육적인 문제였으면 좋겠습니다. 앞으로도 더 나은 ‘좋은 문제’를 만들어보겠습니다. 감사합니다.