TL;DR : 로컬의 문제점을 깨닫지 못하고 폭사(…)
페이스북 해커컵이 끝났다. 구글 코드잼 본대회는 대회 당시 인터넷을 쓸 수 없는 환경(…)에 있어서 아쉬운 마음이었는데, 다행히 해커컵은 일정이 맞아 모두 참가할 수 있었다. 생각치 못한 실수로 Round 2에서 탈락했지만 각 라운드를 간단히 요약해봤다.
Qualification Round
당시 아직 ‘전직’을 한 상태가 아니었지만 주말이라 외출을 할 수 있었다. 대전의 한 PC방에서 파이썬3을 다운받아 대회를 진행했다.
Friends 스코어보드를 보니 익숙한~~(+군대에 있어야 할)~~ 이름이 보였는데 알고보니 사지방에서 대회를 진행했다고 한다. 구닌 둘이 제일 먼저 대회함 문제 자체는 크게 어렵지 않았고, 일찍 일어난 덕인지 패널티에서 큰 이득을 봐 (별 의미는 없었지만) 등수 뻥튀기를 경험할 수 있었다.
p.s. B번은 연산자 우선순위를 이상하게 정의한 문제였는데, 입력받는 부분을 제외하면 O(1)로 풀리는 퍼즐문제에 가까워서 그리 마음에 들진 않았다.
Round 1
대회 시점이 일요일에서 월요일로 넘어가는 밤이었고 다음날 출근해야 했던 터라 걱정이 됐다. A,B번을 제출하고 끝낼까 싶었지만 대회 종료까지 정답 여부가 공개되지 않아 혹시나 하는 마음에 C번까지 건드려 봤다. 다행히 parametric search를 이용한 풀이가 금방 떠올랐고, 결과적으로 A B C 모두 정답으로 1라운드를 통과했다.
Round 2
이 단계에서 500등 안에 들면 티셔츠를 받을 수 있었다. 학부 재학 시절 코드잼이나 해커컵같은 대회들과는 연이 없던 터라 이번만큼은 티셔츠를 받겠다는 목표가 있었다. 결과부터 말하자면 실패했다(…)
A는 조건에 맞는 그래프를 construction하는 문제였다. 대략적인 윤곽은 그려졌지만 ‘설마 이게 답일까’라는 생각에 잠시 접어두고 B를 읽어봤다. 얼마 전 읽어봤던 Euler Tour가 생각났고, 구체적인 알고리즘이 떠오르자 A를 마저 코딩하는 쪽이 나아보였다.
A 제출이 끝난 후 B 풀이에서 부족한 점이 없는지 살펴봤고, euler tour와 함께 크기가 작은 서브트리(=depth가 깊은 노드)부터 따지면 충분히 해결할 수 있을 것 같았다. 예제가 나오는 걸 확인하고, 입력 파일을 다운받아 자신있게 돌려보니 코드가 터졌다(…) 처음 몇 번은 현실을 받아들이지 못하고 아인슈타인의 명언을 그대로 따랐다.
“미친 짓이란, 똑같은 일을 반복하면서 다른 결과를 기대하는 것을 말한다. “
다시 생각해보니 euler tour를 하면서 트리를 dfs로 순회하는 부분이 있었다. 스택 사이즈 제한이 없는 대부분의 채점서버와 달리 내 노트북에선 스택 메모리 사이즈에 제한이 있을 터였고, skewed된 트리에서는 연속된 재귀호출로 인해 스택이 넘칠 수 있다는 사실을 깨달았다. 급하게 g++ 스택 사이즈 제한 해제 같은 검색어로 검색을 시도했다. 많은 팁이 있었지만 대부분 리눅스 상에서 ulimit -s를 사용하거나 Visual Studio에서만 적용 가능한 내용이었고, MinGW로 윈도우에서 g++ 설치해 쓰는 과거의 나를 원망하며 제출란이 Expired로 바뀌는 것을 지켜볼 수밖에 없었다..
p.s. 대회가 끝나고 dfs 부분을 수정해 다시 돌려보니 맞았다고 뜬다(…) 6분동안 검색 대신 STL stack을 사용해 코드를 바꿨으면 어떨까라는 아쉬움이 남지만 이미 지난 일 뭐 어쩌겠는가ㅠ