Google Hash Code 2021 : Team Little Piplup 준비과정

이 글은 올해 해시코드를 준비하는 과정 등에 대한 이야기이고, 해시코드 2021에 Specific한 (문제 등) 은 다음 글(링크에서 다룹니다.

내년에 해시코드를 준비하려는 분들이 읽었을때 재밌게 쓰고 싶었는데 어떤지 모르겠네요. :(

• Google Hashcode
• Team Little Piplup
• Preperation
  • 전략
  • 작년 팀연습들
  • 팀연습 : 2020 Hashcode WF

Google Hashcode

Google Hashcode는 구글에서 개최하는 Coding competition 중 최적화와 휴리스틱을 겨루는 대회입니다. NP한 문제가 주어지고, 이 문제에 대해 좋은 휴리스틱과 적절한 알고리즘적 최적화를 통해 주어진 데이터셋에서 좋은 점수를 받는 경쟁인데, 모든 데이터셋이 공개되기 때문에 데이터셋의 성질을 잘 활용한다거나 하는, Data science틱한 면이 조금 있다고도 할 수 있겠습니다.

이런 형태의 대회는 기존의 PS와는 또 다르지만, 필요한 스킬셋은 어느정도 비슷하고, 최상위권 레벨에서는 기존 PS 스러운 테크닉들이 유의미합니다. PS 실력과 매우 높은 상관관계가 있지만, Hashcode 형 대회에 특히 강한 팀들도 있습니다.

문제가 상당히 Real-world 스럽게 출제되며, 실제로 Google Loon 같은 구글의 product와 깊은 연관이 있습니다. 문제를 풀다 보면 뭔가 진짜 실제로 유의미한 문제를 해결하는 느낌을 받기도 합니다.

Team Little Piplup

이 팀은 2019년도 ICPC를 기점으로 저와 Coffeetea, DHDroid 로 출발했습니다. 이후 두 사람이 병역특례를 위해 휴학을 하게 되었는데, 휴학생은 ICPC 본선 출전권이 없기 때문에 제가 다른 팀을 찾게 되었습니다. (결과적으로, 서울대에서 본선에 진출하는 난이도를 생각해 보면 별로 그럴 필요가 없었다는 생각이 들기도 합니다만…) 2020년부터 그 자리는 병특중이었고 저랑 계속 PS를 같이 공부했던 Dlwocks31 이 들어가게 되었습니다.

Dlwocks31이 들어간 시점의 팀명은 Army Piplup으로 개칭되었고, 2020 ICPC 예선에서 11등을 거두는 놀라운 실력을 보여주었습니다. 코드포스 레이팅 (Max)를 기준으로 dlwocks는 2200++, 저는 2100, Coffeetea와 DHDroid는 1900인데 dlwocks31은 몰라도 저는 거품레이팅이었기 때문에 거품이 꺼진 지금은 1900 정도, 잘쳐주면 퍼플 중간쯤의 CP 실력을 가지고 있는 것으로 보입니다.

• Gratus907 : 수학적인 문제에 비교적 강하고, 말리지 않을때까지는 구현이 빠르지만 말리면 한없이 말리는 경향이 있습니다.
• Dlwocks31 : 가장 C++ 구현을 깔끔하게 잘 하고, 구현에서 덜 말리는 편입니다.
• DHDroid : Constructive한 문제에 매우 강하고, 관찰을 정당화 (증명) 하는 능력이 뛰어납니다.
• Coffeetea : 그리디하거나 휴리스틱한 관찰, 대략적인 경향성의 파악에 강합니다. 뭔가 문제에 빙의하는 특성이 있어서 글쓸때 Coffeetea의 표현을 많이 빌리게 됩니다 :)

Preperation

Hashcode 대회를 준비하기 위해서 올해는 많은 노력을 기울이지 못했습니다. 작년에는 비교적 많은 노력을 했는데, 여러가지 교훈을 얻었습니다. 작년 대회 후기는 제 티스토리 블로그에서(링크) 볼 수 있습니다.

• 문제의 구현량이 상당히 많아서, 구현에서 말리면 상당히 힘듭니다. 기본적으로 dlwocks31이 구현이 가장 덜 말리니까 전체적인 구현을 맡되, 필요하다면 언제든 구현에 저나 다른 팀원들이 참여해야 합니다.
• Parameter Tuning이 많은 도움이 됩니다. 파인 튜닝을 자동화하는 코드를 미리 준비했는데, 이를 위해서는 신속하고 정확하게 채점을 받고 싶습니다.
  • 채점을 웹 환경에서 제출하는 데 많은 시간이 걸립니다. 이는 상당히 불편하기 때문에, 경우에 따라 채점기를 짜는 것이 의미가 있습니다.
  • 채점기를 작성하는 것의 단점은 당연하게도 4시간이라는 짧은 대회시간에서 한명이 빠져서 1시간정도를 채점기에 써야 한다는 점입니다.
  • 그럼에도 불구하고, 채점기 작성을 통해 문제 상황을 좀더 깊이 이해할 수 있다는 점, 경우에 따라 채점기의 시뮬레이션 같은 부분들은 본 솔루션에서도 응용할 수 있다는 점이 있어서 고려할만 합니다.
• 결국 상위권(5-10%)에서 최상위권(1%)을 결정하는 것은, (작년에는) 엔드스펙급 알고리즘 최적화였습니다. 구체적으로는, 특정 데이터의 경우 적절한 환원을 통해 3-SAT 같은 문제로 바꿀 수 있었고, 이를 적절한 3SAT 솔버에 먹여서 답을 구한다거나, greedy 대신 MCMF를 쓴다던가 하는 솔루션들이 최상위권을 겨루었습니다. 다시 같은 최상위권 내에서는 Parameter Tuning이 세부등수를 결정합니다.
  • 그래서, 이번에는 상용 NP-Complete Solver들을 준비했습니다. 이런쪽에 비교적 제가 조금더 해본게 많기 때문에, 이것저것 찾아 모으고, 제 최대의 목표는 이거 사실 3SAT인데 를 찾는 것이라고 스스로 생각했습니다. (결국 틀렸습니다)
  • Glucose SAT Solver, Concorde TSP Solver, Google ORTools(LP, Flow, IP) 정도는 세팅되어 있었습니다.
• 생각보다 높은 Computation power가 필요한 경우가 있습니다. 팀원 전원이 i7급 이상의 노트북을 사용했으며 필요할때 사용할 수 있는 i7급 데스크탑 2대가 세팅되었습니다. 카카오 클라우드, 네이버 클라우드 등이 준비되어있었던 다른 팀에 비하면 부족할지도 모르지만 저희가 확보할 수 있는 컴퓨팅 파워는 나쁘지 않았고, 결국 그 무엇도 필요 없었습니다.

전략

1. 첫 1시간 정도, 제가 Grader를 짜기로 했습니다.
2. 그동안, DHDroid와 Coffeetea는 데이터를 분석하기로 했습니다. 예를 들어 그래프 데이터가 주어진다면, 몇개의 허브가 존재하는 데이터인지, Degree-bounded인지 등의 정보가 있으면 일반적인 그래프에서는 상상도 못할 것들이 가능하기 때문에 이런 정보는 정말 필수적입니다. 경우에 따라 이 두명이 어느정도의 그리디한 솔루션을 제공해 줄 것입니다. Grader 작성은 그냥 깡 시뮬이기 때문에, 이 두명의 논의를 제가 어느정도 들으면서 짤 수 있습니다,
3. Dlwocks31이 이때 튜닝가능한 제네릭 솔루션을 작성하기로 했습니다. 이 코드는 나중에 같이 돌아가면서 고치고 튜닝해야 하므로, 비교적 읽기 쉽게 짜야 하고, IO같은 (다른 사람들이 몰라도 되는) 부분들을 분리하기로 했습니다.
4. 이후 2-3시간 동안, 네명이 같이 솔루션을 잡으면서 알고리즘 개선과 파라미터 튜닝을 반복하며 계속 제출하는 방식입니다.

전반적으로 첫 1시간동안 저랑 dlwocks31의 코딩실력에 조금 의존하는 감이 있습니다만, 저희가 할 수 있는 최선이었고 지난 몇년치 예선을 풀어봤을 때는 말이 되는 전략이었습니다. 이정도 복잡도의 구현은 저희 둘은 어떻게든 가능하긴 했었고, 평소 PS때와는 달리 1초의 Strict time limit이 없으므로 set, map 같은 것들을 마구 남용하며 짜도 되긴 합니다.

이 전략은 올해 해시코드에서 한계에 부딪히게 됩니다.

작년 팀연습들

몇몇 해시코드 예선 문제를 작년에 같이 풀어보았었습니다. 그때 위 1-4 전략도 정립했는데, 몇가지 전략적인 튜닝도 있었습니다.

1. 문제의 구현 복잡도가 높다면, 체커를 짜는 것은 별로 바람직하지 못합니다. 이건 2016 Qual라운드의 DRONE이라는 문제에서 느꼈습니다. 해시코드를 준비한다면 꼭 풀어보길 바랍니다.
   반면, 구현 복잡도는 적절한데 Simulated annealing같은걸 박을수있는 문제라면 무조건 체커를 짜야 합니다.
2. 어떤 문제는, 아예 독립적인 두개이상의 알고리즘을 요구한다는 사실을 알게 되었습니다. 예를 들어 그래프 문제에서 어떤 데이터는 Deg-bounded고 어떤 데이터는 다섯개의 허브와 9995개의 가지정점으로 구성되어 있다면, 두 문제는 사실 아예 다른 문제이기 때문입니다. 이경우 구현페이즈가 n배 힘들어지는데, 이를 빠르게 파악해야 하므로 두명이 데이터를 생각보다 많이 분석해야 한다는 결론을 내렸습니다. 구현이 아닌 데이터 분석에 2명을 배정한 이유가 여기 있습니다.
3. 이를 위해 dlwocks31이 구현을 정말 최대한 제네릭하게 짜야 함을 깨달았습니다.

팀연습 : 2020 Hashcode WF

가장 좋은 해시코드 연습셋은 해시코드기 때문에, 작년 해시코드 월파를 같이 돌았습니다. 정말 충격적인 난이도의 문제로 인해 저희 전략의 한계가 느껴졌습니다.

대충 얘기하자면 정말 빡센 구현 문제였고, 대충 시뮬레이션만 성공해도 월파 중간쯤의 점수가 나오는 미친 셋이었습니다. 위 전략이 다음과 같이 실패했습니다.

1. 팀연습때는 온라인 채점을 받을 수 없으므로, 한명을 지정해서 한명이 미리 체커를 짜 옵니다. 제가 체커를 짜 왔는데, 집에서 혼자 체커를 짜는데 일단 1시간보다 훨씬 오래걸렸고, 정확성도 별로 보장되지 않았습니다. 그래도 그럭저럭 말이 되는 것 같았는데 뭐 이부분은 잘 모르겠습니다. 중요한 것은 체커를 1시간 내로 짜지 못했다는 것입니다.
2. 데이터를 분석하고 그리디를 떠올려야 하는데, 그리디하게 뭘 할 수 있을지도 난해했습니다. 지나치게 구현난이도가 높아서, Coffeetea의 장점을 살린 아이디어들이 쏟아졌지만 구현가능해 보이는 솔루션이 없었습니다.
3. dlwocks31이 1시간은커녕 2-3시간에 걸쳐서도 가능한 C++ 코드를 작성하지 못했습니다. 이건 blame할 일은 절대 아닌게, 다른 3명이 잡았으면 하루 종일 짰어도 못 짰을 것입니다.
4. 솔루션이 없으므로 튜닝할 파라미터도 개선할 알고리즘도 코드를 작성할수가 없습니다.

2020 WF를 풀면서, 저희 전략이 dlwocks31의 구현력에 얼마나 의존하는지 깨닫게 되었습니다. 경우에 따라 체커를 던지더라도 이 구현은 피할 수 없고, 이 구현에서 말리면 0점으로 대회를 마무리하는 참사가 벌어지기 때문입니다.

필요하다면 구현을 나누어야 한다는 직감이 들었으므로, 처음으로 이런 대회 중에도 Git을 이용하기로 했습니다. 최대한 같은 파일을 동시에 2명이 만지는 일을 피하면서, 필요하다면 파일을 많이 늘려서라도 코드를 적절히 공유할 필요가 있었기 때문입니다. 여러 파일로 나누어 구현한 다음 합치는 방법을 포함해서, 부족한 구현력을 전략으로 메우기 위한 많은 시도가 있었습니다.