Outsider's Dev Story

Stay Hungry. Stay Foolish. Don't Be Satisfied.
RetroTech 팟캐스트 44BITS 팟캐스트

Google Code Jam 참가 후기

Google Code Jam 2012에 참가했습니다. 구글 코드잼은 구글에서 매년 진행하는 알고리즘 경진대회입니다. 항상 이맘때쯤 진행하는데 알고리즘 문제를 몇개 주고 시간내에 이를 프로그래밍해서 답을 제출하는 방식으로 진행이 되고 그걸로 순위를 매깁니다. 어떤 의미해서는 개발자들의 축제(?)라고 할 수도 있고 이런 식의 알고리즘을 푸는 것은 ACM이나 ICPC 대회라고 부르고 코드잼외에도 수많은 사이트들이 있습니다. 구글처럼 대형기업에서 진행하는 것은 페이스북의 Hacker cup이 있습니다. 구글은 한지 수년된 걸로 알고 있고 Hacker cup은 작년에 처음 한것 같습니다. 국내에서는 올해 처음으로 코드잼 코리아가 진행되었습니다.

code jam 로고
제가 알고리즘은 잘 못 풀기 때문에 아주 얕은 경험이지만 이번에 하다보니 코드잼을 잘 모르는 사람들도 많고 저도 처음에 하면서 불필요한 헛발질들도 좀 한 관계로 내년에 참가해보려는 사람들에게 도움이 좀 될까 하고 코드잼에 대한 내용을 적어봅니다.

코드잼 기준으로 Qualification Round이 예선전입니다. 일정점수(보통 20점) 정도를 넘으면 QR 통과입니다. 통과하면 Online Round 1로 가고 Online Round 1은 총 3번 진행합니다. 3번 중 아무거나 참여해서 1,000명 안에 들면 Online Round 2로 진출합니다. 총 3번 진행하니까 3,000명이 Online Round 2로 진출하는 것입니다. 물론 3개 다 참여해도 됩니다. 문제를 풀면 점수가 나오고 문제를 푼 시간까지 포함해서(제출했는데 틀리면 페널티를 먹는데 시간으로 페날티를 먹습니다.) QR에서는 점수만 보기 때문에 페널티가 의미 없습니다. QR은 보통 24시간정도의 시간이 주어지지만 그 다음부터는 2시간 반내에 풀어야 합니다.(Round 2는 못가봐서 그 뒤부터는 잘 모르겠네요. 거기까지 가신 분이 이 글을 참고하고 있진 않으실 테니...)




코드잼 대회전에 알고 있어야 할 것들
문제는 보통 A, B, C 3개가 나오게 됩니다. 해커컵도 거의 비슷하게 진행이 되는데 어떤 문제인지 설명이 죽~ 나옵니다.(물론 영어로요.) 인풋을 주는데 인풋 파일을 프로그램에 입력하면 아웃풋을 출력하는 형태로 이루어집니다. 그래서 결과는 아웃풋파일을 제출해서 답이 맞는지 안맞는지 검사하게 됩니다.

4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21

인풋은 보통 위와 같은 형식입니다. 맨 위에 4는 문제가 4개라는 의미이고 보통은 한라인에 한문제씩인데 경우에 따라서는 아닌 경우도 있습니다. 각 라인의 값이 무엇을 의미하는지는 문제에 따라 다르지만 위처럼 여러개의 값을 공백으로 분리해서 나타냅니다. 그래서 미리 인풋파일을 읽어서 파싱하는 코드정도는 짜두는게 좋습니다.(이건 어느 문제에서나 해야되는 거니까요.) 저는 보통 첫라인은 읽지 않고 라인별로 리스트로 만들어서 처리하지만 그건 편의에 따라서 하면 됩니다. 문자열을 복사해서 처리할 수 있지만 이건 좀 귀찮으니까 그냥 파일로 읽는게 좋습니다. 알고리즘은 특성상 TDD나 유닛테스트와 함께 짜기 좋기 때문에 테스트 환경을 미리 준비해 두는 것도 좋습니다.

Case #1: 3
Case #2: 2
Case #3: 1
Case #4: 3

아웃풋은 위와 같은 형태가 됩니다. Case #문제번호: 와 같은 형식에 옆에 답을 적어주게 됩니다. 그래서 인풋에서 각 라인의 문제를 읽었을 때 넘버링을 해서 이처럼 출력할 수 있어야 합니다. 아웃풋도 인풋처럼 출력하는 부분을 미리 작성해 두면 시간을 절약할 수 있어서 좋습니다. 출력을 콘솔에 출력해서 파일에 붙혀넣어도 되고 어차피 파일을 제출해야 하기 때문에 파일쓰기로 만들어도 좋습니다.

코드잼 문제의 인풋 버튼

각 문제는 위처럼 Small input와 Large input 2개가 주어집니다. 위 사진은 이미 끝난 라운드의 문제라 2개 다 버튼이 보이지만 원래는 Small input을 통과해야 Large input에 도전할 수 있습니다. 버튼을 누르면 몇분이내에 아웃풋 파일과 소스를 제출해야 하기 때문에 미리 뭔가 하고 눌러보면 페날티만 물게 됩니다. 해커컵 같은 경우는 작년에 재시도가 없어서 한번만 눌러서 떨어졌던 것 같습니다.

그리고 옆에 점수를 잘봐야 합니다. 보통 20점 넘으면 예선 통과 이런 식인데 한 문제의 small과 Large를 다 풀어도 예선 통과 점수가 안되는 경우도 있습니다. 그럴 경우에는 다른 문제의 Small을 하나 더 풀어야 통과할 수 있기 때문에 점수랑 상황을 잘 보고 해야 합니다. 저는 항상 QR에서 떨어지다가 이번에 처음 QR을 통과했었는데 기분인지는 몰라도 QR에서는 A 문제보다 B 문제가 더 쉬웠던 기분이 들었습니다. 꼭 A가 쉬운건 아닙니다.(보통은 점수가 낮으면 쉽다고 추측할 수 있겠죠.)




코드잼 대회에 참가할때 고려해야 할 것들
몇 번 해보니 가장 크고 처음 부딪히는 난관은 문제의 이해입니다. 한국 구글 코드잼이 아닌 이상 당연히 문제는 영어가 나옵니다. 알고리즘 문제는 구어체가 아니기 때문에 이게 은근히 문제를 이해하기 어렵고 결과적으로 정답을 맞춰야하기 때문에 문제의 조건 중 하나만 잘못 이해하더라도 당연히 정답을 맞출 수 없습니다. 여러번 하다보니 좀 나아졌지만 몇년전에 할 때는 문제도 제대로 이해하지 못했서 메일링이나 채팅에서 여럿이 모여서 문제에 대해서 이야기 나누고는 했습니다.

알고리즘은 현업에서 하는 프로그래밍하고는 좀 다르다고 생각합니다. 프로그래밍이란 것은 문제를 해결하는 과정이라고 하긴 하지만 현업에서 프로그래밍 할 때는 사실 알고리즘 성격의 코딩을 할 일은 별로 없습니다. 웹 어플리케이션에서는 대게 더 비즈니스 로직이 뻔한 수준(?)이고 어떤 어려운 알고리즘을 푸는 일 같은 건 별로 없습니다. 알고리즘을 푸는 것은 평소하던 프로그래밍하고 사고하는 방식이 완전히 다른 느낌입니다. 그래서 이런 쪽으로 연습을 많이 해두는 게 좋습니다.(문제는 알고리즘 사이트들에 수없이 있습니다.)

대회 참가를 시작하고 10분 정도가 지나면 제출자가 나타나기 시작합니다. 코드잼은 왼쪽에 탑스코어러와 제출자 통계가 실시간으로 나옵니다. 저는 아직 문제를 다 읽지도 못했는데 이미 다 풀어서 제출까지 하는 사람들이 등장합니다. 여기서 잠시 멘탈 붕괴가 올 수 있는데 참고 풀어야 됩니다. ㅠㅠ 어차피 그런 수준의 사람과 경쟁할 의도는 아니었으니까요. ㅎ

코드를 짤 때 Large input도 고려해서 코딩해야 합니다. 문제를 보면 input 값의 범위가 나오는데 이 경계값까지 고려해서 작성해야 합니다. 보통 small input은 값의 범위가 좀 적지만 large input은 큰 범위의 값들이 많이 나오게 됩니다. 이런 걸 잘 몰랐을 때는 타입을 Int로 하거나 성능을 고려하지 않고 막 짜다가 Large input을 돌려보다가 오류가 나거나 Stackoverflow가 나서 수정하다가 제출 못하는 일도 있었습니다. input 파일을 다운받기 전에 미리 경계값을 넣어도 잘 돌아가는지 테스트해 보아야 합니다. 보통 small input은 여러번 시도할 수 있지만 large input은 한번의 기회 뿐입니다.(large는 보통 결과도 나중에 나옵니다.)

추가로 피곤한 것 중 하나가 output을 제출했을 틀렸다고는 나오지만 어느게 틀렸는지 나오지 않습니다. 문제를 잘 못 이해한 부분이 있거나 로직에 버그가 있을 경우 어디가 틀린건지 알 수 없습니다. 이건 뭐 방법이 없는것 같습니다. 로직을 보면서 다시 고민해서 버그를 찾거나 문제를 손으로 직접 다 풀어봐서 어느 문제가 왜 잘못되었는 지 찾아내는 방법밖에 없는 것 같습니다. 저는 항상 여기서 시간을 다 소비합니다. ㅠㅠ




Epilogue
매년 참가는 하고 있는데 사실 이런 대회는 자신이 가장 익숙한 언어를 사용해서 하는 것이 좋습니다. 하지만 저는 뭐 재미나 연습의 의미도 있고 해서 Scala로 풀었습니다. Scala는 제가 익숙한 언어는 아니고 하다보면 API 문서를 보고 찾아서 하거나 문법을 몰라서 헤매는 경우도 많기는 하지만 Scala를 공부하면서 사실 사용할 일은 많지 않기 때문에 Scala 연습도 겸할 겸해서 참여했습니다. Scala를 연습하는게 한 50%정도라면 알고르짐 푸는 연습하는게 30%정도이고 20%정도는 QR통과를 목표로 하고 있었습니다.(QR통과는 한번도 못해봤기 때문에요.)

그런 면에서는 소기의 성과를 달성했습니다. 몇가지 안되긴 하지만 Scala를 쓰면서 손에도 약간 익었고 Scala IDE나 ScalaTest도 사용해 보았습니다. 알고리즘도 아직 부족하지만 약간씩 늘고 있는 것 같긴 하고요. 그럼에서 Round 1에서 떨어지니까 좀 분했습니다. 문제도 잘못 이해하기도 했고 저는 2시간 반이란 시간이 턱없이 부족하기도 했지만 내년을 위해서는 더 정진해야겠습니다. Code Jam 2012 Statistics - Go, Hero!사이트에 가면 코드잼 참가에 대한 여러가지 언어나 나라별 통계를 볼 수 있습니다.
2012/05/08 02:41 2012/05/08 02:41