메아리 저널

11월 2일에 ACM ICPC Regional Contest - Seoul에 참가했다. 솔직히 대회 끝난지 1주일 다 되어 가는 마당에 글 쓰는 게 좀 우습기도 하지만 기록하는 셈 치고 남기기로 하겠다.

팀은 갑작스럽게 결성되었다. 처음 ACM ICPC에 나가자고 제안한 건 R모군이었다. 거기에 IRC에서 알고 지내던 V모님을 끌어 들여 완성된 팀이 문제의 ALLCHOL 팀인데, 갑작스럽게 결성되어서 준비도 안 하고 대회에 나갔기에 자조섞인 농담으로 낚시팀이라고 부르곤 했다. (그나마 3~6년 전에 경시대회에서 상 탄 경험이 있다는 게 다행일까...)

이 팀의 낚시성은 여기 저기서 찾아 볼 수 있는데, 예를 들어 폐회식에서 사회자가 팀 이름을 읽으려다가 어떻게 읽어야 할 지 몰라서 버벅이는 일이 일어 났다던지 하는 것들이다. (R모군은 "올철"이라고 읽는다고 주장한다. 뭐 내가 안 지었으니 상관 없지.) 온라인 예선에서도 다양한 뽀록(?)과 삽질(?)을 통해 교내 3위로 본선에 나가는 영광을 거머쥐었다. 물론 올라간 팀 수는 세 팀 — ALLCHOL, Cow Bessie, Farmer John — 이었지만.

예선 뒤에 본선을 위해서 준비를 한다고 하기는 했는데, 상황이 그다지 좋지는 않았다. 원래 교내에서 ACM ICPC 나가는 팀들이나 다른 사람들을 위해서 연습 세션을 금요일 저녁 7시부터 진행하기는 했는데, 두어번 해 본 뒤에 한 번 시간이 안 나서 못 하고 시험 기간 2주를 보내고 나니 그 다음 주가 대회였다. -_-;;;; 설상가상으로 R모군은 자전거를 타다가 공중 부양하는 덕분에 팔과 다리가 정상이 아니었으니, 낚시팀의 위력은 대단했다.

11월 1일 KTX를 타고 서울에 도착했다. 다행히도 R모군이 대회장 위치(백범기념관)를 제대로 기억하고 있어서 택시를 타고 가긴 갔는데 입구는 실제 건물에서 100미터 떨어져 있더라. 대회 등록 하고 연습 세션 해 보는 간단하다면 간단한 과정이었는데, 솔직히 별로 한 것도 없어서 긴장도 안 되고 그냥 그저 그런가보다 하는 기분이 들었다. 진행 요원으로 참가한 선배분을 만나서 열심히 수다도 떨었는데 농담으로 "종이는 뭐든 들고 갈 수 있다고 했는데 그럼 만화책 들고 가도 되나요" 하고 질문했더니 "꼭 들고 와라!"라는 대답을 해 주시는 센스. 지금 생각해 보니 진짜로 들고 갔으면 웃겼을 것 같다.

대회날을 위해 서울에서 잠을 자야 했기에, 왕십리에 있는 지인 F모님의 하숙방에 짐을 풀었다. 하숙방에 오고 나서 엑박 360을 하거나 하면서 놀다가 나가서 삼겹살 구워 먹고 오락실에 놀러 갔다가 (파픈뮤직 피버가 한국에 그렇게 많은지는 처음 알았다. 8의 자리를 14가 메꾸는 건가?) 돌아와서 다시 놀다가 밤 11시가 되어서야 준비를 시작했다. -_- 그 준비라는 것이 어차피 연습 같은 거 할 시간은 없으니까 대회때 볼 책들이나 프린트 정도 준비하고 좀 보고 가자는 것이었는데, 준비를 하다가 사람들이 다 뻗고 나서 자정이 넘어서야 대강 프린트를 완성할 수 있었다. (그 동안 V모님은 게임을 하고 계셨다. 어쩌라고?) 대회 전날에 참 잘도 한다고 생각하며 방에 아무렇게나 누워서 잘도 잤다.

대회는 2일 낮 10시에 시작되었다. 대회 시작되기 전에 들고 갈 책들을 확인하고 키보드를 체크했는데, 다른 팀에 비해서 두 배 정도 되는 책들을 가져 오는 걸 보고 진행 요원들이 황당해하는 걸 보니 뿌듯(?)했다. (물론 이 책들은 한 번도 안 보고 도로 가져 갔다. 공업수학과 확률통계 책은 왜 가져 갔는지 모르겠다.) 스폰서 문제로 무조건 전날 나눠 줬던 티셔츠를 입고 오라고 해서 잔뜩 껴 입었는데, 대회장에 들어 와 보니 그걸 고려한 모양인지 너무 난방을 잘 해 놓아서 목이 탔다.

문제는 열 문제였는데 처음 여섯 문제를 두 문제씩 나눠서 풀기로 하고 대강 문제를 살펴 본 뒤 코딩을 시작했고, 최종적으로는 대략 여덟 문제 정도 건들게 되었다. (다 풀었으면 월드 파이널 감이다...) 문제가 궁금하신 분들은 여기를 참고하시고, 문제별로 설명을 하자면:

• Problem A는 노가다 문제다. 처음에 정확도 문제 때문에 실패한 뒤 자바로 다시 짜서 해결.
• Problem B는 내가 안 풀어서 기억은 안 나는데 아마 동적 계획법이었던 것 같고, 시간 별로 안 쓰고 풀었다.
• Problem C는 귀찮아서 안 건들었다.
• Problem D는 노가다 문제인데 예외 처리가 쉽지 않아서 삽질을 많이 했다. 마지막에서 두 번째로 풀었는데, 계속 segfault가 나길래 범위 체크 실패하면 그냥 루프를 나가게 했더니 되더라는 안구에 습기차는 상황...
• Problem E는 동적 계획법이고, 수학적으로 점화식만 제대로 짜면 쉽게 풀 수 있는 문제였다. 점화식을 한 번 잘못 짜서 다시 짜느라 조금 머리를 썼다.
• Problem F는 linear 시간 안에 풀 수 있는 어렵지 않은 문제였지만 예외 상황이 너무 많고 정확도 문제도 겹쳐서 대회 끝까지 사투를 벌여 결국 풀었다. 이 얘기는 나중에.
• Problem G는 두 정규 언어의 교집합을 구하는 문제와 동일하며, 재귀적으로 정의해서 풀어도 되고 가능한 모든 문자열의 목록을 갖다가 테스트해도 된다. 그런데 문제 다 풀었는데도 PC²가 계속 틀렸다고 해서 결국 포기. 도대체 어떤 테스트에서 망한 건지 궁금하다.
• Problem H는 참가팀 중 아무도 풀지 못 한 궁극의 문제였는데, 대강의 알고리즘 구상은 있었지만 구현하는 데 시간이 너무 많이 걸릴 것 같아서 일찍 때려 쳤다. 문제 보고 뭐 이리 오토마타 관련된 게 많이 나오냐고 불평했음. (오토마타와 관계 없이 할 수도 있지만 본질적으로는 같으리라고 생각한다.)
• Problem I는 알고리즘은 안 어렵지만 구현이 귀찮아서 못 풀었다.
• Problem J는 R모군이 그리디로 짠다고 난리를 치다가 결국 쥐쥐를 쳤다. 그리디가 맞는지는 증명도 안 해 봤고 깊이 생각도 안 해 봐서 모르겠다.

그래서 총 다섯 문제 풀었다. 푼 순서는 대략 B, A, E, D, F 순서였는데, D를 대회 끝나기 20분 전에 풀고 F를 대회 끝나기 40초 전에 풀었기 때문에 순전히 뽀록에 가까웠다. F의 경우 알고리즘은 안 틀린데 정확도 때문에 계속 뻑 나서 마지막에 0.0001씩 좌표를 이동시켜서 테스트해 본 결과 네 가지 가능한 케이스 중 한 가지가 극적으로 통과해서 살아났다. -_-;;;;;

대회는 오후 3시에 끝났다. 최종 결과가 나오는 5시까지 시간을 때우기 위해서 여러 다양한 의미 없는 일들을 했는데, 사람들이 특히 주목했던 것은 각 팀 별로 몇 문제나 풀었는지 보여 주는 풍선을 모아다가 별 희한한 일을 하는 것이었다. 어떤 사람은 풍선 수십개를 직렬로 연결해서 높이 띄우기도 했고, 어떤 사람은 진행 요원들이 모아 놓은 풍선 무더기를 가져다가 사진도 찍고... 하다가 실수로 천장에 날려 버렸다. (이 풍선 무더기는 십여분 후에 각고의 노력에도 불구하고 하늘 멀리 날아가 버렸다. 날아가는 게 꼭 UFO같더라.)

대회가 끝나기 전에 매달려 있던 풍선의 수를 토대로 우리 팀이 12위라고 생각했는데, 발표 결과를 보니 한 팀이 실격하여 최종적으로는 11위가 되었다. 상을 받는 팀은 12개였는데 R모군이 한 학교에서 가장 잘 한 팀한테만 상을 준다고 해서 에라 모르겠다 하고 있었는데, 알고 보니 학교 별로 가장 잘 한 10팀을 뽑고 나머지 팀 중에서 학교 별로 가장 잘 한 두 팀을 다시 뽑아서 스폰서인 NHN에서 특별상을 준다고 한다. 우리 팀은 카이스트 팀 중에서 2등이었고, 우리보다 잘 하고 상을 못 탄 팀은 서울대 두 팀 뿐이어서(서울대 3등 한 팀은 진짜로 안습...) 졸지에 상을 타게 되었다. 낚시팀이 정말로 낚시에 성공한 셈이었다. -_-; 흥미로운 점은 두 팀이 각각 Problem F(NHN 이름 나온)를 각각 맨 처음과 맨 마지막으로 풀었다는 것이겠지.

폐회식이 끝나고 저녁식사를 했는데 한 번 음식을 받아 가고 나서 다시 받으러 가니 음식의 대부분이 사라져 있더라. 결국 배터지게 먹으려는 목표는 달성 못 하고 적절히 먹고 적절히 다른 사람들이랑 얘기하다가 집에 갔다. 준비도 안 하고 나름대로 상도 받아서 용하기는 한데, 대회 자체는 꽤 재밌었고 추억거리가 많았다. 앞으로 이런 대회에 다시 나가게 된다면 좀 제대로 준비해 보는 것도 나쁘진 않을 것 같다. (그리고 그 때는 반드시 팀 이름을 낚시팀으로 하고 말겠다...)