제1회 와쿠컵 출제 후기

넣을 사진이 없다. 내 사진이나 넣어야지

 

 어쩌다가 제1회 와쿠컵으로 출제 데뷔전을 치르게 되었습니다. 그런데 제1회 와쿠컵에 거의 600명이나 되는 사람들이 몰리면서 지금 상당히 부담스러워 하고 있습니다. 이번 와쿠컵에서

• K. I LOVE JavaScript
• O. 지연 평가

 이렇게 두 문제를 출제하게 되었습니다. 사실 5문제 정도를 만들었는데 가장 난이도가 낮고 퀄리티가 높다고 생각한 두 문제를 뽑았습니다.

 

 O. 지연 평가

 이 문제를 첫 번째로 만들었습니다. 아마 5문제 중에 3번째로 만든 문제였던 것 같은데 둘 다 골드 넘어갈 것 같아서 그냥 혼자서 버리기로 결정했습니다. 그렇게 해서 만든 문제가 이 문제였는데 사실 이 문제도 골드를 갈 뻔했습니다. 버전이 총 3개가 있었는데 세상에 나온 버전은  그중에 가장 쉬운 버전이었습니다. 처음에 출제진들은 이 문제를 실버 3(?)이라고 평가했는데, 나도 실버 3일 줄 알았습니다. 검수진 분들은 실버 1과 골드 5 사이로 평가하셨는데(이렇게 되면 출제 가능한 난이도 선 끝자락에 걸친 거임), 어떻게 보면 제가 가장 쉬운 버전을 고른 게 신의 한 수였던 셈입니다.

 

 문제를 만든 계기는... 누가 파이썬에서 sqrt 안 쓰고 O(sqrt(N)) 소수 판정 어떻게 하냐고 물어봐서입니다. 즉 다음 코드가 O(N)이 아니냐고 물어본 사람이 있었습니다.

def is_prime(n: int):
    for i in range(2, n):
        if n % i == 0:
            return False
        if i * i > n:
            break
    return True

 근데 range 객체는 어차피 O(N)개의 수를 다 만드는 것이 아니기 때문에 이 코드는 O(sqrt(N))이 맞습니다. (검증하고 싶으면 p = 1234567891 넣어 보세요... 소수임) 이걸 계기로 이 사실을 널리 알리기 위해 문제를 만들어야겠다고 생각했습니다.

 문제 자체는 만들고 나서 나름 만족스러웠는데, 힌트를 만드는 게 좀 걸렸습니다. 오답 풀이로 O(1/4 Q^2) 풀이가 존재하는데, 실제로 모든 쿼리를 array에 다 저장했다가 꺼내서 푸는 풀이가 O(1/4 Q^2) 풀이입니다. 이 풀이가 생각보다 많이 등장해서 대회 중에도 30명 이상이 시간 초과를 받았습니다. 저와 검수진 분들은 이 풀이의 존재를 알고 있었지만 저는 힌트를 통해 이 풀이를 하지 않도록 유도하는 방법을 찾지 못했습니다. 사실 그렇게 유도하는 게 맞는 일인지도 모르겠습니다. 아무래도 대회 문제니 최소한의 힌트만 주어야죠... 그와 별개로 range 객체처럼 start, step을 들고 있는 풀이 말고도 정해가 하나 더 존재하는데, 그 정해도 어차피 lazy eval 쓰는 건 마찬가지라(정확히는 map과 map 사이에서 즉시 평가, map과 원본 배열 사이에서 lazy eval) 별 문제가 안 된다고 생각했었습니다. 근데 의외로(?) 힌트를 보고 "넌 반드시 start, stop, step을 들고 문제를 풀어야 해"라고 느끼신 분들이 있는 듯...

 

 주어지는 쿼리는 함수형 프로그래밍에서 기초적으로 자주 쓰이는 연산들입니다. 0, 1은 map 연산이고, 2는 drop 연산입니다. 주어지는 배열(지연이가 갖고 있는 1,234,567,890,123개의 수가 담긴 배열) 역시 lazy evaluation으로 할 수 있는 가장 강력하면서도 간단한 예시 중 하나, 무한 수열 객체입니다. (보통 함수형 프로그래밍 소개하는 책에서 lazy evaluation 설명하면서 같이 설명합니다. "함수형 프로그래밍에서는 무한수열도 생성할 수 있다" 그러면 뽕이 차오름...) 그러니까 힌트는 "무한 수열 생성기와 비슷한 객체를 님이 한 번 구현해 보세요" << 이 뜻이었는데, 생각보다 힌트를 제 의도와 다르게 해석한 사람이 많아서 아쉬웠습니다. 사실 애초에 함수형 프로그래밍이라는 개념과 PS가 잘 안 맞았던 걸지도?

 

 K. I LOVE JavaScript

 이거 만들 당시 문제가 한 10개 정도 만들어져 있던 걸로 기억하는데 당시 구현 문제가 부족했습니다. 그래서 제가 만들었습니다. 사실 구현 문제도 제가 2개를 만들어 놨었는데 하나는 하위호환 문제가 실버1인 걸로 밝혀져서 그냥 버렸고, 이걸 들고 왔습니다. 근데 버린 그 문제는 진짜 쌩 구현이라 이 컵에 갖고 오기 굉장히 좋은 문제였던 것 같은데 너무 아쉽습니다. 

 근데 사실 이 문제도 한 번 너프를 먹었습니다. 사실 원래는 ASON 객체가 이런 식으로 주어졌습니다.

[1, [2, 3], foo, [7, bar], [], [[]]]

 즉 현실의 array 표현과 훨씬 가까웠습니다. 근데 출제진 내부 난이도 평가는 괜찮았는데, 검수진 난이도 평가에서 파싱이 너무 까다롭다고 골4까지 갈 위험에 처하면서 급하게 표현을 수정했습니다. 근데 원래 Validator가 DFA Lexer + SLR(1) Parser로 구현된 400줄 가량의 코드였어서, 지금도 Validator가 상당히 거대합니다. 하지만 괜찮습니다. 만드는 게 재밌었으니까요... 별개로 Generator도 재밌게 만들었습니다. Generator를 구현할 때는 Rust의 Enum을 쓰면 좋을 것 같은데 아무래도 Generator는 C++로 만드는 것이 국룰이었으므로, std::variant를 배웠습니다. 이것도 재밌더라고요...

 

 이 문제는 일단 파싱만 제대로 하면 그 이후에는 스택, 애드혹 등 다양한 풀이가 있는데 어느 풀이를 쓰든 별로 신경을 안 썼고 심지어O(N^2) 구현도 통과시켜 주었습니다. 왜냐하면 전 원래 이 문제의 본질이 구현이라고 생각했기 때문에... 실제로 이 문제가 15문제 중 대략 10번째로 출제된 문제였던 걸로 기억하는데, 그때까지 와쿠컵에서 구현을 맡고 있는 문제가 별로 없었습니다. 그래서 대놓고 구현 문제를 노리고 만든 게 K번이지만, 조건 분기가 2중 3중으로 까다롭게 나뉘는 것도 아니었고, 그 때문에 정답률도 상당히 높게 나와서 구현 실력이 부족하다고 K번을 못 푼다거나 그런 일이 있지는 않았을 것 같네요.

 

 구현 주제는 제가 좋아하는 JSON 포맷으로 골랐습니다. 하지만 정작 자바스크립트 자체는 싫어한다는 게 함정. 저는 늘 구현 문제를 낸다면 컴공 주요 과목에서 중요하게 여기는 것들을 구현 문제로 내 보고 싶다는 생각을 갖고 있었는데, 그러기엔 사실 제가 컴공이라는 필드에 들어온 지 2년도 되지 않았기 때문에 지식이 그렇게 많지는 않네요. 다음에는 그래픽스 관련 문제를 내고 싶다는 꿈이 있습니다...

 

 여담

 1. 대회의 권위를 높이기 위해(?) 코드포스 블루를 찍었습니다.

 이것은 그냥 전적으로 대회의 권위를 높이기 위해서(?)이며, 이렇게 해서 저는 출제자 권한 3신기(1000솔브 / 코포 블루 / ICPC regional 30등)를 모두 모으게 되었지만 검수자 권한은 하나도 따지 못했다는 안타까운 현실이 있습니다. 이것이 바로 '재능의 벽'이라는 것...

 

 2. 사람들이 생각보다 예제에 관심이 많더라

이거 디스코드 채널에서 언급되길래 깜짝 놀랐음...

 

팬아트(???)도 받았음

 3. 전 isdigit() 함수/메서드의 존재를 K번 문제 첫 검수자님의 코드를 받고서야 알았습니다.

 

 사실 이렇게 후기를 대충 적었지만, 출제/검수는 정말 힘든 일입니다. 여러분은 출제/검수로 먹고사는 일을 꿈꾸지는 마셨으면 합니다. 어차피 이게 다 깃허브 프로필에 한 줄 남기기 위해 하는 일 아니겠습니까? 물론 재밌어서 하는 일이기도 합니다. 저는 와쿠컵 다음날이 현대대수학 시험 날이었는데, 사실 대회 시간 5시간 중 1시간만 컴퓨터 앞에 앉아 있고 나머지 시간에는 현대대수학 시험을 공부하려고 했는데 스코어보드 보는 게 너무 재밌더라고요... 5시간 + 반응 구경하는 2시간을 풀로 날려먹었습니다. 이것이 2달 반 동안 개고생한 결과라도 충분히 가치있는 일이니까 기회가 생긴다면 꼭 해 보시길 바랍니다. 그리고 다행히도 현대대수학을 제외한 모든 시험을 잘 봤습니다.

 내가 아무리 다이아2라고 하더라도 대회가 끝나고 나면 남는 것은 세팅에 대한 아쉬움밖에 없다는 사실이 상당히 슬프지만 어쩌겠습니까 그래도 100명 가까이 되는 사람이 실시간으로 솔브를 했고 관심이 있는 사람이 많았으니~~

와쿠컵과 상관은 없지만 빈틈을 타서 제 시집 좀 홍보하겠습니다. 감사합니다.