Google Hash Code 2020 참가 후기

생애 처음으로 Google Hash Code에 참가했습니다.

저는 import_torch_as_tf 라는 이름의 팀으로 김민철, 김상범 님과 함께 참가했습니다.

최종 26,282,007점이라는 점수로 세계 1,119등, 한국 24등 이라는 다소 저조한 성적을 냈지만, 그래도 나름대로 재밌었습니다.

 

각 문제에 대해 저희 팀의 풀이를 소개하자면, 다음과 같습니다.

스포일러가 될 수 있으니 주의해주세요!

 

B - read on / 5,822,900

데이터를 살펴보면 sign up time 순으로 출력하면 해결할 수 있음을 알 수 있습니다.

C - incunabula / 5,521,060

Library를 sign up time이 작은 순으로 정렬하고, library 안의 책들을 그리디하게 정렬하면 충분한 보상을 받을 수 있습니다. 저는 그 후 그리디한 랜덤 스왑을 몇 번 더 해서 점수를 소폭 올렸습니다.

D - tough choices / 5,028,530

To be updated

E - so many books / 4,593,191

데이터의 특성을 파악하지 못해 결국 휴리스틱을 이용해 그리디하게 골라주었습니다. 휴리스틱에 사용되는 상수의 경우 최적화 하여 local maximum solution에 다가가기는 했습니다.

F - libraries of the world / 5,316,305

Library 및 book의 정렬 순서를 하나의 상태로 보고, 상태 간의 전이 연산으로

- 두 library의 순서를 바꾸거나

- 한 library내의 두 책의 순서를 바꾸는

것을 생각해봅시다. 두 상태 간의 거리를 이동하기 위한 최소의 연산 횟수로 정의합시다.

저희 팀은 그리디 알고리즘을 통해 적당히 좋은 상태에서 시작해 거리가 특정 값 이내인 랜덤한 상태를 탐색하고, 더 좋은 상태이면 이동하고, 아니면 머무르는 간단한 방법을 통해 약 531만점을 받았습니다.