좋은 문제 만들기

tl;dr

글이 너무 길어서 읽기 귀찮다면 결론만이라도 읽자.

개요

요즘 커뮤니티 대회에 관해 말이 많다. 최근 여러 대회에서 대회 이후에 문제 오류가 발견되는 상황이 있었고, 현재의 대회 검수 시스템에 대한 전반적인 재정비의 필요성이 시사된 바 있다. 나 역시 현재의 검수 시스템에 문제가 있음에 동감하는 바이지만, 이 글에서 이야기하고자 하는 바는 아니다. 이 글에서 이야기하고자 하는 것은 문제의 질에 관한 것이다. 조금 민감한 주제일 수 있다는 것을 인지하고 있고, 이 글에 적힌 건 어디까지나 내 의견일 뿐, 절대적인 것이 아님을 전제로 읽어주셨으면 한다.

(비고: 글을 올리기 전 몇몇 사람들에게 피드백을 받은 결과, "좋은 문제"의 의미가 조금 모호하다는 이야기를 들었다. 내가 이 글에서 이야기하고자 하는 것은 문제를 세팅하거나 검수하는 방법론에 대한 것이 아니다. 예를 들어 문제 지문이 이해가 불가능하거나, 문제 풀이에 오류가 있거나, 증명을 하지 않고 냈거나, 비슷한 사례들은 이 글에서 내가 다루고자 하는 것이 아니다. 나는 이런 것들을 "문제"(Task)로 취급하지 않는다.)

대회 출제의 기준

일단 내가 이 글에서 가장 하고 싶은 이야기는 이것이다.

• 단순히 문제 출제를 목적으로 문제를 출제하지 말자.
• 단순히 대회 개최를 목적으로 대회를 개최하지 말자.

물론 많은 사람들은 자신이 문제를 출제해 보고 싶다는 생각을 하고, 이는 어쩌면 당연한 것이다. 나는 문제를 출제하는 것이 잘못되었다고 말할 생각이 아니다. 단지 문제를 출제하고 싶다는 것이 가장 중요한 이유라면 안 된다는 것이다. 자신이 좋은 문제에 대한 아이디어가 떠올랐다거나, 그런 아이디어를 다른 사람들과 공유하고 싶다는 등의 동기가 아니라 별로 좋은 아이디어도 없는데 억지로 문제를 내게 되면 보통 결과물 역시 좋지 않게 나올 수밖에 없다. 이것은 대회 개최에서도 똑같다. 특히 대회의 경우, 한 문제라도 이상하게 출제되면 다른 문제들 역시 같이 피해를 볼 수 있다. (예를 들어 한 문제에서 오류가 있었는데 그 문제에 시간을 모두 쏟다가 다른 문제를 보지 못했다던지…)

또 하나 강조하고 싶은 것은 바로 문제의 난이도보다 문제의 질이 언제나 우선시되어야 한다는 것이다. 물론 난이도 커브가 급격히 상승하는 것은 모두에게 기분나쁜 일이다. 그러나 이것은 문제 난이도의 급상승으로 인해 가로막히는 사람들에게만 적용되기도 하고, 적어도 대회가 끝나고 문제 하나하나를 개별적으로 풀어보는 사람들에게는 적용되지 않는 문제이기에 후자보다 참작의 여지가 있다. 그러나 문제의 질이 나쁘면 그건 더 이상 변호가 힘들다. 특히 앞부분 문제에서 참가자가 "이 문제는 조금 별로인 것 같다"라는 인상을 받게 되면, 후반부 문제들을 보지도 않은 채로 대회 자체에 대한 평가가 나빠질 수 있다.

그러나 보통 대회에서 낮은 질의 문제가 출제되는 가장 흔한 원인은 억지로 어려운 문제를 만들다가 생기는 것 같다. 제발 억지로 어려운 문제를 만들지 말자. 이런 경우를 꽤 많이 봤는데, 주로 어떤 특정한 "사전지식"에 약간의 변형만을 가해서 출제되는 경우이다. 이런 경우 그 사전지식이 없는 사람은 몰라서 못 풀고, 사전지식을 아는 사람은 문제를 혹평하게 되는, 누구에게도 좋지 않은 결과가 나온다. 예를 들어 아래와 같은 문제를 생각해 보자.

• 길이 $N$의 순열 $A$가 주어진다. 이때 다음 두 가지 쿼리를 처리하시오.
  • 구간 $[l, r]$에서 LIS (최장 길이 증가 부분 수열)의 길이를 구한다.
  • 구간 $[l, r]$에서 LDS (최장 길이 감소 부분 수열)의 길이를 구한다.

만약 수열과 쿼리 42를 아는 사람이라면, 첫 번째 쿼리는 이 문제와 일치하고, 두 번째 쿼리는 단지 수열을 거꾸로 저장해 풀면 된다는 것을 매우 쉽게 알 수 있다. 이런 식으로 이미 존재하는 문제를 아주 살짝 꼬아 만든 문제가 대회에 출제되었을 때 좋은 문제라고 생각하는 사람은 아무도 없을 것이다. 예시가 너무 과장된 거 아니냐고 생각하시는 분들도 있을 수 있는데, 정말 저 정도급 문제들이 올라오는 것을 여러 번 봤다. 이런 걸 낼 바에는 그냥 어려운 문제 낼 공간을 쉬운 문제로 대체하는 것이 몇백 배 낫다. 다 된 밥에 굳이 재를 뿌리지 말자.

피해야 하는 예시

사실 이 부분이 굉장히 민감할 거라고 생각해서 작성이 쉽지 않았다. 직접적으로 어떤 문제의 예시를 드는 것이 출제자들에게 굉장히 실례일 것이라고 생각했기 때문이다. 그러나 글의 목적을 위해서라면 조금 더 직접적으로 쓰는 게 맞다고 생각했고, 조금 위험한 선택을 시도하게 되었다.

아래는 지금까지 내가 PS를 하면서 만나본, 내가 생각하기에 출제하지 말아야 하는 문제들의 유형이다. "좋은 문제가 아니다"라고 말하기는 조금 애매한 예시들도 포함되어 있다. "출제하지 말아야" 한다는 뜻이다. (아마 각 문제들에 대한 코멘트에서 내가 이야기하고자 하는 것이 무엇인지 파악할 수 있을 것이다.)

• 이미 존재하는, 잘 알려지지 않은 문제의 지나치게 사소한 변형임
  • 많은 수의 대회에서 어려운 문제를 내기 위해 사용되는 방식이다. Codeforces의 특정 라운드에서는 중국 OJ의 한 문제를 베껴서 출제했다가 걸린 일도 있었다. 이런 사례는 정말 문제를 그대로 가져다놓은 것이기 때문에 여기서 말하는 케이스랑은 조금 다르지만, 대회에 미치는 영향은 크게 다르지 않은 것 같다. 보통 출제자가 능력이 부족해 어려운 문제를 내기 힘들 때 자주 등장하는데, 이런 경우에 나는 어려운 문제를 출제할 칸에 쉬운 문제를 하나라도 더 출제하라고 권고하고 싶다. 항상 문제의 난이도보다는 문제의 질이 중요하다. 다 된 밥에 굳이 재를 뿌려 망칠 이유가 하나도 없다.
  • BOJ 19570. 삼각 분할: 이건 내가 출제한 문제인데 정확히 이 사례에 부합한다. 이 문제로 이야기를 시작해 보자. 이 문제를 출제한 동기는 만점을 방지하기 위함이었고, 이를 위해 적당한 문제를 생각하다가, 해당 문제를 FFT로 풀 수 있음을 발견하였다. 그러나 나중에 알고 보니 이러한 종류의 문제는 p-recursive 점화식의 일종으로 굉장히 잘 알려진 형태였고, 이런 문제를 접근해본 경험이 있다면 굉장히 쉽게 풀 수 있지만, 반대로 처음 보았다면 사실상 풀지 못할 유형이었을 것이다. 지금의 나라면 이러한 문제를 절대로 출제하지 않았을 것이지만, 당시 대회를 운영하면서 나에게 이러한 조언을 해 줄 검수진이 아무도 없었기에 이러한 문제가 그대로 나오게 되었다. 대회의 성격과 난이도에 전혀 맞지 않는 문제였고, 문제의 질마저 나쁘다. 앞서 말했듯이 이런 문제를 낼 자리에 쉽고 좋은 문제를 하나 더 출제하는 게 백 배 더 이득이다.
  • BOJ 25433. PLCS: 잘 알려진 문제인 LCS 6으로 환원하는 과정이 너무 쉽다. 대충 골드 정도 되는 것 같다. 이 말은 원래 루비5 문제들을 풀 줄 아는 입장에서는 사실상 똑같은 문제로 취급할 수 있다는 것이고, LCS 6 풀이를 모르면 못 푼다는 뜻이다. 나는 이 문제의 단점은 $N, M \le 50000$이라는 제한을 굳이 넣어서 문제를 어렵게 만들려고 시도한 것에서 일조한다고 생각한다. 그 부분만 없었다면 문제가 백 배 천 배 정도 좋았을 것이다. 그렇게 하면 LCS를 실제로 구하는 과정과 문제를 환원하는 과정의 난이도가 비슷해 재미있는 관찰 문제로 남았을지도 모른다. 대체 왜 이런 선택을 해서 문제를 나쁘게 만드는 것일까?
  • BOJ 31505. N진수 곱셈: FFT 알고리즘을 PS에 소개하는 문제 격인 큰 수 곱셈 (2)에 이상한 파싱을 추가한 문제이다. 그러나 FFT를 모르면 애초에 풀지도 못하고, FFT를 아는 사람들은 코드를 다 어딘가에서 복붙해 온 다음 파싱 부분만 열심히 짜고 있을 것이다. 이런 문제를 왜 출제했는지 궁금하다. 이 문제가 대회에서 무슨 역할을 하는가? 이 질문을 조금 깊이 생각해 봤으면 좋겠다.
  • BOJ 29257. 하늘의 타일링: 이 문제도 유명한 루비2 문제인 Domino Covering을 직사각형에서 원기둥으로 바꾸기만 한 문제이다. 내가 두 문제 풀이를 자세히 이해하고 있는 것은 아니지만 풀이 라인이 거의 같다고 들었고, 출제자들도 정해를 제대로 못 짜서 대회 당시 데이터에 오류가 있었다는 제보도 들었다. 대체 왜 이렇게까지 해서 문제를 출제하려고 하는 건지 도저히 알 길이 없다.
• 문제가 지나치게 사전 지식에 의존함, 그리고 그 사전 지식이 PS의 범주에 속한다고 보기 애매함
  • 바로 위의 케이스와 조금 느낌이 비슷하다. 사실상 같은 분류로 쳐도 무방하다. 그러나 위 케이스에는 넣기 조금 애매한 문제들이 있기 때문에 따로 새로운 분류를 만들었다. 여기서 내가 이야기하고 싶은 문제들은 흔히 말하는 수학 사전지식 문제들 같은 부류이다.
  • 그런데 자료구조 사전지식 문제랑 수학 사전지식 문제가 다른 게 뭐냐고 묻는 사람들이 있을 것 같다. 둘 다 모르면 못 푸는 것은 마찬가지인 건 맞다. 그런데 자료구조는 PS의 범주에 포함되는 반면, 많은 수학 사전지식 문제들은 그렇지가 않다. 이해를 돕기 위해, 유명한 문제인 총알의 속도를 보자. 이 문제는 PS에서 완전히 벗어난 범주인 물리학 영역에 속한다. 따라서 이 문제는 내가 설명하고자 하는 종류의 문제에 부합한다. 단지 이 문제가 그나마 재미있는 이유는 상대성 이론을 모르거나 이 문제가 상대성 이론과 관련이 있을 거라고 생각하는 사람들을 낚는 역할을 하기 때문이다. 그러나 이런 문제가 예를 들어 대회에 출제되었다고 생각해보자. 그 누구도 좋은 문제라는 이야기를 하지 않을 것이다. 나는 이러한 논리를 PS에서 별로 쓸 일 없는 수학 사전지식 문제들에게도 적용시키고자 하는 것이다.
  • BOJ Bundle in Math. Vol 1: 정말 최악 중의 최악이다. 일단 대회가 생성된 이유부터가 "문제 출제 권한이 없는 사람들이 기준을 회피하기 위해 더 낮은 대회 출제 권한을 이용하겠다"라는 것이었다. 뭐 그것도 좋은 문제라도 있으면 몰랐을까, 점점 대회 이름이 "매립지컵"으로 개편되면서 다른 대회에 못 낼 질 낮은 문제들만 모아놓는 쓰레기장이 되었다. 그리고 그 위대한 결과물을 보자. 이런 대회를 만들자고 결정하는 사고 방식을 이해할 수 없다. 애초에 다른 대회에 못 낼 문제라는걸 안다면 출제하지 말아야 하는 게 아닐까? 내가 떠올릴 수 있는 이 대회를 옹호하는 유일한 논리는 "신선하고 다양한 수학적 지식들을 많이 배울 수 있다"라는 것이다. 그런 논리에 동의할 만한 사람들은 아마 백준 말고 다른 수학 커뮤니티에 많을 것 같다.
    • 단순히 수학 문제들이라서 이렇게 이야기를 하는 것이 아니다. tag:math가 달린 문제들 중에서도 좋은 문제들은 얼마든지 있다. 그런데 그러한 문제들의 특징이라면 PS의 범주 안에 통용되는 수학 지식을 활용하거나, 적어도 PS에 영감이 될 만한 무언가를 보여준다는 것이다. 뜬금없이 리만 제타 함수 같은 이상한 함수를 들고 와서 "와, 이런 신기한 성질이 있어요" 같은 걸 하면 안 된다는 뜻이다.
  • 플로우컵: 평면기하를 주제로 하고 있는 대회이고, 아마 KMO 중등부 기하 수준에서 모든 문제가 풀리는 것으로 알고 있긴 하다. 그러나 여전히 문제 하나하나의 퀄리티는 옹호하기 어려운 수준이다. 이 사전지식을 아시나요? 그렇다면 저 사전지식은 아시나요? 수준인 것 같다.
• 문제의 풀이를 떠올리는 난이도에 비해 구현이 지나치게 복잡함
  • 첫 번째 케이스인, "이미 존재하지만 잘 알려지지 않은 문제의 사소한 변형"과 조금 겹치는 케이스이기도 한다. 이미 잘 알려진 문제에 뭔가를 추가하려면 가장 쉬운 것이 복잡한 구현을 추가하는 것이기 때문이다. 그러나 굳이 그런 케이스가 아니더라도, 문제의 난이도에 비해 구현이 지나치게 복잡한 경우가 있다. 이 경우는 따로 문제로 출제한다면 뭐 그나마 참작의 여지가 있지만, 시간이 제한되어 있는 대회에는 출제를 최대한 피해야 한다. 문제를 잡는 참가자들에게 불쾌한 경험을 줄 확률이 높기 때문이다.
  • BOJ 17081. RPG Extreme: 지금에야 구현 문제의 대표격 사례로 알려져 있지만, 이 문제도 사실 어느 대회에 출제된 문제라는 점을 떠올려 보면 정말 좋지 않은 케이스라고 할 수 있다. 대회에서 이러한 문제가 출제되었을 때 참가자들에게 어떤 선택지가 돌아가는지를 살펴볼 필요가 있다. 이 문제를 구현하는 데 많은 시간을 날리고 확정적으로(사실 그렇게 확정적도 아니다!) 100점을 짤 것인지, 아니면 이 문제를 무시하고 다른 문제를 선택할 것인지 하는 것이다. 대회 경험이 많은 사람들은 자신에게 맞는 판단을 잘 할 수 있겠지만, 구현이 약한 사람들은 이 문제에서 크게 말릴 확률이 높다. "어차피 사람들의 실력으로 인해 차이가 나는 건데 괜찮지 않냐"는 반론이 있을 수 있지만, 이런 경험은 참가자들에게 매우 부정적인 경험을 준다. 단순히 일반적인 문제 구현을 끝날 때까지 못한 경우에도 아쉬움이 남는데, 이런 식으로 대놓고 "구현을 얼마나 잘 하십니까?"식의 문제를 만나게 되면 오죽할까. 그렇다고 문제에서 배울 점이 있는 것도 아니다.
  • BOJ 21851. 육각형 영역: 다양한 방면으로 망한 문제이다. 문제의 풀이 아이디어 자체는 굉장히 신선하지만, 저 문제를 자력으로 해결하려면 IOI 2012 Ideal City에 대한 배경이 있어야 하기 때문에 사실상 사전지식이나 다름이 없다. 이런 사전지식을 안다면 문제 풀이를 떠올리는 데에는 채 5분이 걸리지 않을 것이다. 여기서부터 어느 정도 망한 문제라고 생각할 수 있다. 그러나 이 문제는 한 가지 단점이 더 있다. 바로 구현이다. 이상적인 도시 문제 티어가 D2인데, 육각형 영역의 예상 티어가 R4~R3일 정도로 구현이 복잡하다. 모델 코드가 11KB(350줄)일 정도로 구현이 복잡한데, 5시간 대회에서 풀라고 낸 문제가 맞는지도 의심이 된다. 심지어 이 긴 길이가 복잡한 자료구조 같은 데에서 오는 것이 아니라, 정말 신경쓰이는 off-by-one 처리를 하며 육각 격자 스위핑을 하는 데에서 발생한다. 사실 가장 문제인 것은 이 문제를 선정한 APIO Commitee라고 할 수 있겠다. 대체 이런 문제를 통과시킬 생각을 어떻게 했지?

이러한 상황을 피하는 방법

사실 대회를 처음 출제하는 사람들에게 어떤 문제가 좋은 문제인지 판단하는 것은 정말 어렵다. 의식적으로 좋은 문제를 만드려고 해도 쉽지 않다. 이것을 잘 알기 때문에 나는 이런 사태가 발생하는 이유를 출제진의 문제만으로 말하고 싶지는 않다. 분명 출제진들의 책임도 있지만, 이런 대회 문제들을 검수하는 검수진들에게도 조금의 책임이 있다고 말하고 싶다.

하지만 요즘의 대회 검수 시스템이 어떻게 작동하는지를 잘 알고 있기 때문에, 검수진 탓하기 매우 어렵다는 것을 알고 있다. 나는 일단 출제진들이 책임감 있는 검수진들을 뽑을 책임이 있다는 것을 말하고 싶다. 또한 검수진들 역시 문제 선정에 최소한의 의견을 표현할 권리가 있어야 한다고 생각한다. 대회에 어떤 문제들을 출제하는 게 좋고 어떤 문제를 출제하면 안되는지 나보다 더 잘 아는 경험 많은 검수진들이 많다. 그런 사람들이 "이 문제는 출제하면 안 될 것 같다"고 말했을 때, 출제진들이 따를 수 있어야 한다. (물론 검수진들이 최소한의 책임감이 없는 케이스도 정말 많고, 이것도 반드시 개선되어야 한다. 그러나 이런 경우는 애초에 문제 오류가 생기는 경우가 많고, 이러한 경우는 이 글에서 다루고자 하는 주제와는 다르다.)

Codeforces의 Coordinator 시스템을 보면 좋다. 예전에 어떤 라운드가 하나 있었는데, Coordinator가 출제진들이 제시한 문제를 30개 넘게 reject한 대회가 있었던 것 같다. 이 예시는 조금 극단적이긴 하지만, 어쨌든 대회의 질을 높이기 위한 노력이었다는 점에서 나는 매우 긍정적으로 생각한다. 현실적으로 30문제 이상 reject가 된 경우에는 대회가 정상적으로 열리기 어렵긴 하겠지만, 그래도 검수진들이 대회 문제의 질에 대한 의견을 내기 힘든 현재의 상황은 조금 개선되어야 한다고 생각한다. 이렇게 상황이 개선되고 나서야 대회 문제의 질에 대한 검수진의 책임에 대해 본격적으로 이야기하는 것도 가능할 것이다.

결론

이 글에서는 나의 문제 출제에 관한 철학을 설명했고, 내가 지금까지 출제한 문제들 중 일부를 되돌아보며 각각의 문제를 다시 평가해 보았다. 이 글은 모두 나의 개인적인 의견에 대한 이야기일 뿐이지만, 많은 사람들이 공감할 만한 내용도 일부 섞여 있다고 생각한다. 이 글의 내용이 여러분의 앞으로의 문제 출제나 대회 운영에 도움이 되었으면 좋겠다.

글이 너무 길어서 읽기 힘들었다면, 다음과 같이 짧게 정리해볼 수 있다.

• 언제나 문제 출제의 난이도보다는 문제 출제의 질이 우선되어야 한다.
  • 어려운 문제를 억지로 만들려고 하는 것보다는 쉽더라도 좋은 문제를 출제하는 것이 좋다.
  • 대회 문제의 풀이에 비해 구현이 지나치게 복잡한 것은 지양하는 것이 좋다.
• 문제 풀이는 사전지식보다는 수학적, 컴퓨팅적 사고력에 초점을 맞춰야 한다.
  • 통상적으로 PS의 범위 안에 들어온다고 생각되는 사전 지식은 괜찮지만, 이 범위 또한 참가 대상을 고려해 적절히 판단해야 한다.
  • 참가자들 중 극히 소수만이 알 것이라고 추정되는 사전 지식의 경우 출제를 지양해야 한다.
• 문제 출제 시 참가자가 대회에서 불쾌한 경험을 하지 않도록 최대한 노력해야 한다.