[프롤로그]

온라인으로 치루어 지는 google codejam 예선전에 처음으로 참가해 보게 되었습니다. 하루동안 대회를 접해 보면서 나름대로 재미있는 경험이 되었구요, 대회를 접해 보지 않은 상태에서 나중에 저와 똑같은 실수를 범하는 사람들이 또 생겨 날까봐, 그 실수를 피해 갈 수 있도록 알려 드리고자  X팔림을 무릅쓰고 이렇게 글을 적습니다. 향후 구글 코드잼 도전을 생각하시는 많은 분들께 도움이 되었으면 하는 바램입니다.

구글 코드잼 공식 홈페이지 : http://code.google.com/codejam

[히스토리]

어리버리하게 있다가 메일로 google codejam 시작한다는 메일이 날라 온 것을 확인했습니다. 한국 시간으로 아침 8시부터 24시간동안 문제를 푸는 예선전(Qualification Round)입니다. UTC 금요일 밤 11시에 시작을 하는 것이고, 한국 시각으로는 토요일 오전 8시입니다. 한국이라면, 금요일 저녁에 사람들 만나서 회식하지 않고 집에 가서 일찍 잠자리에 든 다음, 토요일 아침에 일찍 일어 나서 세수하고 상쾌한 마음으로 대회에 임하면 되겠습니다.

부랴부랴 1시간이 지난 시각(오전 9시)부터 문제를 풀기 시작했습니다. 최소 하나라도 정답을 제출한 사람들이 이미 수백명이 넘더군요. 흐미~  등수 체계를 보니까 일단 정답을 맞춘 사람에 한해서 일정 점수(10점 or 23점)를 부여하고 같은 점수를 가진 사람들은 정답을 먼저 제출(submission)한 순서대로 점수가 매겨 지더라구요.

score board를 보는 순간 '빨리 문제를 풀어서 올려야 겠구나' 하는 생각이 들었는데요, 나중에 자세히 얘기를 하겠지만 Qualification Round에서는 속도전은 절대 금물입니다. 정답 제출을 빨리할 이유가 전혀 없었던 것이었습니다. 부끄럽지만 아래는 저의 최종 결과입니다. 비록 예선은 통과했지만, 결과는 초허접 ㅠㅠ

일단 첫번째 문제( Snapper Chain )는 1시간 50분만에 풀었습니다. LSB부터 주어진 갯수만큼 모든 bit가 1이냐 아니냐를 보는 간단한 로직. 코드 작성은 5분도 안걸렸습니다. 문제의 요지를 파악(램프 꺼지고 켜지고 하는게 그냥 숫자 이진수 체계와 동일함)에 시간이 걸렸죠. small input 풀고 나서 대번에 large input 받아서 풀고... 끝! 구차한 변명 같이 보일지는 몰라도 대회 시작하고 1시간이 지난 이후에 문제 풀이를 시작했으니 실제로는 50분만에 문제를 푼 것이지요(핑계 맞습니다요 ㅋㅋ). 와, 그런데 top ranking에 드는 사람들을 보니 불과 몇십분만에  3문제 전부를 풀어 버리는.... 대단해 보입니다.

그 다음 문제는 2번째를 풀려고 했는데, 다른 사람들의 score를 보니 3번째 문제를 먼저 푼 사람들이 많더군요. 아마도 2번 문제가 어려웠나 봅니다. 그래서 저도 3번째 문제( Theme Park )를 먼저 풀어야지 했습니다. 문제 대충 보고 푸는 방법을 생각한 다음에 샘플 예제를 돌려 보니 정답이 제대로 나왔고 small input(10점 짜리)를 입력 받아 풀었더니, 정답이라고 하더군요. 바로 large input(23점 짜리)를 받아서 풀려고 하는데, 아뿔싸~ CPU가 팍 올라 가는 겁니다. 순간 입력되는 값들을 검토를 해 보니,  '아, 알고리즘을 이렇게 해서는 안되는구나' 판단을 했고 프로그램의 수정을 하기 시작했죠. '오호라~ 이 문제 출제의 의도가 바로 이것이구만. 과연 구글이군' 이라는 생각이 들더게 만들더군요.

large input에 대한 출력도 완성되었다고 판단하고 정답을 submit(제출)하려는 순간, 헉~ 이게 뭡니까? 정답(output) 제출이 안되는 겁니다. small input에 대해서는 몇번이고 반복해서 정답의 submit이 가능하지만, large input에 대해서는정답 제출이 단 한번의 기회밖에 없는 것입니다. 그것도 주어진 시간안에서만 해야 한다는 겁니다. (small input은 4분, large input은 8분).

보통 이러한 온라인상의 대회는 brute force attack의 접근만 아니라면 몇번이고 정답 제출을 try할 수 있도록 하는 것이 상식이죠. 그런데 google codejam 예선전에는 그러한 상식이 통하지 않았던 겁니다. 이걸 몰랐던 제가 바보죠. 해결 방안(정확히 정답을 산출하는 방법)을 알아 냈음에도 불구하고 정답을 제출할 수 없는 어처구니 없는 상황이 연출이 된 겁니다. 순간 생각했었죠. '알고리즘 확인 절차를 거치지 않고 괜히 빨리 정답을 제출하려고 했는데, 이게 화근이구나' 결국 예선전이 끝날 때 까지 3번째 문제의 large input은 score board상에서 "Time expired"라는 메세지만 보이며 나를 울리다가 결국은 0점 처리... ㅠㅠ

왜 이렇게 대회를 운영을 하는 것인지 도저히 이해가 되지 않았습니다. 대회 도중임에도 불구하고, 정확한 문제 풀이 방식을 알아 내어도 어쩔 수가 없는 형국. 그러면 어쩝니까? 후회해도 소용이 없습니다. large input에 대해서는 input 을 받자 마자, output 제출을 주어진 시간내에서만 해야 하고, 다시는 그런 기회가 주어 지지 않는다는 것을 몰랐던 제가 바보였던 거죠.

이때까지는 Qualification Round 정확한 통과 기준을 몰랐었습니다. 그냥 순위로 잘라서 다음 Round로 갈 줄 알았는데, 허걱! 그게 아니었습니다. score board 페이지의 윗부분을 보니 다음과 같은 문구가 있는 겁니다.

이제 마지막 문제인 2번째 문제( Fair Warning )로 갑니다. 문제를 찬찬히 읽어 보고 문제 의도 파악을 이해한 다음(시간이 좀 걸렸습니다) 코드를 짜기 시작했습니다. 주어진 여러 숫자들의 각각의 차이의 조합들에 대한 최대공약수(great common divisor)를 구하는 것이 문제의 핵심입니다(요거 파악해 내려고 A4 용지 두세장에 이런 저런 숫자 끌쩍끌쩍해 보다가 1시간 정도 소요. 저질스러운 머리 ㅠㅠ). 숫자들이 워낙 커서 64 bit Integer로도 처리가 당연히 안되었고, 그래서 큰 크기의 정수를 처리하는 로직이 필요했구요, 결국 구글링을 통해서 BigInteger라는 클래스를 구했습니다(헥헥). third party 모듈 가져다 써도 상관없답니다. 구슬도 꿰어야 보배이고, 중요시 여기는 것은 구슬이 아니라 꿰는 방법이라는 얘기.

그리고 나서 또 다른 GCD 값을 구하는 문제. 큰 숫자들간의 GCD를 구하는 로직을 고민하다가(단순하게 for문 돌려서 나머지가 0인 공통된 숫자를 알아 내는 방식은 숫자가 워낙 크기 때문에 안됨) 우연하게도 간단한 로직에 의해서 GCD 값을 빠르게 구할 수 있는 로직을 발견해 냈습니다(이거 알아내는데도 시간이 좀 걸림). Euclid's algorithm 이라고 하는데(이놈의 유클리드라는 사람은 뭐 그리 많은 것들을 발견해 냈는지, 쩝) 아마도 이런 대회 준비하는 학생들에게는 이런 것들이 기본중의 기본이겠죠? 아흑, 대학교 때 공부 좀 더 해 두는 건데... ㅠㅠ 

요 공식을 찬찬히 보게 되면요, a와 b의 값이 조낸 큰 값이라 하더라도, 간단한 사칙 연산만 가지고 resursion 방식으로 계속 돌리다 보면 빠른 속도로 GCD값을 알아낼 수 있게 된다는 것을 알 수 있게 됩니다. a나 b가 아무리 큰 수라 하더라도 위의 공식에 의해서 큰 값이 작은 값으로 나눠 지게 되고(정수 나누기 & 나머지는 걍 무시)  그 크기가 계속해서 팍팍 줄어 들다 보면 언젠가는 하나의 값이 0에 도달하게 된다는 것. 당연히 for문을 무식하게 돌리는 방식( O(N) )보다는 훨 빠름.  아싸!!! 유클리드님 땡큐~ ^^. 이제부터 문제가 풀리기 시작했고, 관련 코딩을 하고 small input에 대한 정답을 제출해 보니 오~예~ 한번만에 패~쑤~.

이후에 large input을 받으려고 하니, 덜컥 겁이 나더군요.  또 Time Expired되면 어쩌나...  소스 코드상 면밀히 검토를 한 이후에 문제가 없다고 나름 판단을 하고 large input을 받고 난 이후 돌려서 정답을 제출했습니다. input 파일 받자 마자 output 파일 빨리 만들어서 확 제출했습니다. 혹시라도 Time Expired되면 안되니까요.

허걱! large input에 대한 정답을 제출하자 마자 소스 코드를 보니, 잘못된 부분이 딱 보이는 겁니다. 제가 제출한 정답이 정답이 아니었더라는 거죠. 그런데, 이미 시간(8분)은 지나가 버린 상태. ㅠㅠ 결국 한번 제출을 한 것으로 실패하고 말았습니다. 아, 허무하더군요. 완전 똘아이가 된 기분이었습니다. 아래는 코드잼 운영자에게 문의를 하였고 그에 대한 응답을 받았습니다.

간단히 번역을 하자면( 질문을 올리자 마자 거의 실시간으로 응답이 올라 오더군요. 운영자(구글러)들도 대회 운영하는 동안 잠 못잤는 듯 합니다 ^^)

나 : "정답 제출 잘못했는데, 다시 제출할 수 없나요?"

운영자 : "안됩니다."

나 : "왜요? 서버 부하때문에? 네트워크 문제때문에? 이해가 안되는데요."

운영자 : "룰입니다."

나  : "그럼 앞으로 10시간이나 남았는데, 이제 제가 할 수 있는 것은 아무것도 없나요? 아마도 저와 비슷한 불평을 하는 사람들이 많을 것 같은데... 이뭐병"

운영자 " 죄송합니다. 룰입니다."

좀 화가 나더군요. RTFM!!! 대회의 룰을 제대로 보지 않았던 저도 잘못이 있지만, 저와 똑같은 클레임을 거는 사람들이 한둘이 아님을 상식적으로 짐작할 수가 있습니다. 하지만 돌아 오는 대답은 똑같네요. "룰입니다". 저 당시까지만 해도 몇백위 정도를 하고 있었습니다. 그런데 오늘 일어 나서 순위를 보니 3천 몇위... ㅋㅋㅋ. 생각해 보세요, 정답이건 오답이건 답을 다 제출하고 나서는 할 수 있는 것이 아무것도 없습니다, 비록 그 답이 오답임을 알아 차리고,  정답을 알고 있다 할 지라도. 그냥 나머지 시간은 집에 가서 발닦고 잠이나 잘 수 밖에. 뭔가 형평성이 안 맞죠.

그러기 때문에 예선전에서 속도전은 절대 금물입니다. 소스 코드를 몇번이고 검토를 하고 하고 해서 제대로 된 정답을 한번만에 맞추는 것이 중요했던 것이었습니다. 최소한 Qualification Round 만큼은요. 그런데도 불구하고 score board에서는 Top Ranking을 보여 주는데 있어서 제출 시간이라는 것이 중요한 것처럼 뉘앙스를 풍기며 표시를 해 주고 있으니, 대회를 처음 접하는 저같은 사람에게는 '정답을 제출하는 시간이 중요하구나' 라고 당연히 오해를 할 수 밖에 없습니다. 대회를 처음 접해 보았던 저만 결국 바보가 된 거죠.

[에필로그]

1. 직접 해보라. 직접 해 보면 구글 코드잼이 왜 재미있고 유익한 대회인지 저절로 알게 된다.

2. 예선전(Qualification Round)에서 순위는 전혀 의미가 없다(Top Ranking에 들어 가는 소수의 사람들의 경쟁을 제외하고는). 24시간은 3문제를 풀 수 있는 충분한 시간이다. 예선전에서는 절대 성급히 서두르지 말고 반드시 천천히, 그러면서도 차분히 진행하라.

3. 로직을 빨리 구현해서 정답을 빨리 제출하는 것보다 정확한 로직을 구현해서 한번만에 정답을 제출하는 것이 무엇보다 중요하다(Round 1부터는 잘 모르겠음. 나가본 적이 없으니 ㅋㅋ).

4. 대회의 Rule을 잘 검토해라. Rule을 잘 모르는 상태에서 접했다가는 낭패를 접할 수도 있다. 문제의 의도를 다 파악하고 남들보다 먼저 다 풀어 놓고도, 실수로 남들보다 정답을 단한번 빨리 제출했다는 죄(?)로 나중에 가서 등수가 뒤로 밀려 날 수도 있다. 이는 실력이 문제가 아니라 부주의의 문제이다.

5. 역시 구글. 한문제 한문제 풀 때마다 왜 이러한 문제를 냈는지를 저절로 알게 된다. 문제 하나 풀 때마다 뭔가 하나씩 배우게 된다는 의미. 똑같은 문제임에도 불구하고 Easy(small input)모드와 Hard(large input)모드에 대해서 해결 방식이 달라질 수가 있다. "좀 더 고민해 보세요" 라는 환청 소리가 들림 ㅋㅋ

6. 1등한 친구(neal.wu. 미국)의 점수를 보니 31분 30초만에 3문제를 오류 없이 정답 제출. 허걱, 저게 사람인가? 역시 세상에는 머리 좋은 사람이 많구나.

7. 영어는 별로 장애가 아니다. Newyork Times의 정치란의 기사 내용을 이해를 요구하는 수준은 아니라는 얘기. 다만 문제의 이해에 약간의 시간이 좀 더 걸리기는 함.

8. 코딩 실력(프로그래밍 실력)도 중요하지만, 역시 이런 대회도 결국 대회 참가 경험을 바탕으로 해야 하는구나를 느끼게 됨. 비슷한 유형의 문제를 이전에 풀어 봤더라면 훨씬 더 좋은 결과를 낼 수 있었다는 것. "준비한 자만이 열매를 얻는다"

이상 구글 코드잼 대회를 처음 접해 본 노땅의 푸념이었습니다. ㅠㅠ