구글 코드잼 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등 이내의 성적을 받으면 됩니다.

관련 포스트