ACM ICPC 참가 후기 (이현섭 작성)

2009년 ACM ICPC 서울 지역 예선에서 우리 학교가 1등을 했다.  프로그램 경진대회가 없던 시절 대학을 다녔던 나로써는 얼마나 힘들고 치열한 경기일지 상상만 해 볼 따름인데, 이번 행사에는 참가했던 학생 중 하나가 현장상황을 생생하게 기록하였다.  대회에 한 번도 가보지 못한 나에게는 이 생생한 현장리포트가 우리 학교가 1등했다는 사실을 빼고라도 무척 재미있었기에 올린다.

[제9회 대학생 프로그래밍 경시대회]카이스트 6년 만에 정상

KAIST 전산과 박사과정 이현섭 작성

2003년 이후 처음으로 카이스트에서 가져가는 우승이었다. 지난 주 목, 금(11월 5일-6일) 백범김구기념관에서 열린 제9회 대학생 프로그래밍 경시대회(행안부 주최)에서 KAIST의 Nondeterminist 팀이 같은 학교의 RoyalRoader 팀, 서울대학교의 rand() 팀, 홍콩과학기술대학교(Hong Kong University of Science & Technology)의 HKUST_Optimus Prime 팀과 접전을 벌인 끝에 대회 종료 10분을 남겨두고 극적인 역전 드라마를 만들어냈다.

대학생 프로그래밍 경시대회는 3명의 학생이 한 팀이 되어 5시간 동안 주어진 문제를 해결하는 방식으로 진행되며 보다 많은 문제를 빠른 시간에 해결하면 높은 점수를 얻게 되며 한 번씩 틀릴 때 다시 제출할 수 있지만 페널티를 얻게 된다.

출발은 카이스트의 RoyalRoader 팀이 순조로웠다. 시작 30분 만에 문제 A, D, B를 차례로 감점 없이 해결하며 다른 팀들을 따돌리며 여유롭게 선두를 유지했다. RoyalRoader 팀은 1학년 새내기2명과 2학년 1명으로 이루어진 팀이라 초반 강세는 더욱 놀라웠다. 그 후 2시간 13분 만에 4문제를 더 풀어 총 7문제를 해결하면서 Royalroader 팀이 쉽게 우승하나 싶었다. 이 시각에 Nondeterminist 팀은 3문제, rand() 팀은 4문제, HKUST_Optimus Prime 팀은 5문제를 해결한 상태였다.

하지만 어려운 문제 F, G, J에서 각 팀의 운명이 갈렸다. 셋 중 그나마 간단한 문제 F의 경우 꼼꼼하게 따지면 해결할 수 있으며 프로그램 코드의 길이도 길지 않아도 되었다. 문제가 간단해 보여서였을까? rand() 팀은 대회 초반부터 문제 F를 공략하면서 거의 3시간을 써 가면서 네 팀 중 가장 먼저 문제 F를 해결했다. 이 문제는 후원사인 NHN㈜의 특별 문제로 특별상이 걸려있었다. 하지만 문제 F를 가장 먼저 해결한 것은 같은 서울대학교의 srand() 팀. 문제 G의 경우는 전공 지식이 요구되는 문제였는데 1학년과 2학년으로 구성된 RoyalRoader 팀에게는 조금 무리였는지도 모른다. 3시간 만에 8문제를 해결하고 2 시간 동안 문제 G를 공략했으나 9번이나 틀리면서 주저앉고 말았다. 대회 종료 페널티가 739점으로 비교적 낮았던 RoyalRoader 팀이 문제 G를 해결하기만 했어도 우승할 수 있었기에 대회 종료 직전까지 우승 팀을 가늠할 수 없었다.

대회 종료 30분 전 상황은 1위: RoyalRoader 팀 8 문제(1시간 30분 동안 8문제로 머물러있었다), 2위: Nondeterminist 팀 8문제, 3위:rand() 팀 7문제. RoyalRoader 팀이 1시간 30분 동안 문제 G를 공략하고 있었기에 조만간 문제 G를 해결하면 RoyalRoader 팀이 우승하게 될 것 같은 분위기였다. 하지만 rand() 팀이 대회 종료 23분을 앞두고 F 번을 해결하면서 1~3등 팀이 모두 8 문제로 페널티 계산에 의해서 rand() 팀이 1위, RoyalRoader 팀이 2위, Nondeterminist 팀이 3위가 되었다. 어느 팀이라도 한 문제를 더 풀게 되면 1등이 되는 상황. rand() 팀에게 남은 문제는 문제 G, J. RoyalRoader 는 2시간 동안 문제 G에 발목이 잡혀서 다른 팀들에게 추월을 허용한 꼴이 되었다. Nondeterminist 팀에게 남은 것은 문제 F와 J. 시간이 얼마 남지 않은 상황에서 긴장감을 갖고 지켜보는 가운데 rand() 팀이 종료 16분을 남겨두고 문제 J를 해결하면서 세 팀 중 먼저 9 문제를 해결했다. 이제 남은 것은 G번. G번은 시간을 요구하는 문제라 9문제로 대회를 마쳐야 할 상황. 페널티를 계산해 보면 RoyalRoader 팀, Nondeterminist 팀 두 팀 중 어느 팀이라도 한 문제를 더 풀게 되면 1위 자리를 내주어야 하는 상황. 팀 이름 그 대로 Nondeterminist 팀이 대회 종료 10분을 앞두고 문제 F를 해결하면서 rand() 팀과 함께 9 문제를 해결하고 단숨에 3위에서 1위로 올라선다. 경기 초반 비교적 문제를 천천히 풀었지만 꼼꼼하게 문제를 해결해서 세 팀중 틀린 횟수가 가장 적어 페널티 관리가 된 덕이다. 남은 시간 10분. 2시간째 문제 G를 공략하고 있는 RoyalRoader 팀의 경우 해결하기만 하면 페널티 계산에 의해서 우승할 수 있는 상황이었다. 하지만 어린 1학년 학생들에게는 허락되지 않았으며 RoyalRoader 팀은 내년을 기약할 수 밖에 없었다.

KAIST의 Nondeterminist 팀이 우승함으로써 서울대학교의 4년 연속 우승을 저지했다. 이 대회는 ACM-ICPC(Association for Computing Machinery-International Collegiate Programming Contest) 아시아 서울 지역 예선을 겸하고 있어서 우승팀은 내년 2월 중국 하얼빈에서 열리는 세계 대회에 진출하게 된다. 지난 11월 1일 인도 Amritapuri 지역에서 우승을 차지한 서강대학교 Oasis 팀에 이어 KAIST의 Nondeterminist 팀의 세계 대회 진출이 확정된 것이다. 서강대학교 Oasis 팀은 제9회 대학생 프로그래밍 경시대회에 SNSD 팀으로 참가해 6 문제를 해결해서 7위에 입상했다. SNSD 팀은 이미 세계 대회 진출권을 확보해서였을까? 대회 시작과 동시에 어려운 문제를 먼저 해결하는 여유를 보여주기도 했다(패널티 계산 때문에 쉬운 문제를 빨리 해결하는 것이 유리하다).

대학생 프로그래밍 경시대회는 매년 9월경 온라인 예선을 거쳐 65-70 팀을 선발하여 외국팀 5팀 내외를 초청하여 11월 초에 본선을 갖는다. 올해 60개 학교에서 397팀이 참가하여 70개 국내 팀과 외국 5팀이 본선에서 실력을 겨루었다.

 

대회 공식 홈페이지: http://acm.kaist.ac.kr

대회 문제: http://acm.kaist.ac.kr/forum/viewtopic.php?t=1389

대회 결과: http://acm.kaist.ac.kr/forum/viewtopic.php?t=1394

대회 감독: 좌경룡 KAIST 전산학과 교수