https://codingcompetitions.withgoogle.com/hashcode

Google Hash Code라는 대회가 3/1 새벽에 열렸습니다. 국내에서는 아직 덜 알려진 것 같은데, 이 대회는 탑코더 마라톤 매치와 같은 최적화 문제를 2-4인의 팀이 4시간동안 풀이를 하는 대회입니다. 채점에 사용되는 데이터셋은 대회 시작과 동시에 바로 공개가 됩니다. 작년에는 예선에서 40팀이 선발되어 아일랜드 더블린에서 본선을 진행했고 올해도 아마 비슷할 것 같습니다. 작년 ICPC를 같이 했던 3명이서 같이 팀을 이뤄 참여했습니다.

시간이 충분하면 복잡하고 어려우면서도 효과적인 알고리즘을 생각해낼 수 있겠지만 이 대회에서는 시간이 4시간으로 굉장히 제한적이기 때문에 보통은 간단한 그리디 알고리즘을 일단 만들어놓고 그 알고리즘에 랜덤성을 부여한다던가, Simulated Annealing 혹은 Hill Climbing Method와 같이 조금씩 점수를 올리는 방식이 더 효과적인 경우가 많습니다.

문제를 글로 설명하긴 조금 복잡하지만, N개의 사진을 적당히 잘 배치하는 문제였습니다. 정확히 말해서, A개의 세로 사진, B개의 가로 사진이 있는데 세로 사진은 먼저 둘씩 짝을 지은 후 배치해야합니다. 점수는 인접한 사진의 연관도(문제에서 연관도가 어떻게 계산되는지 주어짐)의 총합이었습니다.

가로 사진끼리의 매칭은 서로 태그가 최대한 적게 겹치는 사진끼리 시켜두었고, 이후 사진의 배치는 임의로 시작 사진을 정한 후 연관도가 가장 높은 사진을 그리디하게 이어붙이는 식으로 정했습니다.

즉, 가로 사진끼리 매칭하는 프로그램과 사진을 이어붙이는 프로그램을 따로 만들어 이 둘을 합칠 수 있게 했습니다. 두 프로그램 모두 시간복잡도가 $O(N^2)$이고 $N$은 최대 10만이었기 때문에 결과를 찾기까지 대략 5-10분 정도가 걸렸습니다.

이렇게 간단한 아이디어로 104만점 정도를 얻을 수 있었고, 시간이 충분했다면 개선점을 더 찾을 수 있었겠지만 새벽이라 다들 머리가 잘 안돌아가서 그런지 사진을 이어붙이는 그리디한 프로그램은 한 70분만에 완성시켰으나 가로 사진끼리 매칭하는 프로그램이 대회 종료 30분 전에 완성이 되어서(정확히 말해 코드를 짜긴 짰는데 오류가 있었고 그 오류를 굉장히 늦게 찾았습니다ㅠ) 별 다른 것을 해보지 못하고 그대로 대회가 종료됐네요.

프리즈 기준으로 24등이어서 아주 살짝 기대를 했지만 결론적으로는 73등으로 마무리되었습니다. 한국에서는 2등을 기록했습니다. 세계 73등이라고 하면 별 것 아닌 것 같은데 한국 2등이라고 하면 뭔가 어마어마한 것 같네요ㅎㅅㅎ

더블린은 못가서 아쉽지만 그래도 재밌었던 대회였습니다!