카카오 코드 페스티벌 2018 본선, 8문제 중 6문제 풀린 최고 성적 기록

카카오가 지난 8월 25일 판교 오피스에서 코드 페스티벌 2018 오프라인 본선을 개최했다. 예선을 통과한 64명의 참가자가 경쟁했으며, 본선에서는 총 8문제가 출제되었다.

문제별 풀이 및 난이도

본선 문제는 알고리즘과 자료구조의 심화 지식을 요구했다. 주요 문제들의 풀이 방향은 다음과 같다.

승부 예측: 36가지 경우의 수를 고려하는 완전 탐색으로 해결 가능했다.
카카오머니: 로그 데이터의 모순을 분석해 최대공약수(GCD) 개념을 활용해 금액 단위를 역산하는 문제였다.
섬: 그래프 이론의 절점(Articulation Point) 개념을 활용해 특정 섬 제거 시 연결성 변화를 판별하거나, 평면 그래프의 Flood-Fill을 활용해 포함 관계를 분석했다.
보물 상자 열기: 문자열을 회문으로 만들기 위해 필요한 최소 교체 비용을 선형 시간 O(N)에 계산하는 DP 문제였다.
조용한 생활관 만들기: 트리 구조에서 경로의 비용 합을 최소화하는 문제로, Dynamic Convex Hull과 Small-to-large 기법을 결합해 O(N log²N) 시간에 해결할 수 있었다.
자석 장난감: 그래프에서 Clique 구조를 이용해 노드 제거 순서를 결정하는 문제로, O((N+M)logN) 시간 알고리즘으로 접근했다.
헬리콥터: 직교 다각형 내에서 단 한 번의 사선 이동을 허용한 최단 경로 문제로, 새 영역의 꼭짓점과 삼분 탐색을 활용해 O(N² logN) 시간 복잡도로 해결했다.

본선 결과, 1등은 8문제 중 6문제를 풀었다. 사전 공지된 대로 상위 31명에게 상장 및 상금이 수여되었으며, 작년에 비해 본선 문제의 난이도가 높다는 피드백이 많았으나 참가자들의 열정적인 참여가 이어졌다.