10회 대학생 프로그래밍 경시대회 치루고~

출처 : http://acm.kaist.ac.kr/2010/photo/contest/Photo1.html

지난 10월 30일, KAIST ICC 에서 열렸던 10회 대학생 프로그래밍 경시대회(겸 ACM-ICPC Daejeon Regional)에 참가 했다. 2006년도 대회에 참가하고 이번이 두번째 참가.

2006년도 여름방학이 시작하기 전에 학교에 붙어있던 포스터를 통해 "대학생 프로그래밍 경시대회" 라는것을 알게 되었다. 당시 "씨앗" 이라는 학술 소모임을 만들어 운영하고 있었기 때문에 과 게시판에 공지를 했고, 그래서 모인 인원은 12명. 룰 대로 라면 4팀은 나갈 수 있는 인원이였지만 미숙하고 (부끄러운 이야기지만 이때는 로봇 체점사이트의 존재도 몰랐다. 문제는 어찌 구했는데 예제 입출력과 직접 만든 허술한 테스트 케이스에서 제대로 나오면 풀었다고 여기고 연습을 했다) 무리한 스터디 운영으로 인해서 대회 접수 당일에는 3명으로 줄어 들었다.  그 중 한명 마져도 대회에 나가지 않겠다고 하는것을 인원이 부족하면 참가가 안되니 설득하여 등록시켜 대회를 치루었다. 다행히 인터넷 예선에서 쿼터제 덕분에 가까스로 서울대회에 갈 수 있게 되었고, 대회에서는 5시간동안 2문제만 풀고 Honorable Mention에 그쳤다.

당시 대회가 끝나고는 조금만 더 연습하면 수상을 할 수 있을 꺼 같다는 생각을 했다. 우리팀처럼 2문제를 풀다가 마지막에 한문제 더 풀어서 동상을 수상한 모 대학을 보고 말이다. 하지만 그 한 문제 벽의 높이가 얼마나 높을지는 전혀 몰랐지 =_=;

2007년도 대회에 나갈 생각을 하고 있었으나 06년 말에 운 좋게 산업기능요원으로 복무를 하게 되어서 군대는 가고 싶지 않았기에 다른거 다 뒤로하고 떠나느라 4년이 지난 이번에 대회를 참가할 수 있었다.

그간 나름대로 연습을 했다. 복학을 해서 이 대회에 다시 참가 했을 때 수상을 할 수 있을만한 실력을 만들고 싶었다. 안타깝지만 우리학교에서 이 대회 준비를 할 만한 사람을 찾기는 어렵기 때문에 혼자 수상 가능할 정도의 실력을 쌓지 않으면 안된다고 생각을 했다. 하지만 어떻게 공부를 해야 하는지 방법을 몰랐고, 회사 다니면서 가끔식 문제를 풀어보았지만 두서없이 이것저것 건들여보기만 할 뿐 실제적인 실력이 나아진다는 느낌이 드는건 별로 없었다.

그러던중 만난 사이트중 하나가 Dovelet이다. 나같은 초보에게 딱 적합한 사이트로 어떤 테스트 케이스에서 오답이 나오는지 친절히 알려주어 다른 사이트에서 겪을 수 있는 답답함을 해소해 주었다. 오답의 경우를 알려주는 것이 문제 풀이 능력 향상에 도움이 안 될 수 있고, 재미를 반감시킬 수 있다는 의견도 있겠지만 어디까지나 초보자에게는 오답케이스를 알려주는 것도 의미 있는 일이라고 생각한다. 난 알고리즘 문제 풀이의 초보자 이기 때문에 쉬운 난이도부터 차근차근 풀어 볼 필요가 있는데 그에 딱 적합한 사이트였다. 여기서 지금까지 500문제가 넘는 문제를 풀었다. 어려운건 건들지 못했으며 내 수준에서 풀 수 있는 문제들만 =_=;;

올 초부터는 마음맞는 04학번 친구들과 같이 Topcoder도 시작했다. 다들 실력은 그리 좋지 않아 블루와 그레이 사이를 오고 갔지만 재미있게 연습했던 기억이 난다. 최근엔 하지 못해 몇달 째 그린으로 남아있지만 -_-;;;

올 여름방학에 있었던 Algospot의 Summer-Camp도 많은 도움이 되었다. 실력있는 분들이 직접 기본 내용에 대해서 강의를 해주었고, 그 내용을 적용하는 문제들을 골라준 덕분에 많은 연습을 할 수 있었는데, 당시 대전에 있었기 때문에 주말마다 먼거리 이동을 했지만 아깝거나 힘들진 않았다(.... 사실 무지 피곤했다ㅠ). 이곳에서 하루 종일 알고리즘 문제를 푸는데에 집중 했던 감옥 체험은 생전 처음해봤다. 구글 코리아의 스낵바가 없었다면 중도 포기를 했을지도.[사랑합니다 스낵바 ㅠㅠ]  이 캠프에서 DP를 풀 때 어떤식으로 사고를 해야 하는지, 기하 문제를 풀기 위해서 무엇을 알고 있어야 하는지, 문제를 어떤식으로 변형하여 생각을 해야 하는지 등에 대해 맛을 볼 수 있었는데, 이번 겨울방학때도 캠프를 열 계획이라고 하니 가능하면 또 참가해볼 생각이다.

학기가 시작하고 어떤 문제를 풀어보며 대회 준비를 해야 하는지 모르는 상황에서, 아주대학교 정현환님이 전화를 해주셔서 아주대 연습에 같이 연습하자 해주신 덕분에 인터넷 예선과 본선 대회 준비를 하는데 방황을 하지 않을 수 있었다. 여기서 연습하면서 가장 기억에 남는 것은 A번 난이도의 문제를 여러개를 순서대로 2~10분안에 해결하는 타임어택 문제풀이. 컨테스트가 이어지는 동안 긴장의 끈을 놓지 않고 재미있게 문제 풀었던 기억이 난다.

하지만 막상 이번 인터넷 예선을 치루고 나서는 지금껏 준비한다고 준비를 했던건데 예상했던것 만큼 문제를 풀지 못해 낙담했다. 우리팀은 쉬운 A번을 내가 잡아서 빨리 끝내 패널티에서 유리해지려고 했었는데, 8번 내리 틀려 버리는 바람에 완전 꼬여버렸다. '비토의 친척들' 이라는 문제를 살짝 변형 한 듯한 B번과 공식을 알고 있던 G번을 풀었지만, 간단한 DP로 보이는 C번도 결국 답을 내지 못했다. HM을 받고 쿼터제로 올라가는 수모는 피할 수 있었으나 노력한거에 비해서 결과가 나오지 않아 썩 기분 좋은 예선이 아니였다.

쏟아지는 과제들과 중간고사 일정, 그리고 졸업작품. 인터넷 예선이 끝나고 갑자기 더 바빠져서 대회 연습을 제대로 못했다. 처음 팀을 만들때 "우리팀은 시험기간에도 연습할꺼다~" 라고 말했는데 막상 시험기간이 되니 그럴 여유가 전혀 없어서 매일 모이기로 한 것도 못 모이게 되었다. 그 와중에도 틈틈이 한두문제씩 풀어보긴 했으나 인터넷 예선의 충격으로 대회에서의 자신감이 높진 못했다.

심지어 대회 당일이 팀원중 하나가 D회사 인적성 검사를 받는 날이랑 겹친다는 사실을 알게 되어서 팀원에게 대회 포기하고 인적성 검사 받으러 가라고 까지 말을 했었다. 대회는 이번이 마지막이라며 지금까지 연습한게 아깝다며 회사는 '다음'에 다시 지원할수 있다고 그 친구는 D회사을 포기하고 대회를 선택해 주었고 대회에 참여하게 되었다. (안타깝게도 D회사에서는 인적성 검사 일정을 조정해 줄 수 없다고 했단다.)

금요일에 마지막 전공 중간고사을 보고 나니 예비소집에 가 있던 팀원에게 연락이 왔다. 팀노트를 예비소집에 미리 제출을 해야 한다며.. 4년전 대회때는 책은 마음껏 가지고 와도 되는거여서 마찬가지로 팀노트를 대회당일 가지고 가면 되는거라 생각을 했던지라 시험끝나고 하려고 작성을 해놓지 않았었다. 고맙게도 예비 소집이 끝나기 전까지 보내주면 대회측에서 프린트를 해준다고 해서 부랴부랴 작성하기 시작. Algospot 캠프때 배웠던 내용들과 그 때 풀었던 문제중에 신선했던 문제들, 다시 풀이를 떠올리는데 오래 걸릴 것 같은 문제들을 추렸다. 캠프에서 기하 관련 라이브러리 정리 해둔 것을 붙여 넣고, 잘 외워지지 않은 알고리즘 몇개를 붙여넣고 보내주었다.

우리팀이 자리잡은 숙소에 저녁늦게 도착하여 간단히 문제를 풀어보려고 시도했다. 이때 본게 union-find 관련문제. 더 많이 보려고 했지만 시험에 대한 여파 때문인지 눈을 뜨고 있기 힘들어 난 먼저 잠을 잤고 눈을 떠보니 대회 당일 아침이였다.

마음을 최대한 편하게 먹었다. 나름대로 연습을 했었지만 인터넷 예선 결과가 그다지 좋지 않았기도 했고, 상을 타려고 생각했다가 실패를 하면 받을 정신적인 상처에 대한 방어 체계 였던듯 하다. HM만 피하고 싶은 생각 뿐이였다. 2006년부터 우리 학교에서 참가를 해 지역대회까지는 항상 나갔지만 언제나 HM을 받았기 때문에 이번엔 순위를 받고 싶은 생각 뿐이였다.

학교이름의 마지막은 Education. 오탈자가 있다는건 대회 끝나고 몇일뒤 알았다. (ㅠㅠ)

대회 시작을 알리는 징이 울리고 이번에도 인터넷 예선과 같이 A번을 내가 잡았다. 마음을 편하게 먹으려고 했고 팀원들에게도 맘편히 쉬엄쉬엄 문제 풀자 라고 까지 말을 했는데, 문제를 읽고 Visual Studio에서 프로젝트를 만드는데 두번이나 CLR Console Application 프로젝트를 만들어 버렸다. 한박자 쉰다음에 제대로 Win32 Console Application 프로젝트를 만들고 코딩을 했는데, 제출하기 전에 떨렸다. 인터넷 예선때 계속 되었던 WA가 떠올라서 (ㅠㅠ). 하지만 이번엔 다행히도 한번에 Yes를 받았다. 맘 편한척 했지만 안도의 한숨을 쉬었다. 이어서 무작정 모든 경우의 수를 돌려 보면 되는 B번도 풀었다.

하지만 이번 대회의 복병이 숨어있었는데 바로 D번. 문제를 읽자마자 어젯밤 자기 전에 보았던 union-find가 떠올랐다. 하늘이 우리를 돕는구나 라는 생각에 정리해둔 팀노트를 보며 작성해서 제출했지만 WA. 다른 방법으로 풀어야 한다는건 전혀 생각을 하지 않고 사소한 실수가 있을꺼란 생각에 몇 번 수정하다가 WA를 몇번 더 받고 다른문제 부터 풀기로 마음 먹었다.

괜히 문제만 길고 어려워 보이지만 사실은 역시 그냥 다 돌려보면 답이 나왔던 C번도 풀어 내고나니 더이상 무엇을 풀어야 할지 감이 오지 않았다. 주위를 둘러보니 초록색 풍선이 많이 있는데 우리는 초록색 풍선을 가지고 있지 않아 D번이 초록색 풍선이라 생각을 했다. 쉬운 문제인데 인터넷 예선때 처럼 또 무언가에 말려 들어 못 풀고 있는거라 생각이 들어서. 

마음의 동요가 생길꺼 같아서 여태까지 열어보지 않았던 스탠딩을 보니 왠지 지금의 순위만 지키면 수상 할 수 있을꺼 같은 생각이 들었다. 괜히 급해졌다. 열어보는게 아니였는데 ㅠㅠ.

D번에 대한 알고리즘의 반례를 팀원이 찾아준 덕분에 깨끗하게 union-find를 포기했다. 어떻게든 끼워맞춰 풀려고 했던것을 접근 방법을 바꾸어 방향 그래프를 만들어 모든 도달 할 수 있는 Node를 마킹하는 식으로 풀어 8번만에 간신히 yes를 받았다. 이 때 벌써 대회시간 5시간중 4시간이 넘게 지났다. 평균적으로 한시간에 한문제씩 풀었다. 스탠딩을 보니 D번의 많은 삽질 때문에 4문제 푼 팀중에서 순위가 썩 좋지 않았다. 하지만 한문제를 더 풀면 순위가 10등 이상 상승 할 수 있을 것 같아 보였다. 게다가 D번을 풀어서 우리에게 온 풍선의 색은 여전히 초록색이 아니였다.

2~3번째로 많이 달고 있는 듯이 보이는 초록색이 오지 않아 하나의 희망이 생겼다. "풀지 않은 문제중에서 쉬운 문제가 숨어있다. !" 대회 초반에 보았던 DP를 이용하는 문제 인듯한 E번을 뚫어져라 쳐다 보았다. 솔루션이 떠오르지 않아 기분 전환겸 화장실에 괜히 한번 걸어갔다 오는 중에 자식과 부모간의 조합을 이용한 점화식이 떠올랐다. 바로 코딩하고 제출~ 하였으나 Run Time Error~ 이진트리를 배열로 만든지라, 배열 범위를 체크해보니 트리의 깊이가 가장 깊을 때 자식의 수를 체크하는 부분에서 배열의 범위를 넘어가는 곳에 접근을 하는 바람에 죽은 것이였다. 예외처리 할 생각을 안하고 바로 배열범위만 두배로 늘리고 제출했다. PC^2에 뜨는 결과창이 무서워 하단으로 내리고 저지의 응답을 기다렸다. 작업표시줄에서 반짝이며 메시지가 도착했음을 알리는것을 보고 떨리는 마음으로 클릭해 창을 앞으로 꺼냈다. 보이는건 yes!

나도 모르게 박수치고 자리에서 일어섰다. 이 문제를 푸니 도착한 풍선의 색은 초록색. 그토록 궁금하던 초록색의 문제가 바로 E번 이였다. 

우리팀의 제출은 이렇게 끝이 났다. 한문제 더 시도를 해 보았지만 문제를 잘 못 이해 한건지, 이상 없어 보이는 알고리즘으로는 WA만 받았다. 4문제 풀었던 팀들이 얼마나 한문제를 더 푸느냐에 따라, 5문제 이상 푼 팀중에서 학교 중복이 얼마나 많으냐에 따라 우리의 수상 여부가 결정되는 상황이다.

다른 팀들이 문제를 더이상 풀지 않았으면 하는 못된 마음을 먹으며 남은 30여분을 보냈다. 종료를 알리는 종소리를 듣고 애써 외면했던 마음의 짐을 하나 내려 놓았다.

4년전 대회에서는 한시간 정도에 두문제를 풀고 나머지 4시간 동안 아무런 문제도 풀지 못했다. 시간은 길었지만 아무리 시도해도 풀리지 않은 문제 탓에 지루했고 재미도 없었는데, 이번 대회는 대회 내내 골고루 문제를 풀어서 개인적으로 재미있게 대회를 치루었다. 4년전 대회에서는 종료하고 손에 들고 있던 풍선이 팀원 수보다 적은 2개였는데 이번엔 5개였다. 그땐 하나라도 가지고 노는게 아까워 건들지 못했는데 이번엔 낼름 하나를 풀어서 핼륨 가스를 마셔줬다.

대회가 끝나고 보관했던 짐을 찾아서 핸드폰을 켜 acm.kaist.ac.kr 에 접속을 해서 팀명과 학교명이 적혀 있는 스탠딩을 확인했다. 최종 스탠딩은 우리가 E번을 풀기 직전의 스탠딩인듯 보였고 학교를 세어보니 동상은 거의 확실하고, 4문제를 풀었던 아주대, 연세대, 인하대, 시립대 팀이 모두 그대로 라면 은상까지 가능했다.

Algospot의 문자중계를 보니 다른 대학의 상황이 업데이트 되어 있었다. 중계를 통해 연세대와 아주대는 4문제로 종료되었다는 것을 알 수 있었지만 인하대와 시립대의 상황은 나와 있지 않았다. HM만은 피하고 싶었던 처음 마음은 잊고, 이를 확인하니 은상을 받지 않으면 섭섭할꺼 같다는 생각이 들기 시작 -_-; 사람의 마음은 욕심이 끝이 없다니.

기업설명회가 끝나고 특별상 수상이 끝나고, 본대회 수상식 시작!. 동상 부터 시작을 했는데 상황을 몰랐던 시립대와 인하대를 호명했다. 우리팀의 은상이 확정되는 순간이였다. 오늘 아침까지만 해도 상을 받을 수 있게 될지 몰랐다. 정말 꿈에도 몰랐다.

[ 출처 : http://yfrog.com/4pn7mlj ] 맨 왼쪽에 있는게 나 =_=;

긴장을 하지 않고 마음을 편하게 먹을려고 애쓴 덕분이였던거 같다. 작년에 우수한 성적을 냈던 숭실대와 서강대의 멤버들이 휴학을 해 이번대회에 참가하지 않은 덕도 있다. 운이 좋게 풀 수 있는 문제가 나온 덕도 있다. 이렇게 이런저런 이유를 찾아보려 하지만 상을 받았다는게 신기하고 잘 믿겨지지 않는다.

최종 스탠딩이 올라온것을 보니 5문제 푼 팀중에선 가장 패널티가 많다. 학교별 1등만 상을 받을 수 있는 덕분에 우리보다 우수한 많은 다른 대학 팀들은 아무런 상을 받지 못하고 우리에게 까지 상장이 내려왔다. 때문에 어느 누군가에게는 별것 아닌 은상으로 비추어 질 수 있다는것도 안다. 하지만 우리에게는 큰 값어치가 있다.

저녁 리셉션때 대회 디렉터이신 좌경룡 교수님께서 우리팀이 다른 대학의 희망이 되었다고 말씀해 주셨다. 매년 대회를 치루지만 수상하는 팀은 거의 정해져 있다. 비 수상권에 있는 대부분의 대학이 이 대회에 대해서 관심도 없고 지원도 없다. 학교에서 대회를 알고 준비하는 학생도 없고, 어떻게 준비해야 하는지 아는 사람도 별로 없다. 대회의 존재를 알게 되어 준비를 한다 하더라도 4년전에 우리가 그랬던 것 처럼 정보의 빈부 차이와 경험의 유무에서 오는 어쩔 수 없는 갭이 존재한다. 우리학교도 그런 학교 중 하나인 상태에서 4년이 지나서야 수상을 하게 되었다.

난 이번 대회가 마지막이다. 이번의 성과가 학교 후배들에게 좋은 자극이 되어 할 수 있다는 자신감을 가지고 열심히 공부를 하는 계기가 되었으면 하는 바람이다. 좌교수님 말씀대로 타 대학에서도 노력하면 수상이 가능하다는 용기도 가졌으면 하는 마음도 있다. 우리학교에서도 학교나 학부 차원에서 조금 더 관심을 가지고 지원을 해줬으면 하는 바람도 있다. 이번 한번의 반란이 아닌 후배들이 이어서 다음 대회에서도 좋은 성적을 내주었으면 하는 소망도 있다.

대회가 끝난지 3일이 지났는데 아직도 꿈같은 느낌이 든다. 오래전부터 나갈려고 마음에 두었던 대회였고 수상했으면 하는 막연한 소망을 가지고 있었고 이게 이루어졌다. 모든 지나간 것이 그러하듯 꿈같다는 느낌과 약간의 허무감이 남아있다. 어서 이를 떨치고 일상으로 돌아가야지.

지금 이 기분과 생각을 남기고 싶어 다소 장황하게 블로그에 글을 남긴다. 나중에 보면 손발이 오글거릴 글 하나 완성. =_=;;