2023년 해커컵 후기

어제 해커컵 티셔츠가 무사히 도착한 기념 및 오랫동안 귀찮아서 글을 쓰지 않았다는 죄책감에 더불어 오랜만에 글을 쓰게 되었습니다. 최종 등수는 Round 2에서 1,540등으로 끝났습니다만 짧게나마 후기를 남겨볼려고 합니다.

최종 등수... 2000등 내로는 들어서 티셔츠는 받았습니다!

 

제가 PS에 맛을 들리기 시작한게 작년이었습니다. 그러다가 좀 속도가 붙기 시작한 시점이 11~12월 쯤이었는데 당시에는 이런 대회가 있는 줄 몰랐습니다. 그래서 올해도 열게 된다면 꼭 참여해보고 싶은 대회중 하나였습니다. 그런데 Meta 주관인 해커컵 말고도 Google 주관인 코드잼이 올해부터 안 열린다길래 '혹시나 이 대회도...?'라는 생각이 들어서 좀 아쉬웠습니다. 실제로 작년에는 8월 말에 열렸는데 아무 소식도 없어서 Google과 마찬가지로 이 대회도 끝났구나 싶었습니다. 그런데...

"우리 아직 정상영업합니다"

이걸 보고 희망이 생겨 꼭 참여하기로 마음을 먹었습니다. 그래서 Round 1,2가 새벽 2~5시라도 열심히 풀어보았습니다.

그전에 대회가 어떤식으로 흘러가는지 설명해보겠습니다. 코드포스나 그런 곳과는 좀 많이 다르게 흘러갑니다.

 

먼저 제가 현재까지 참여한 대회는 주로 아래와 같이 흘러갑니다.

1. 문제를 읽는다.

2. 솔루션을 만들어내는 코드를 짜서 제출한다.

3. 맞은지 틀렸는지를 확인한다. 틀렸으면 다시 짠다.

 

그런데 해커컵은 좀 복잡하게 제출합니다.

1. 문제를 읽는다.

2. 솔루션을 만들어내는 코드를 짠다.

3. 샘플 테스트 케이스를 돌려서 정답들을 따로 텍스트 파일로 추출한다.

4. 3번에서 추출한 텍스트 파일를 먼저 제출해본다. 만약에 다시 코드를 짜야하고, 아니면 5번으로 넘어간다.

5. 실제 테스트케이스가 압축파일로 주어진다. 그리고 압축파일에는 비번이 걸려있다.

6. 비번을 받는 버튼을 누른 순간부터 6분 타이머가 시작된다. 6분 내로 실제 테스트케이스를 돌려서 정답을 텍스트 파일로 추출하고 추출한 텍스트 파일 및 사용한 소스코드를 제출해야한다.

7. 제출이 성공적으로 되었으면 Submitted라는 표시가 뜬다. 정답인지 아닌지는 대회가 끝나고 나서야 알 수 있다.

 

이렇게 좀 많이 복잡한 과정을 거칩니다. 특히나 6분 타이머 내로 정답 코드 및 텍스트 파일을 제출하지 못하면 영영 다시 제출할 수 없는 것이 특징인 것 같습니다. 정답인지 아닌지를 안 알려주는 건 삼성 B형과 비슷한 것 같기도 하구요. (삼성 B형도 테스트 케이스 반 개만 주고 반 개는 숨겨서 최종 정답이었는지 아닌지는 나중에야 알 수 있습니다.) 아무튼 이러한 특성을 설명하였으니, 이제부터 각 라운드에서 몇 등을 했는가와 어떤 문제들이 있었는지를 간략하게 회고해보겠습니다.

 

Practice Round - 4,239 등 (Score : 0/100)

어차피 한 문제도 안 풀어도 Round 1에 들어갈 수 있다길래 별 생각도 하지 않았고 당일에 대회가 있었다는 것도 까먹어서 안 쳤습니다. 그런데 Round 1에서 해커컵의 풀이 절차가 이렇게나 복잡한 것을 알았다면 좀 연습해둘껄 그랬습니다. (나중에 연습으로 제출이 가능하긴한데 실제 라운드랑은 좀 많이 다르더라구요...)

 

Round 1 - 1,491 등 (Score : 40/100)

A, B1, C1, C2번을 풀었습니다. 특이사항으로는 첫 한 시간동안 서버의 오류때문인지 제대로 문제를 풀 수가 없었습니다. 저도 A번을 읽고 풀려고 했는데, 샘플 테스트케이스 정답을 제출하는 버튼이 먹통이라서 당황했었습니다. 저만 그런게 아니라 다른 사람들도 같이 겪고 있었던 문제였고 어느 분은 심지어 샘플 테스트케이스조차 제대로 다운이 안 되는 상황이었습니다. 그러한 난리통이 있어서 그런지 대회도 30분 연장되었고 원래 기억상으로는 5,000등까지만 Round 2로 올라갈 수 있었는데, 이번에는 한 문제만 풀어도 올라갈 수 있었습니다. 그래도 제출한 결과를 바로 알 수도 없기도 하고 이번 기회에 대회 문제 제출 방법에 익숙해질 겸 최대한 많이 풀어보았습니다.

 

A. Here Comes Santa Claus

엘프들을 그룹으로 묶는다면 제일 떨어진 두 엘프의 평균에 해당되는 지점에서 만나게 됩니다. 또한 산타의 이동거리는 항상 제일 첫 번째 그룹이 만나는 지점부터 제일 마지막 그룹이 만나는 지점간의 거리가 됩니다. 따라서, 산타의 이동거리를 최대로 할려면 제일 첫 번째 그룹이 만나는 지점과 제일 마지막 그룹이 만나는 지점간의 거리를 떨어뜨려야 합니다. 5명이 아니라면 항상 맨 첫 번째 그룹은 맨 앞의 2명, 마지막 그룹은 맨 뒤의 2명으로 묶어주면 됩니다. 5명일 때는 중간의 한 명이 둘 중 한 그룹으로 꼭 소속되어야 하므로 앞 그룹으로 묶었을 때와 뒤 그룹으로 묶었을 때 어느 거리가 더 먼지 계산 해주면 되었습니다. 

 

저는 처음에 풀었을 때 만나는 지점이 그룹의 속한 모든 엘프들의 지점에서 평균인 줄 알았는데, 그게 아니어서 약간 헤맸었던걸로 기억합니다.

 

B1. Sum 41 

a = 1 * a 인 사실을 잘 활용한다면 결국에는 특정 값의 곱에 대한 합을 41 이하로 나타낼 수만 있다면 1을 계속 더 곱해주면 41까지 채울 수 있으니 가능하다는 사실에 도달할 수 있습니다. 또한, a와 b가 2 이상이라면 a * b >= a+b 이라는 사실도 활용한다면 특정 값을 최대한 여러 값들의 곱으로 나타내면 해당 값들을 모두 더한 값이 특정 값을 인수분해 했을 때 결과들의 합 중 최소가 됨을 알 수 있었습니다. 그래서 이를 활용하여 주어진 값을 소인수분해 했을 때의 결과를 모두 담고 합이 41 초과면은 불가능하다고 판단, 미만이면은 될 때 까지 1을 계속해서 추가하는 방법으로 풀었습니다. 추가 조건으로는 주어진 값을 여러 값들의 곱으로 나타낸 결과의 길이가 최대 100까지라고는 했는데, 상식적으로 곱했을 때의 값이 최소 1이므로 최대 길이는 41밖에 안 되니 무의미한 조건이었습니다.

 

B2. Sum 41

이 문제는 대회 당시에 어떻게 풀어야 할지 아에 감이 안 와서 포기했던 문제입니다. 그래서 과감히 포기하고 C1으로 넘어갔습니다.

 

C1. Back in Black

일단 제일 앞에 켜져있는 값은 항상 눌러주어야 한다는 관찰을 하였고, 그래서 이 문제가 그리디일 가능성이 매우 높을 것이라 짐작했었습니다. 그러고는 정확히 어떻게 풀었는지는 기억이 안 나지만, 코드를 살펴보니 제일 처음에 꼭 눌러야 했던 버튼들을 파악하였고, 쿼리들에 따라서 해당 버튼이 몇 번이나 눌러지게 되었는지를 파악했습니다. 이후에 정답은 그냥 각 버튼 별로 짝수번 눌러지는 가를 판단하여 풀었습니다.

 

C2. Back in Black

 이번에는 쿼리별로 결과를 구해야했는데, 어차피 처음에 꼭 눌러야 했던 버튼들만 누르는게 최적이므로 해당 버튼들을 눌러주었다면 최소 횟수 - 1, 아니면 +1 하는 방법으로 구할 수 있었습니다.

 

D. Today is Gonna be a Great Day

1,000,000,006을 곱해주는 게 결국에 -1을 곱해주는 것과 동치라는 것을 파악하였고, 그리고 쿼리 구간에 따라서 레이지 세그먼트 트리를 활용하여 -1 곱하는 것을 반영해주는 것까지는 생각을 했는데 어떻게 -1을 곱해주면서 최댓값도 같이 관리할지가 생각이 안났기도 했고 너무 늦은 시간이라서 포기했었습니다.

 

Round 2 -  1,540등 (Score : 17/100)

A1, A2만 정답을 받았습니다. B번은 혹시나 하는 마음에 제출해보긴 했는데 틀렸습니다. 

 

A1. Ready, Go (Part 1)

플러드-필을 구현하여 각 하얀 돌들을 한 그룹으로 묶어주고, 해당 그룹별로 인접한 칸들 중 빈 자리가 딱 한 군데가 존재하는지를 파악하는 문제였습니다. 약간 구현 실수가 있어 시간이 좀 지체되었긴 했지만 그래도 22분만에 풀어냈습니다. (특히나 방금전 스코어보드를 확인해보니 제 점수가 딱 티셔츠를 받을 수 있는 2,000등 컷이어서 시간 차이로 못 받아냈을 수도 있었겠네요...)

 

A2. Ready, Go (Part 2)

A1과 구현에 더불어서 각 그룹별로 크기 및 인접한 칸들 중 빈 자리가 있는 좌표를 저장하여 풀었습니다. 플러드-필까지 돌린 후에 인접한 칸이 한 개라면 해당 칸에 놓으면 해당 그룹의 크기만큼의 돌들을 잡을 수 있다는 것을 표기해두었고 그 중 최댓값을 정답으로 제출하였습니다.

 

B. Meta Game

뭔가 느낌상으로는 문자열 문제 같았었습니다. 결국에는 문자열을 계속 돌렸을 때에 Palindrom을 이룰 수 있는 지를 물어보는 문제 같았었는데... 제가 문자열 알고리즘을 잘 모르기도 해서 한 번 찾아보니 매내쳐 알고리즘 같은 게 있긴 하더라구요. 그런데 해당 알고리즘을 대회 시간내에 익히기에는 너무 부족했었습니다. 뭔 문제인지 잘 모르겠었어요...

 

C. Wiki Race

문자열들과 그래프가 주어져서 풀기 싫었습니다. 그리고 구현량도 많아 보였구요. B에 올인했었습니다.

 

D. Tower Rush

뭔가 게임이론 관련 조합론 문제같아서 걸렀는데, 이제 솔루션을 보니 포함-배제원리, 뫼비우스 함수, 베주 항등식 등의 단어들이 나오는 것을 보니 거르길 잘 한 것 같습니다.

 

아무튼 이렇게 첫 해커컵에서 2,000등 내로 들어가서 셔츠도 받았습니다. 입어보았는데 매우 괜찮았습니다. 아마도 복학한다면 기숙사에 들고갈 것 같네요. 이상 2023년 해커컵에 대한 후기였습니다. 내년에도 꼭 참여해서 티셔츠를 받을 수 있으면 좋겠네요.