구글 코드잼 2012 예선 참가 후기

구글 코드잼

구글 코드잼에 대한 설명은 이전 포스팅을 참고하세요.(구글 코드잼 참가 신청)
4월 14일 오전 8시부터 15일 오전 9시까지 구글 코드잼 2012 온라인 예선이 열렸습니다.
대회 시작 시각이 되자 구글로부터 코드잼 예선 시작을 알리는 메일이 도착했습니다.
다음 링크에 접속해서 문제를 풀었습니다.
http://code.google.com/codejam

문제

문제는 A~D로 총 4개가 주어졌습니다.

A. Speaking in Tongues (15점)
B. Dancing With the Googlers (10점+10점)
C. Recycled Numbers (10점+15점)
D. Hall of Mirrors (15점+25점)

A 문제는 large input이 없었고, 나머지 문제들은 small input과 large input이 각각 채점되었습니다.
100점 만점에 20점을 넘으면 통과였기 때문에 1-2문제만 풀면 통과할 수 있었습니다.
작년과 달라진 점은 large input의 경우의 제한시간이 8분으로 늘었다는 점입니다.

풀이

작년에는 PHP를 사용했으나, 올해는 얼마 전부터 배우기 시작한 python을 사용하였습니다.

A. Speaking in Tongues

알파벳 26글자를 일대일대응으로 치환해서 만든 Googlerese라는 언어를 제시하고, 대응관계를 찾아서 Googlerese를 English로 번역하는 문제였습니다.
예문으로 주어진 3 문장을 분석해 보면 알파벳 26글자 중에서 24글자의 대응관계를 찾을 수 있지만, q와 z의 대응관계는 주어지지 않았습니다.
그러나 문제에 주어진 힌트를 살펴보면 z->q로 대응되는 것을 알 수 있으므로 일대일대응의 원리에 따라 q는 z에 대응됩니다.
이를 이용하여 주어진 Googlerese 문장을 번역할 수 있습니다.
large input 문제가 없고 small input 문제만 있었고, 쉽게 풀었습니다.
아마 암호화/복호화를 염두에 두고 출제한 문제로 생각됩니다.

B. Dancing With the Googlers

댄서들을 3명의 심사위원들이 평가하는 상황을 제시하고, 댄서가 받은 점수의 총점과 심사위원별 점수 중 최대값과의 관계를 구하는 문제입니다.
총점을 3으로 나눈 나머지에 따라 경우를 나누어 풀면 쉽게 풀립니다.
small input과 large input이 큰 차이 없이 쉽게 처리되어 답을 얻었습니다.
무엇을 염두에 두고 출제한 문제인지는 모르겠습니다.

C. Recycled Numbers

경우의 수 문제입니다.
주어진 범위 내에 속한 n자리 숫자를 재배열한 새로운 숫자를 만들어서 다시 주어진 범위 내에 속하도록 하는 경우의 수를 구합니다.
python의 성능을 믿고 for 문을 2번 중첩해서 사용한 결과 답이 구해졌습니다.
small input의 경우에는 금방 구해졌지만, large input의 경우에는 답을 구하는 데에 6분 정도 소요되어 아슬아슬하게 통과했습니다.
정렬 관련 알고리즘을 묻는 문제로 생각되지만 제대로 된 방식으로 푼 것인지는 모르겠습니다.

D. Hall of Mirrors

배점이 가장 크지만 제대로 풀지 못한 문제입니다.
거울로 된 방 안에서 자신의 모습이 몇 번이나 반사되어 보이는지를 묻는 문제입니다.
small input의 경우에는 방 안에 벽면에만 거울이 있고, 내부에는 또다른 거울이 없기 때문에 좌표평면으로 옮겨서 대칭과 거리, 기울기를 이용하여 풀었습니다.
large input의 경우에는 방 안에 또다른 정육면체 거울들이 존재했기 때문에 아예 풀 엄두를 내지 못했습니다.

성적

최종 성적은 A(15점) + B(10점+10점) + C(10점+15점) + D(15점) = 75점입니다.
등수로는 전세계 374등입니다.
예선 통과의 커트라인인 20점을 넘겼기 때문에 다음 라운드에 진출하는 데에는 성공했지만 격자나 기하를 응용한 문제를 풀기 위한 공부가 필요할 것 같습니다.
다음 라운드는 4월 28일에 한 번, 5월 6일에 두 번 열리고, 1000등 이내의 성적을 받으면 됩니다.

관련 포스트

구글 코드잼 참가 신청

어느덧 2012년의 구글 코드잼 시즌이 되었습니다.

구글 코드잼은 구글에서 개최하는 프로그래밍 대회입니다.
제한 시간 내에 주어진 수학 문제를 해결하는 코드를 작성하여 문제를 해결해서 소스 코드와 함께 답을 제출하면 채점이 되고 순위가 매겨집니다.
사용해야 하는 프로그래밍 언어는 제한되어 있지 않습니다.

구글 코드잼은 2003년에 처음 시작한 이래로 매년 열리고 있고, 전 세계에 있는 직장인과 학생 누구나 무료로 참가할 수 있습니다.
총 4번의 온라인 대회를 차례대로 통과한 상위 25명은 뉴욕에 있는 구글 본사에서 열리는 결승전에 진출할 수 있습니다.
최종 우승 상금은 1만달러이고, 우승자에게는 구글에 입사할 기회가 주어집니다.
우승을 하지 못하더라도 1000등 안에 들면 티셔츠를 받을 수 있습니다.

한국 시각으로 어제 새벽부터 접수가 시작되었습니다.
접수는 1달 동안 진행되고, 접수 마지막 날에 25시간 동안 진행되는 온라인 예선전이 시작됩니다.
저는 작년에 이어서 올해에도 참가 신청을 했습니다.

코드잼에 접수하기 위해서는 구글 계정을 만든 상태에서 다음 주소에 접속합니다.

https://code.google.com/codejam

Participate 버튼을 클릭하고 몇 가지 정보를 입력하면 참가 신청이 접수됩니다.

접수가 완료된 뒤에는 접수 확인 메일을 받게 됩니다.
다시 구글 코드잼 주소에 접속해 보면 Participate 버튼 대신에 예선 시작까지 남은 시간이 표시됩니다.

주의할 점은 모든 문제가 영어로 제시되기 때문에 문제를 이해하는 데에 불리할 수 있다는 점을 감수해야 합니다.
이런 점을 고려하여 얼마 전 구글 코리아에서는 구글 코드잼 코리아 2012를 개최하기도 했습니다.

또 다른 주의할 점은 문제 풀이의 순서와 제한시간입니다.
각각의 문제에서는 처리할 데이터의 크기에 따라 small input, large input 두 가지 파일을 주고, small output, large output 두 가지 파일을 제출해야 합니다.
제출한 output 파일들은 각각 따로 채점됩니다.
당연한 얘기이지만 small에 비해 large output의 배점이 높습니다.
small input 파일을 다운받아 처리한 뒤에 small output 파일을 제출합니다.
만약 정답과 일치한다면 large input 파일을 다운받을 수 있습니다.
large input 파일을 다운 받은 후로부터 제한된 시간(5분) 안에 large output 파일을 제출해야 합니다.
만약 large input 파일을 처리해서 output 파일을 만들어내는 데에 시간이 오래 걸려서 제한 시간을 초과했다면 그 문제는 틀린 것으로 기록되고 다시는 풀 수 없습니다.

관련 포스트