[Google HashCode] 2022 구글 해시코드 참가 후기

결론부터 말하자면..

 

전 세계 10177팀 중에서 663등, 한국 54팀 중에서 15등을 했습니다.

 

첫 출전이고 준비 기간이 2일이었던 것을 생각해보면 정말 좋은 성과를 거두었다고 생각합니다.

 

 

---

대회 소개

 

Hash Code - Google’s Coding Competitions

 

구글의 팀 기반 프로그래밍 경연 대회이며, 구글에서 실제로 직면했던 문제들을 간단하게 모델링한 상황을 해결하는 알고리즘을 구성하는 대회입니다.

 

2인 ~ 4인으로 구성된 팀으로 출전 가능하며, 하나의 문제 상황에 대해 A ~ F까지 각기 다른 input data들이 주어집니다.

 

A ~ F의 각 코드는 달라도 되며, 10분에 50회 제출이라는 제한을 제외하고는 프로그래밍 언어, 라이브러리 사용 등에 아무런 제약이 없으며, 제출 패널티도 존재하지 않습니다.

 

제출 패널티가 존재하지 않아서 일명 점수를 긁어모은다는 전략이 통합니다.

같은 알고리즘에서 상수 값들만 적절히 바꿔가면서 점수를 조금씩이라도 올리는 전략입니다.

 

---

짧았던 대회 준비

 

대회로부터 3일 전에 대회가 열린다는 것을 알게 되었고, SAFFY에서 같이 알고리즘 스터디를 진행하고 있는 친구들을 꼬셔서 팀을 결성했습니다.

 

대회 2일 전부터 규칙에 대해서 읽기 시작한 수준이라 choboyo라는 상대방의 방심을 유발할 수 있을 팀명을 골랐습니다.

 

대회 2일 전에는 각자 기출문제 2개에 대해서 알고리즘을 떠올려보고 더 나은 솔루션을 찾아보는 시간을 가졌습니다.

 

대회 하루 전에는 practice로 공개된 One Pizza 문제를 같이 풀어보면서 역할을 분담하고, 문제를 분석하는 방식 등을 연구했습니다.

 

 

---

자바는 별로다

 

싸피 과정에서 자바를 배우는 만큼 자바를 사용하기로 결정했지만, 휴리스틱을 사용하는 문제들이 많은 만큼 관련 라이브러리가 현저히 부족했기에 좋은 성적을 거두기는 힘들어 보였습니다.

 

일례로 저는 대회 당일 저녁 Google ortools라는 라이브러리의 사용법에 대해 숙지했으나, 이 라이브러리가 c++ 기반으로 작성되어 자바 애플리케이션에서 사용하기 위해서는 JNI를 활용하는 등 복잡한 과정을 거쳐야 했습니다.

 

또한, 데이터 분석을 해서 입력 데이터에 적절한 알고리즘을 구성했다는 참가 후기를 읽고 찾아봤지만, 파이썬과 다르게 자바에서는 데이터 분석 툴도 제한적이었습니다.

 

 

최적화 알고리즘 정리 노트

 

1. linear optimization

objective function과 contraints가 모두 수식, linear expression으로 나타날때


2. contraint optimization

최적화보다는 (objective function)을 찾기보다는 모든 contraints를 만족하는 실현가능한 solution을 찾는 방안
스케쥴링, 계획, 등의 서로 다른 contraints를 가진 도메인에서 활용
N queen, Cryptarithmetic puzzles (숫자가 문자로 암호화) 등의 문제에서 사용

만약 문제에서 linear objective와 linear contraints로 모델이 가능하다면 이 방식이 아닌 linear programming 문제로서 해결하려고 해야하며 반드시 MPSolver를 고려해보라
다만, 경로 문제에서는 linear model로 나타난다 하더라도 vehical routing library로 푸는 것이 최고다


3. mixed-integer optimization

일부 혹은 모든 변수가 정수가 되어야하는 문제이다
Assignment 유형의 문제를 풀 때 사용한다 (해당 직원이 주어진 일에 배정되었는지의 유무를 0, 1로 구분)

- Integer variables : 몇개의 차나 텔레비전을 만들어야 이익을 극대화하는 가에 대한 문제
standard linear optimization problems + added requirement (정수 조건)
- Boolean variables : 0 또는 1로 결정을 나타내는 문제. Xij에서 worker i가 task j에 배정받았으면 1, 아니면 0

MIP solvers는 standard LP 문제에서 임의의 정수 조건만 더해진 경우에 더 적합하다
CP-SAT solver는 boolean 값이 대부분인 문제에 더 적합하다
위의 두 경우 모두 시간적 차이는 없고 개인적인 선호도 차이이다

integer programming 문제에서 또다른 풀이법은 network flow solver를 사용하는 것이다
Min Cost Flow Problem 과 같이 network flow로 풀수 있는 문제라면 min cost flow solver가 위의 두 가지보다 빠르다.
다만 모든 MIP문제들이 network flow로 풀리는 것은 아니다.


4. bin packing

다양한 크기를 가진 물체를 다양한 용량을 지닌 container에 넣는 문제
container의 용량에 한해서 가능한 많은 물체를 넣는 것이 목표이다
knapsack 문제는 bin packing의 특수한 경우로, 단 하나의 컨테이너만 가진 문제이다

간단한 knapsack 문제에서는 컨테이너가 하나 존재한다
- multidimensional knapsack 문제 : 무게나 부피 등 2개 이상의 성질을 가진 물품을 특정 공간을 가진 배낭안에 넣는 문제
사각형의 저장소에 사각형의 박스를 넣는 최적의 방법을 찾는 문제
- multiple knapsack 문제 : 다수의 배낭이 있고 모든 배낭에 최대한 많은 물건을 넣는 것이 목표

가장 잘 알려진 packing 문제중 하나는 bin-packing 문제이다.
동일한 용량을 가진 다수의 컨테이너가 존재하며, multiple knapsack 문제와는 달리 저장소의 수가 고정되어 있지 않다
다만 목표는 모든 물품을 다 담기위해 필요한 최소 컨테이너의 개수를 구하는 문제이다



5. network flows

많은 최적화 문제는 유향 그래프로 나타낼 수 있다
예를 들어 transportation 문제에서 물건을 나르는 철도 네트워크와 같은 문제가 있다
- maximum flow 문제에서 각각의 간선은 최대 용량을 가지고 있으며, 최대한 많은 물품을 이송하는 것이 목표이다

network flows에서의 주요 contraint는 각 간선이 용량을 가지고 있다는 것이다. (고정된 기간에 최대량을 이동시켜야 한다)



6. Assignment

각각의 agent에 특정한 일을 시키면 고정된 비용이 발생할 때, agent의 그룹에 task를 할당하는 문제이다
한명의 agent는 하나의 일만 할 수 있고, 모든 agent는 각각 다른 일을 해야한다
least total cost과 같은 문제이며, network flow의 특수한 경우이다

간선의 부분집합을 이용하며, 각각의 worker들은 중복없이 하나씩 일을 맡게 된다.

MIP solver와 CP-SAT solver를 동시에 사용해서 해결 가능
Linear sum assignment solver나 minimum cost flow solver를 사용하면 더 빠를 수도 있지만, 간단한 assignment 문제만 풀 수 있다.
따라서 복잡한 문제를 풀고, 대부분의 상황에 통용되는 일반적인 solver는 MIP와 CP-SAT이다


7. Scheduling

특정 시간에 일을 수행하기 위해 자원을 배분하는 문제이다
가장 대표적인 예제는 job shop 문제이며, 여러개의 기계가 다수의 작업을 수행하는 문제이다.
각각의 작업은 일련의 task들로 구성되어 있으며, task들은 주어진 순서대로 수행되어야 한다.
또한 각각의 task들은 특정 기계에서만 수행되어야 한다
목표는 가능한 짧은 시간에 모든 작업을 수행할 수 있는 스케쥴을 완성하는 것이다 

예시
- constraints 들과 staffing requirements 아래에 직원 교대 스케쥴을 만드는 것
- 한번에 하나의 작업만 수행할 수 있는 기계들로 최대한 많은 일을 수행하도록 하는 제조 공정 스케쥴링



8. Routing

유향 그래프에서 자동차들이 네트워크를 횡단하는 최적의 경로를 찾는 문제이다
배송 트럭이 택배를 할당받는 문제가 있다
또 다른 예시는 traveling salesperson 문제가 있다

가장 중요한 최적화 중의 하나인 vehicle routing은 vehicles들이 장소들을 방문할 최적의 경로를 찾는 것을 목표로 한다
여기서 최적의 경로란 가장 짧은 거리 혹은 가장 적은 비용이 필요한 경로이다

예시
- 배송을 위해 기사들에게 경로를 할당하는 물류회사
- residential service call을 위해 기사의 경로를 할당하는 케이블 티비 회사
- 승객을 태우고 내려주기 위한 최적의 경로를 기사에게 알려주고자 하는 운임회사

가장 유명한 routing 문제는 traveling salesperson problem(TSP)이다. (특정 장소에 갔다가 다시 돌아오는 가장 짧은 경로를 찾는 문제)
TSP는 그래프로 나타낼 수 있으며, 모든 정점을 지나는 가장 짧은 경로는 하나뿐이다

경로가 많아질수록 문제가 어려워지는데, 10개의 장소만 있더라도 36만개의 경로가 생긴다
장소 20개는 2432902008176640000개의 경로를 가진다

가장 짧은 경로를 보장하기 위해 모든 search를 탐색할 수는 있지만 다루기 힘들다
더 큰 문제에서는 최적화 기술을 현명하게 사용해서 최적의 solution을 찾아내야 한다

TSP의 일반적인 버전은 vehicle routing problem(VRP)이며, 여기에는 다수의 차량이 존재한다
대부분의 경우에서 VRP는 contraint가 존재하며, 각 차량은 최대 weight나 volume 등의 용량이 존재한다

---

대회 결과

 

대회는 한국 시간으로 새벽 2시 45분부터 6시 30분까지 진행되었습니다.

 

Zoom을 통해서 알고리즘에 대해 활발하게 토의하고, 서로의 코드를 보완해주면서 예상보다 높은 성적을 거둘 수 있었습니다.

 

 

Global 663 / 10177

South Korea 15 / 54

 

 

---

후기

 

저희 팀의 준비 기간이 조금 더 길었거나 다른 언어를 사용해서 최적화 라이브러리를 다양하게 사용할 수 있었다면 하는 아쉬움도 들었습니다.

 

처음에는 난이도 있는 문제에 직면해서 다들 긴장했지만, 복잡한 문제를 해결하기 위해 단순한 문제로 쪼개고, contraint에 대한 우선 순위에 대해서 열띤 토론을 벌이는 과정에서 몸은 지치지만 머리는 흥분에 가득차 오히려 잠에서 깨는 듯한 경험을 했습니다.

 

같이 대회에 참여한 대희, 가영, 종민이와 협력을 통해 더 끈끈해지는 느낌을 받았으며, 이후 kickStart 뿐만 아니라 다양한 코딩 대회에도 나가서 경험을 쌓아보기로 했습니다!