jh05013's profile image

jh05013

November 21, 2020 00:00

프로그래밍 문제 출제하기

programming-contest

서론

삼성 소프트웨어 멤버십 블로그에는 대회 개최에 관한 글을 몇 개 찾아볼 수 있습니다. 대회 준비와 운영이 어떻게 진행되는지를 알 수 있는 유용한 글입니다.

이 글은 문제를 어떻게 만들 것인가에 초점을 둡니다. 아이디어를 어떻게 구상하고, 지문은 어떻게 작성하고, 데이터는 어떻게 만들고, 문제 검수는 어떻게 해야 하는지를 다룹니다.

백준 온라인 저지에 문제를 내고 싶어요

문제 출제 안내에 따르면, 다음 중 최소 하나를 만족하는 유저는 문제를 출제할 수 있습니다.

  • BOJ 2000문제 이상 해결
  • Codeforces 레이팅 2200 이상
  • Topcoder 레이팅 2200 이상
  • ICPC 리저널 본선 10등 이상

한편, 대회 개최 안내에 따르면, 다음 중 최소 하나를 만족하는 유저는 대회 문제를 출제할 수 있습니다. 조건이 약화된 이유는 학교, 단체 등에서 대회를 열 때를 위함입니다. 각 학교의 모든 출제자가 위 조건을 달성하기는 쉽지 않죠.

  • BOJ 500문제 이상 해결
  • Codeforces 레이팅 1600 이상
  • Topcoder 레이팅 1400 이상
  • ICPC 리저널 본선 30등 이상

문제 구상하기

출제에 대한 철학은 사람마다 다를 것입니다. 저의 철학은 “문제를 먼저 만들고, 풀어서 출제하기”입니다. 그렇다면 질문은 “문제 아이디어를 어디서 가져오냐”입니다. 이에 답하기 위해 제가 2020년 11월까지 백준 온라인 저지에 출제한 문제를 모두 분류해 보았습니다.

Lewin님의 탑코더 글, antontrygubO_o님의 코드포스 인터뷰 글 등에서도 다른 사례를 찾아볼 수 있습니다.

현실 및 인터넷의 소재

퍼즐

  • Dev, Please Add This! - 이 문제에서 제시한 퍼즐은 Clickmazes 사이트의 Tilt Maze와 동일합니다. 별이 한 개인 버전은 그래프 순회로 풀 수 있는데, 별이 여러 개일 때는 지수 시간이 걸려서 잘 안 됩니다. 과연 별이 여러 개여도 효율적으로 해결할 수 있을지를 고민하다가 이 문제가 탄생했습니다.
  • Glen - 구데기컵 문제이기 때문에 지문이 길고 장황하지만, 그 점을 제외하면 일반적인 프로그래밍 문제입니다. 이 문제에서 풀어야 되는 퍼즐이 이 문제의 모티브인 OneShot에서 그대로 사용됩니다.

수학, 전산학 등의 소재

  • Faster Sorting - 지문에서도 언급했듯이, 이 과정은 팀소트 알고리즘에서 그대로 사용됩니다. 자세한 설명은 djm03178님의 글 특별한 정렬 알고리즘들을 참조하세요.
  • 랭퍼든 수열쟁이야!! - 랭퍼드 수열을 가져와 문제로 만들었습니다.
  • 우리는 진실을 잊고 살잖아 - “오라클”이라는 개념에서 가져왔습니다. 그래프를 처음부터 다 주는 게 아니라, 그 그래프의 “오라클”을 준다고 합시다. 우리는 두 정점을 오라클에게 물어보면 두 정점 사이에 간선이 있는지 알려줍니다. 오라클에게 질문을 몇 번 해야 그래프가 연결되었는지 알 수 있을까요? 모든 그래프를 고려한다면 최악의 경우에는 모든 정점 쌍을 질문해야 하겠지만, 하나의 그래프만 고려한다면 그렇지 않을 수도 있습니다.
  • 여러분의 다리가 되어 드리겠습니다! - 트리에 대한 잘 알려진 정리 중 하나로, 트리에서 하나의 간선을 제거하면 그래프는 항상 두 개의 연결 요소로 나누어진다는 것이 있습니다.
  • Hilbert’s Hotel - 힐베르트 호텔 역설을 가져와 문제로 만들었습니다.
  • 홀수와 짝수의 대결 - 포여 추측을 가져와 문제로 만들었습니다. 알고리즘 문제 치고는 풀이가 조금 이상한 문제지만, 구데기컵이라서 낼 수 있었습니다.
  • 문제를 푸는 문제 (잘못 구현한 오일러 회로) - 제 이산수학 교재의 연습문제에서 가져왔습니다. 이 문제에서 제시한 방법을 썼을 때 실패할 수 있는 정점이 없을 필요충분조건을 찾는 문제였습니다.

문제를 변형하거나 뒤집기

  • Satan Game - 지금은 삭제된 문제 중, 뱀과 사다리 게임을 끝낼 때까지 주사위를 굴리는 횟수의 기댓값을 구하는 문제가 있었습니다. 그 문제의 데이터를 만들던 중, 기댓값이 너무 커서 double이 아니라 long double을 사용해야 통과되는 데이터를 만들어냈습니다. 이 문제는 그 데이터를 재현하는 문제입니다. 이 문제가 나온 이후 기댓값이 훨씬 큰 데이터가 발견되었고, 뱀과 사다리 문제는 long double로도 풀리지 않게 되었습니다. (정해는 Python의 fractions를 사용했기 때문에, 정해가 터지지는 않았습니다.) 결국 오차 분석을 제대로 할 수 없어서 그 문제는 삭제되었습니다.
  • 회문은 회문아니야!! - 가장 긴 팰린드롬 부분문자열 문제는 Manacher 알고리즘으로 풀 수 있는 잘 알려진 문제입니다. 가장 긴 팰린드롬이 아닌 부분문자열은 어떨까요?
  • 성공 - 알고스팟 문제에서는 한번에 1x1 크기의 벽을 제거할 수 있습니다. 한번에 3x3 크기의 벽을 제거하면 어떻게 될까요? NxN은?
  • 맥주 99병 - 99 Bottles of Beer라는 유명한 프로그래밍 문제가 있습니다. “N Bottles of Beer”는 어떨까요?
  • Economic One-way Roads - 원래 만들려고 했던 문제는 “minimum spanning strongly connected graph”였습니다. 최소 스패닝 트리에서 “트리”를 “강하게 연결된 그래프”로 바꾸면 어떻게 될지를 생각하면서 만든 문제입니다.
  • Square, Not Rectangle - 히스토그램에서 가장 큰 직사각형을 찾는 문제는 꽤 유명합니다. 정사각형이라면 어떨까요?

다른 문제 또는 해법에서 아이디어를 가져오기

제가 자주 쓰는 방법은 아니지만, 다른 문제에서 영감을 받아 만들거나, 해법으로부터 역으로 문제를 만들 수도 있습니다.

  • Remote Control - 원래 만들려고 했던 문제는 2차원이 아니라 1차원이었고, 벽이 원점의 왼쪽과 오른쪽에 하나씩 있었습니다. Atcoder의 문제 Sandglass를 보고 영감을 받았습니다. 3년 후에 이 문제가 다시 떠올랐고, 2차원으로도 문제를 풀 수 있음을 알아내면서 이 문제를 만들었습니다. Sandglass를 볼 당시에는 2차원 버전의 풀이를 떠올리지 못했으니, 이것도 “문제를 먼저 만들고, 풀어서 출제한” 것으로 볼 수 있겠군요.

논외

이 분류에 속하는 문제는 제가 구상하지 않은 문제거나, 연습용 문제를 의도하고 만들었거나, 구데기컵에 내기 위해 만들었습니다.

  • 빠른 A+B, 합성함수와 쿼리, 큐 2는 빠른 입출력 연습용이나 특정 알고리즘 연습용으로 만들었습니다.
  • 레드 블루 스패닝 트리 2, 어려운 계단 수는 백준 온라인 저지에 이미 있는 문제의 입력 크기를 늘리거나, 추가적인 조건을 붙여서 만들었습니다.
  • 개구리 1, 2, 3은 사실 제가 만든 문제가 아닙니다. 이 대회를 검수할 때 개구리 2의 풀이를 제가 개구리 3으로 확장했고, 출제자님이 저를 이 문제의 출제자로 넣어 주셨습니다.
  • 제271회 웰노운컵의 구상은 제 친구가 했는데, O(N^3) 풀이를 제가 발견하고 출제 허락을 받았습니다. 수 개월 후 제2회 웰노운컵에 제안하면서 O(N^2) 풀이를 찾았고, 다른 검수자 분이 O(NlogN) 풀이를 찾아 주셔서 더욱 어려운 문제가 되었습니다.
  • 문제를 푸는 문제 (미니 앨범) 역시 구상은 제가 하지 않았고, 풀이만 만들었습니다.
  • 나머지는 모두 구데기컵 문제입니다.

풀이

대회 참가자의 경우, 자신의 풀이에 대한 정당성을 완전히 증명하지 않고 푸는 경우가 가끔씩 있습니다. 이를 속칭 “proof by AC”라고 하죠. 하지만 출제자가 proof by AC를 하면 안 됩니다. 출제자는 풀이가 옳음을 완전히 증명해야 합니다. 설령 증명에 4페이지가 필요하더라도 그렇습니다. 예상치 못한 곳에서 풀이가 틀렸을 지도 모르는 일이죠.

풀이가 시간, 메모리 제한 안에 잘 돌아감을 증명하는 방법은 크게 두 가지입니다.

  • 시간, 메모리 복잡도를 계산합니다.
  • 풀이가 특정 데이터에서 가장 오래 걸림을 증명하고, 그 데이터를 넣었을 때 시간, 메모리 제한 내에 여유롭게 돌아감을 확인합니다.

지문

문제를 구상했으면, 이제 이걸 지문으로써 설명해야 합니다. 이때는 기본적으로 설명문을 쓰는 능력이 요구됩니다.

  • 지문은 명확해야 합니다. 비문이 나타나서는 안 되며, 모호한 표현도 나타나지 않아야 합니다. 출제자의 선호에 따라 지문이 장황할 수는 있지만, 그로 인해 지문이 여러 방법으로 해석될 수 있으면 안 됩니다.
  • 부족한 정보가 있으면 안 됩니다.
  • 입출력의 조건을 완전히 명시해야 합니다. 이에 대해서는 후술합니다.
  • 위의 셋보다는 덜 중요한 요건이지만, 맞춤법 검사를 권장합니다.
  • BOJ Stack에서도 유용한 정보를 많이 찾을 수 있습니다.

물론 완벽한 지문을 작성하는 것은 쉬운 일이 아닙니다. 그래서 검수가 중요합니다. 검수에 대해서는 후술합니다.

입출력의 조건

단순히 “N이 입력될 때 N+1을 출력해라”라고 하면 N은 -2일 수도, 1.5일 수도, 10^100일 수도 있습니다. 다음은 입출력 설명을 작성할 때 고려할 사항 중 일부입니다.

  • 몇 번째 줄에 무엇이 주어지는지를 명시해야 합니다. 단순히 “A, B, C가 입력된다”라고 하면, 한 줄에 하나씩 총 세 줄이 입력될까요? 한 줄에 전부 입력될까요?
  • 모든 것에는 자료형이 필요합니다. x는 정수인가요, 자연수인가요, 실수인가요?
  • 모든 것에는 범위가 필요합니다. 최소 얼마, 최대 얼마인가요?
  • “int 범위”라는 표현은 좋지 않습니다. int 범위라는 것은 언어에 따라 다릅니다. C++의 int 범위라고 해도, C++ 표준에서는 int의 범위를 특정 범위로 고정해 두지 않습니다. 정확히 몇부터 몇까지인지 명시하는 것이 좋습니다.
  • 실수가 주어진다면, 소숫점 아래 몇째 자리까지 주어지나요? “정확히” 몇째 자리까지인가요, 아니면 “최대” 몇째 자리까지인가요?
  • 실수를 출력해야 할 경우, “정답과의 절대/상대오차는 $10^{-?}$까지 허용한다.”라는 문구를 추가하고, 실제로 정답과 출력의 절대/상대오차가 $10^{-?}$ 이하인지 검사하는 스페셜 저지를 작성하는 것이 좋습니다. 반올림하여 소수 몇째 자리까지 정확하게 출력하도록 하는 방법도 있지만, 오차가 아주 조금만 나도 반올림의 결과가 달라질 수 있기 때문에 안전하지 않습니다. 그래서 그 방법은 오차 없이 정확하게 계산할 수 있을 때에 쓰는 것이 권장됩니다.
  • 그래프가 주어질 경우, 정점은 최소 몇 개, 최대 몇 개인가요? 간선은 최대 몇 개인가요? 간선에는 방향이 있나요? 자기 자신을 잇는 간선이 존재하나요? 같은 정점 쌍을 잇는 두 간선이 존재하나요?
  • 좌표평면 상의 점이 주어질 경우, 좌표가 같은 두 점이 존재하나요? 세 점이 한 직선 위에 있는 경우는 없나요? (그런 경우가 있다면 명시할 필요는 없으나, 없다면 명시해야 합니다.)
  • 다각형이 주어질 경우, 단순다각형인가요?
  • 문자열은 무슨 문자로 이루어져 있나요? 알파벳 소문자? 숫자?
  • 테스트케이스가 여러 개인 문제일 경우, “테스트케이스의 개수”가 최대 몇인지를 명시하거나, “모든 테스트케이스에 대해 ??의 합”이 최대 몇인지를 명시하는 것이 좋습니다. 백준 온라인 저지에서는 이것이 명시되지 않은 문제들을 가끔씩 볼 수 있는데, 이는 몇 년 전까지의 관행이고 오늘날에는 둘 중 하나를 명시해 주는 것이 선호됩니다.

단, 입력의 조건을 지문으로부터 알아낼 수 있다면 입력 설명에서 생략되기도 합니다. 예를 들어 X가 “??의 개수”라면, X는 무조건 음이 아닌 정수일 것입니다.

데이터

채점 가능한 문제가 되려면 데이터가 있어야 합니다. 데이터도 지문 못지 않게 매우 중요합니다. 여기서부터는 Codeforces에서 제공하는 Polygon을 강력히 권장합니다. 입문 장벽이 낮지는 않지만 강력한 도구입니다. Polygon의 사용 방법에 대해서는 Acka1357님의 문제 출제를 위한 플랫폼 - Polygon 사용하기를 참조해 주세요.

올바른 데이터

먼저, 데이터가 입력 조건에 어긋나면 안 됩니다. 이는 문제가 성립하기 위한 필수 사항입니다. 당연한 말로 들릴 수 있겠지만, 그렇다고 방심해서는 안 됩니다. 가장 놓치기 쉬운 것은 “입력을 한 줄에 하나씩 준다고 했는데, 실제로는 한 줄에만 전부 들어오는 경우” 등 공백과 줄바꿈이 잘못된 경우입니다. 이러면 C++로 정해를 작성했을 때 assert로 잡기도 쉽지 않고, Python처럼 줄 단위로 입력을 받는 언어로 풀 때 아무 이유 없는 런타임 에러를 받습니다. 실제로 이런 일이 발생한 사례가 많고, 제가 이 오류를 발견한 문제만 20건이 넘습니다.

그래서 데이터가 올바른지를 검사하는 validator가 필요합니다. Polygon에 있는 validator 기능을 사용하면 됩니다. BOJ Stack에 있는 설명을 참조하세요.

BOJ Stack도 testlib를 사용하므로, Polygon에서 사용하는 validator를 Stack에서도 그대로 사용할 수 있습니다.

강력한 데이터

그 다음으로, 잘못된 코드가 통과하지 않을 정도로 데이터가 강력해야 합니다. 풀이 자체가 잘못되었거나, 시간 복잡도가 너무 크거나, 구현 실수가 발생하면 통과되지 않아야 강한 데이터라고 할 수 있습니다.

모든 잘못된 코드가 막히는 건 현실적으로 매우 어렵지만, 많은 코드를 만들어 볼 수록 좋습니다. 중요한 데이터의 예시를 몇 개 소개합니다. 마찬가지로 일부입니다.

  • 크기가 (즉 N의 값이나, 그래프의 정점 개수 등이) 최소인 입력은 반드시 넣읍시다. 문제를 푸는 사람들이 여기서 예상치 못한 예외를 겪을 수도 있습니다.
  • 크기가 최대인 입력도 반드시 넣읍시다.
  • 정해에 예외처리가 있을 경우, 그 예외처리에 해당되는 데이터를 반드시 넣읍시다.
  • 입력이 트리일 경우, 일자로 이어져 있는 트리, 한 정점의 차수가 매우 큰 별 모양 트리 등을 넣읍시다.
  • 입력이 수열일 경우, 가장 작은 수만 계속 나오는 수열, 가장 큰 수만 계속 나오는 수열, 오름차순 정렬된 수열, 내림차순 정렬된 수열 등을 생각할 수 있습니다.
  • 다익스트라 알고리즘을 잘못 구현하는 경우는 어떻게 막을 수 있을까요? djm03178님의 글 잘못 구현한 다익스트라 알고리즘 저격하기에서 알아볼 수 있습니다.

evenharder님의 글 UCPC 2020 출제 후기에서 실제 사례를 확인해 볼 수 있습니다.

시간, 메모리 제한

잘못된 코드가 통과하지 않으면서, 정해가 여유롭게 통과할 정도의 시간, 메모리 제한을 잡는 것이 권장됩니다. Acka1357님의 글을 인용합니다.

모든 과정이 끝났다면 각 문제에 알맞은 메모리제한과 시간제한을 설정합니다. 이는 출제자의 의도보다 좀 더 넉넉하게 하는 것이 좋습니다. 같은 솔루션임에도 참가자마다 누군가는 통과하고, 누군가는 통과하지 못하는 상황을 피하기 위해서입니다. 하지만 넉넉하게 잡는 바람에 의도하지 않은 솔루션까지 통과하는 일이 발생하기도 하니, 이 과정 역시 다양한 방법의 실험이 필요합니다.

스페셜 저지

Validator처럼, 스페셜 저지도 특수한 라이브러리로 구현할 수 있습니다. Polygon에서는 checker라고 부릅니다.

스페셜 저지의 구현도 위의 Polygon 글에서 볼 수 있으나, ouf.readSpace()와 ouf.readEoln()을 하면 공백이 정확하게 출력된 경우만 통과합니다. 코드포스나 백준 온라인 저지는 출력의 맨 끝에 공백이 있거나, 공백을 출력해야 할 때 줄바꿈을 출력해도 정답으로 간주합니다. 이런 경우를 허용하려면 ouf.readSpace()와 ouf.readEoln()을 하지 않아야 합니다.

검수

마지막으로, 자신의 문제를 시험삼아 풀어 줄 검수자가 필요합니다. 다른 사람들이 이 문제를 어떻게 해석하는지, 지문 이해에 문제가 없는지, 풀이에 어떻게 접근하는지를 알 수 있습니다. 또한 출제자가 발견하지 못했던 지문, 데이터 등의 문제점을 잡아낼 수도 있고, 예상치 못했던 더 좋은 풀이를 찾을 수도 있습니다. 출제나 검수 경험이 풍부한 사람이라면 특히 그렇습니다.

대회와 관계 없이 문제를 낼 경우 검수자를 백준 온라인 저지 게시판이나 Slack에서 구할 수 있고, 대회 문제를 출제한다면 대회의 검수자가 검수를 할 것입니다.

데이터와 검수에 대한 사항은 Acka1357님의 글 프로그래밍 대회를 개최하기 위한 10가지의 “8. 데이터 제작 및 검수” 부분에서도 읽어볼 수 있습니다.

결론

과거에는 백준 온라인 저지의 대회에서 지문, 데이터 등의 조건이 제대로 충족되지 않은 문제가 많이 있었습니다. 다행히도 출제, 검수 조건이 더 엄격해지면서 그런 문제는 줄었습니다. 사람의 실수가 늘 그렇듯 완전히 막을 수는 없지만, 출제와 대회 개최에 대한 가이드라인이 있으면 효과적일 것입니다. 이 글도 그 중 하나가 되기를 바라며, 그래서 이 글은 시간이 지나면서 내용이 추가될 수도 있습니다.