제1회 소프트콘 개최 후기

* 이 글은 해당 대회 문제의 풀이에 대한 스포일러를 포함하고 있습니다.

2회 대회도 개최한지 몇 달은 넘게 지났는데 이제서야 후기를 쓰는게 좀 우습기도 하지만, 대회 개최 하면서 느꼈던 점에 대한 걸 좀 정리해두고 싶어서 그냥 1,2회 다 글을 쓰려고 한다.

소프트콘은 뭔가 마음 편하게 참여할 수 있으면서 문제가 재밌는 그런 대회를 꾸준히 열고 싶은 생각에 개최를 하게 됐다. 이 대회는 내가 직접 개최하는 만큼 철저하게 내 취향에 맞는 문제로 구성하고 싶었다. 내 문제 취향은 꽤 명확한데 요약하자면 다음과 같다.

1. 수학적인 문제보다는 컴퓨터적인 구조나 사고방식을 요하는 문제

2. 어려운 알고리즘, 자료구조에 대한 사전 지식이 필요 없는 문제

3. 그 문제만이 갖고 있는 고유한 성질에 대한 관찰이 많이 필요한 문제

 그래서 소프트콘은 위 세 가지를 만족하는 문제를 위주로 내려고 노력했다. 또, 코드포스 기준으로 블루~퍼플 정도 레이팅의 유저에게 흥미롭고 도움이 되는 문제로 구성하는게 목표였다(그래서 오렌지, 레드 이상의 상위권에게 흥미로운 문제인지 여부는 별로 중요하게 생각하지 않았다).

1회 대회는 문제는 전반적으로 좋았다고 생각하지만 난이도가 첫 문제부터 너무 어려웠던 것 같다. 대회가 시작하고 나서야 출제자들은 자신이 만든 문제의 난이도를 과소평가하는 경향이 있다는 것을 뼈저리게 깨달았다.

아래는 각 문제 출제에 대한 간단한 후기.

대회에 출제된 문제 전체 목록은 다음 링크에서 확인할 수 있다.

- 문제 목록: https://www.acmicpc.net/category/detail/1843

A. 부당한 퍼즐

내가 출제한 문제인데, 고등학교때 동아리에서 학생들 상대로 이 문제의 거꾸로 된 버전을 낸 적이 있었다. 즉, 수열이 주어지고, 뒤집기 / 밀기 연산들이 주어졌을 때 그걸 수행한 결과를 출력하는 문제. 문제 만들려고 이것저것 고민하다 우연히 이 옛날에 낸 문제를 발견하고, 반대로 접근하면 재밌지 않을까 생각해서 만들었다.

나는 div2 B 정도 문제라고 생각하고 만들었고, 그래서 A번으로 적당하다고 생각했는데 막상 대회때 풀린 숫자를 보니 div2 C 정도 난이도였던 것 같다. KMP로 푸신 분이 꽤 있었다는 것도 신기했다. 

B. K - 균등 문자열

onjo0127님이 출제하신 문제.  디스크립션에서 이해하는데 어려움을 겪은 분들이 좀 많이 계셨다. 지문에 대한 검수를 좀 더 빡빡하게 하고 이해하기 쉬운 지문을 쓰는 것에 더 신경을 쓸 걸 그랬다는 후회가 좀 들었다. 좋은 문제인데 지문 때문에 인상이 나빠진 것 같아서..

언뜻 보면 그래프 문제인 것 같지 않은데 그래프로 환원해서 풀어야 하고 아이디어를 떠올리면 구현이 그렇게 어렵지 않다는 점에서 상당히 재밌고 좋은 문제였다.

C. 레벨 배치하기

내가 출제한 문제. 처음에는 '파라메트릭 서치를 하는데 파라메트릭 서치의 결정 함수도 파라메트릭 서치인 문제'를 만들어 보자 라는 생각에서 출발했었다. 하지만 문제를 만드는 과정에서 어느새 문제의 원형은 온데간데 없이 사라졌고... 원래의 생각과는 그냥 전혀 상관 없는 문제가 되었다. 결과적으로 만든 문제는 꽤 괜찮았던 것 같아서 만족. 하지만 이 문제 역시 B번처럼 디스크립션에 대한 고민이 부족했었기 때문에 조건을 정확히 이해하는게 까다로운 문제가 되어버린 점이 조금 아쉽다.

D. 프로그래밍 대결

onjo0127님이 출제하신 문제. 이 문제는 문제의 풀이에 쓰이는 알고리즘이 뭔지를 알면 의외로 쉬운데 그걸 모르면 또 상당히 어렵다. 그래서 난이도 판단을 좀 잘못한 것 같다는 생각이 든다. 이 문제가 E나 F번에 배치되었어야 하지 않았을까. 

 원래 나는 이 문제를 접하기 전까지 이 문제의 풀이 알고리즘을 아예 모르는 상황이었는데 문제 검수하면서 온조님 덕분에 새로운 알고리즘도 하나 배우게 되었다. 하지만 조금 아쉬운 점은 이 문제의 풀이가 어느 정도 '고급 지식'에 속하는 범주인 것 같아 처음 의도한 소프트콘의 방향과 살짝 어울리지 않는 부분이 있는 것. 문제는 개인적으로 정말 좋다고 생각한다.

E. 아름다운 퍼즐 만들기

smu201111192이 출제하신 문제. bitmask DP 문제에서 볼 수 있는 각종 테크닉을 때려박으면 풀 수 있는 문제다. bitmask DP 연습 문제로는 상당히 좋다고 생각하는데, 역시나 원래 생각했던 소프트콘의 방향성과는 조금 거리가 있지 않았나 싶다. 이런 테크닉들은 아는 사람은 좀 쉽게 풀고 모르는 사람에게 아주 흥미로운 성질을 가진 종류의 문제는 아니기 때문이다.

F. 정원사

 onjo0127님이 출제하신 문제. 검수 과정에서 한참동안 고민했지만 풀이를 떠올리지 못해서 결국 온조님에게 풀이를 듣고 나서야 풀었다. 풀이를 듣고도 이해하고 구현하는데 상당히 오랜 시간이 걸렸었다.

 세그먼트 트리를 이용해야 하는 쿼리 문제에서 조건이 두 가지 이상이면 단순한 방법으로는 해결하기가 꽤 힘든데, 이럴 때 접근 가능한 방법에 대해서 상당히 많이 배웠다.

 한 가지 아쉬운 점은 출제 및 검수 과정에서는 쿼리를 온라인으로 처리하는 방법에 대해 누구도 떠올리지 못했는데, 정해로 생각한 오프라인으로 처리하는 풀이보다 더 쉬우면서도 온라인으로 처리가 가능한 풀이가 있었다.

G. 연산 최적화

내가 출제한 문제고, 개인적으로 여태껏 출제한 문제들 중에서 가장 마음에 드는 문제다. 처음에 이 문제의 시작은 어떤 무한한 길이의 문자열에 대해서 특정한 구간의 패턴 등을 찾는 문제를 만들어보면 어떨까 하는 것이었다. 이 원래의 발상에서 꽤 오래 고민을 하다가, 이 문제에서 나온 3종류의 연산(0 추가, 1 추가, 지금까지 만들어진 문자열과 동일한 문자열 추가)을 떠올렸다.

그 다음에 이 연산들만 가지고 주어진 문자열을 만들 때 가능한 최소 길이를 구하여라. 라는 문제를 생각했는데, 이건 마지막 문제로 쓰기엔 좀 쉽다는 생각이 들었다. 그래서 조금 더 꼬아볼 생각으로 연산들을 합쳐서 새로운 연산 F를 만들고, 이 연산을 두 번 적용해서 주어진 문자열을 만들 수 있는 연산 F를 찾는 것으로 문제를 바꿔봤는데, 이렇게 바꾸니 문제의 난이도가 훨씬 상승했다.

 이 건 분명히 쉽게 풀 수 있는 규칙성이나 성질이 있을 것이라는 감이 들었고, 이 걸 고민하는데 거의 한 달 정도의 시간을 보냈던 것 같다. 문제에서 중요한 포인트가 두 가지 정도 있는데 둘 다 해결법을 떠올리기가 꽤 힘들었다. 어쨌든 풀이를 처음 떠올렸을 때 정말 기분이 좋았고, 문제를 출제하는 과정이 가장 재밌었던 문제였다.

 이 문제는 해결하기 위해서 단계를 둘 혹은 셋 정도로 나눠서 봐야하는데 그 각각의 과정에서 쓸 수 있는 방법이 내가 생각한 것 외에도 상당히 다양하다는 것이 재밌었다. 출제 과정, 대회에서 사람들이 이 문제를 푸는 방법을 보는 과정 모두가 다 정말 재밌고 유익했던 문제.

 대회 끝나고 아쉬웠던 점은 내 풀이보다 훨씬 좋은 풀이가 있었다는 것, 그리고 그 걸 한 달이나 고민하고도 떠올리지 못 했다는 것. 

대회가 끝나고 나서 느꼈던 아쉬움들은 요약하자면 다음과 같다.

1. 디스크립션에 대한 고민이 부족했던 부분

2. 더 좋은 풀이 혹은 문제에 사용할 수 있는 다른 접근 방법에 대한 고려가 부족했던 것

3. 문제들이 내가 생각했던 대회 문제의 기준에 완벽히 부합하지는 않았던 것

4. 문제가 생각했던 것보다 전반적으로 어려웠던 것(참가자 92명 중에 2문제 이상 푼 사람이 19명뿐이라는 건...)

 처음으로 대회를 개최했던 것 치고는 크게 문제 없었던 것 같아 다행이지만 정리하고 보니 아쉬운 점도 많았던 것 같다. 대회를 열고 준비하는게 대회에 참가하는 것 못지 않게 엄청 많은 공부가 된다는 것을 느낀 시간이었다.