Google Hash Code 2020 후기

부추전 고양이

boots jeon cats는 이런 사람들이 모여 만든 팀입니다.

• ryute, 고려대 아기호랑이, 랜덤과 휴리스틱을 사랑함
• Lawali, 고려대 석유호랑이, 랜덤과 휴리스틱을 혐오함
• cloneofsimo, 고려대 어른호랑이, 아무튼 알고리즘 시작한지 한달 반 지남
• junie, 서울대, 왜 설대인데 고대 사이에 끼어 계십니까? :blobaww:

개인적으로 junie님하고 꽤 많이 친하기에, 구글 해시코드에 나가자는 뜻이 맞아 2인 팀이 결성되었습니다. 그 후 연습을 빙자한 맥주 마시기 행사를 가진 다음 사람이 많을수록 무조건 이득이라는 것을 확인하고, 대충 버스를 태워줄 수 있을 것으로 보이면서 할 것도 딱히 없어 보이는 라왈리를 섭외했습니다. 마지막으로 인원수를 대충 때워야 할 것 같다는 생각을 하던 중 대충 조건이 맞아 보이는 cloneofsimo님을 끌고왔습니다. 알고리즘 코딩 경험이 많이 부족하신 게 걸리긴 했지만 뭐 18세 이상이셨고, "그 고등학교" 학생이면 와서 트롤할 일은 절대 없을 거라는 나름의 휴리스틱이 있기도 했습니다.

왜 팀 이름이 부추전 고양이인지는 저도 잘 모르겠습니다. 대회 전날 진행한 연습(Practice Round)에서 제출을 해보기 위해서는 팀을 꾸려야 했고 그래서 팀명을 급하게 정해야 했습니다. 팀명을 고민하다가 갑자기 부추전 얘기가 나왔고, 제가 고양이를 정말정말 사랑하기에 그냥 붙여서 부추전고양이, boots jeon cats가 되었습니다. (공식 로마자 표기법을 지키지 않은 것은 의도된 사항입니다.)

연습

저는 연습을 꽤나 좋아하는 편입니다. 다른 해시코드 팀들을 대충 둘러봤을 땐 연습을 아예 안 하는 팀도 꽤 있는 것 같았지만 미리 문제의 성격을 보고 어떻게 행동해야 할 지 미리 생각해 두는 건 대회에 있어서 엄청나게 중요한 요소라고 생각하기 때문에, 총 3차례의 연습을 진행했습니다. 한 사람이 추가될 때마다 한 번씩 진행했네요. 저 같은 경우에는 이 연습을 진행하면서 문제가 복잡할 때 그리디 코드를 직접 코딩하는 것(그리고 뇌절해서 1시간 30분을 꽁으로 날리는 것)보다 아이디어나 최적화 코드를 넘겨서 점수를 긁는 것을 우선으로 해야겠다는 생각을 했습니다. 데이터 분석하는 것이 상당히 중요하다는 것도 알 수 있었고요. 과거 문제에서 현재 문제로 넘어올수록 모든 테스트케이스에 대한 일반적인 해법보다, 각 테스트케이스에 적용되는 특수한 해법을 코딩하는 것이 더 중요해지고 있다는 것을 느꼈습니다. 이러한 여러 감상들을 가지고, 본 대회에 임했습니다.

폭 풍 전 야

구글 해시코드 2020은 한국 시간으로 02월 21일 새벽 2시 반부터 6시 반까지 진행되었습니다. 매우 늦은 시간대라 저 같은 경우에는 잠을 미리 자 두었고, 다른 분들도 이런 새벽 시간대에 익숙하지 않으신 분들은 미리 모종의 대책을 세우셨다고 들었습니다. 전 최근 3일동안 해가 떠있는 시간에 깨 있던 시간이 얼마 되지 않았기에 큰 상관은 없었습니다. 뭔가 새벽에 배가 고플 것 같아서 치킨을 사두기도 했는데, 결과적으로는 입에도 대지 못했습니다. ㅠㅠ

대회 시작 약 30분 정도 전에 와서 디스코드로 수다를 떨었습니다. 그리고 30분이 지나고 나서 스트리밍을 같이 보고 (사실 이때는 대회가 3시간 45분이 아니라 4시간인줄 알았습니다) 문제 디스크립션을 딱 펼쳐보았습니다. 진짜 이때까지 정말 떨려서 숨도 제대로 못 쉬었던 것 같습니다. 사실 연습 때 정말 많은 트롤링을 했거든요...

대회 시작 이후

문제가 다른 연습 때 읽었던 것 보다 훨씬 직관적이고 짧아서 너무 좋았습니다. 문제를 요약하면 구글 북스 프로젝트를 진행하는데, 이를 위해서 도서관을 등록하고 도서관에서 책을 스캔해야 합니다. 도서관은 한 번에 하나씩만 등록할 수 있으며 등록에 필요한 기간이 모두 다르고, 등록이 끝나면 도서관마다 정해진 수만큼 하루에 책을 스캔할 수 있습니다. 스캔한 책의 종류에 따라서 점수를 얻습니다. 단, 같은 종류의 책을 다른 도서관에서 여러 번 스캔한다고 해서 점수가 오르는 것은 아닙니다! 테스트케이스는 예제를 포함해서 총 6개였습니다.

저희는 대회 중에 한 자리에 모이지 않고 Discord 음성채팅을 이용해서 소통을 진행했기 때문에, 대회 중에 누가 무엇을 했는지는 정확하게 파악할 수 없습니다. 대략적으로 설명하자면 제가 B를 잡았고(단순 정렬 후 그리디), 라왈리가 C를 잡았고, 시모님이 휴리스틱을 짜면서 D랑 F를 잡았고, 그 외에도 모두가 E를 잡으면서 같이 최적화 작업을 했던 것 같습니다. 처음에 잠깐 40등대였다가, 계속 뭔가 의미있는 시도를 성공시키지 못하면서 200위권 정도에서 계속해서 진동했습니다. 초반에는 주니의 야매 그리디로, 후반에는 시모님의 가중치 있는 휴리스틱으로 적당히 점수를 올려갔고 중반에는 냅색과 MCMF를 적절히 적용하면서 아주 조금씩 점수를 올렸던 것 같지만, 다른 팀들한테 계속 따라잡히는 일이 빈번했습니다. 한 몇 만점씩 느리고 꾸준히 올랐던 것 같습니다.

프리징 이후에도 크게 변하지는 않았는데, F와 같은 테스트케이스에서 휴리스틱 상수최적화를 하면서 아주 조금씩 오르는 것이 전부였습니다. 저희 팀의 등수를 뒤집어 놓았다고 생각되는 기점은 E에서 나왔는데, E에 적용된 휴리스틱이 굉장히 별로라고 생각했기에 제가 새로운 휴리스틱을 짜서 적용시켜 보았습니다. 점수가 갱신되지는 못했지만 기존의 휴리스틱에 라왈리의 MCMF 최적화를 더한 것과 비슷한 점수가 나오자, 여기에 MCMF를 끼얹으면 조금은 점수가 오를 것이라고 생각해서 전달했습니다. 이때가 대회 종료 3분 30초 전이었습니다.

라왈리가 제 휴리스틱으로 만든 output에 MCMF를 끼얹어서 순서가 유지될 때의 local optimum을 구해냈고, 이 결과가 기존의 결과보다 약 15만점 이상의 개선을 이뤄내며 27x대에 진입하게 됩니다. 정확히 대회 종료 30초 전이었습니다!!

결과

boots jeon cats는 다음과 같은 성적으로 세계 61위, 한국 2위를 달성하게 됩니다!

A - 21 B - 5,822,900 C - 5,639,447 D - 5,028,790 E - 5,200,905 F - 5,322,233

총점 27,014,296 점

2등이다!!!

잡설

사실 라왈리가 없었으면 한국 2등은 커녕 한국 10등 안에도 들지 못했을 것 같습니다. 물론 다른 팀원들도 매우 잘해주시긴 했지만, 라왈리의 캐리력을 따라갈 수 없습니다.

• 꽤 어려운 개념을 요구하는 알고리즘을 구데기같은 복잡성을 자랑하는 해시코드 문제에 잘 버무려냅니다.
• 코딩에서 뇌절 안하고 굉장히 빠른 속도로 결과물을 만들어 냅니다. 보통 유의미한 개선을 가져옵니다.
• 혹시 버그가 있더라도 디버깅을 거의 하지 않고 문제를 항상 고쳐냅니다. 버그가 생기는 순간 그날 대회가 망해서 한번 짤 때 무조건 제대로 짜야 하는 저와는 대조적입니다.

사실 제가 해시코드에서 한 가장 큰 역할은, 휴리스틱이나 랜덤 아이디어 제공이 아닌 라왈리 섭외가 아니었을까 싶습니다. 한 가지 아쉬운 점은 이번 대회에서 라왈리가 냅색+그리디로 C를 밀었는데, 모두가 이 솔루션이 optimal에 가깝다고 생각하고 건드리지 않아서 5만점 가량을 날려버렸다는 점입니다. 이걸 먹었으면 유럽에 갈 가능성이 있었습니다!

급하게 데려온 시모 선배님은 예상보다 자신 몫을 굉장히 잘해주셨습니다. 보통 수학 하다가 알고리즘으로 넘어오는 사람들 특징이 휴리스틱에 굉장히 약하고 결정론적 풀이를 사랑한다는 점인데, 그런 것 치고는 이런 류의 문제에 익숙하게 접근해서 풀어내시는 모습이 인상적이었습니다. 제가 하자고 한 연습이 도움이 되어 이런 결과가 나온 것이었다면 좋겠습니다.

주니는 원래 항상 무난하게 잘 해줬으니까 딱히 언급할 게 없습니다. 그냥 잘해요!

저는 모든 연습에서 한 게 없었고, 이번 대회에서도 한 게 없습니다. 제 역할은 잘 하는 사람 3명을 대충 어떻게 잘 모아서 팀으로 엮은 것이고, 그 대가로 한 자리를 얻어탄 것이라고 생각하고 있습니다. 승차감이 아주 편안했습니다. 만세~

마무리하며

사실 조금만 더 하면 유럽에 갈 수 있었는데 그렇지 못한 것에 상당히 아쉬움이 남습니다. 그럼에도 불구하고 대회 중에는 얼마나 저희 팀이 부족한 지 알 수가 없으니까 결과론적인 생각은 내려놓기로 했습니다. 급하게 팀을 모아서 급하게 대회를 쳤음에도 수많은 국가대표 함유/고인물 함유 팀을 누르고 한국 2등을 할 수 있게 만들어 준 우리 팀원들에게 무한한 감사와 경의를 표합니다. 마지막으로 매우 높은 확률로 본선에 진출할 것으로 보여지는 한국 1등 78-9(Sixty Nine...) 팀이 유럽에 국위선양을 넘어 국뽕을 널리 퍼트릴 수 있기를 희망합니다. 너무 졸려서 글에 부족한 점이 있으면 나중에 보완하고 수정하겠습니다. 내년에 봅시다~