카카오 코드 페스티벌 예선전 이야기
함께 축제를 즐겨주신 모든 분들께 감사드립니다!
지난 8월 5일 토요일, 카카오 코드 페스티벌의 온라인 예선이 개최되었습니다. 합병 후 카카오라는 이름으로 처음 열리는 개발자 행사인 만큼, 여러 카카오 크루들이 긴장되지만 신나는 마음으로 대회를 준비했습니다.
이번 예선전에는 총 6개의 문제가 출제되었습니다. 다양한 난이도의 문제를 출제하여 최대한 많은 참가자들이 즐길 수 있도록 하는 데 초점을 맞췄습니다. 출제진이 생각했던 것보다 빠르게 문제를 풀어나가는 참가자를 보면서 뛰어난 실력에 감탄했고, 여러 번 제출했지만 정답 판정을 받지 못하는 분들을 보며 안타까움을 느꼈습니다. 그리고 대회가 끝난 뒤 후기를 통해 어려운 문제였지만 즐거운 경험이었다는 이야기, 특히 문제 안에서 만날 수 있었던 아이유와 카카오프렌즈에 대한 관심을 보면서 뿌듯함을 느낄 수 있었습니다.
이 글을 통해 온라인 예선에 출제되었던 문제와 해설, 그리고 결과를 공유드리고자 합니다. 카카오 코드 페스티벌 예선에 참가해주신 모든 분들께 감사드리며, 향후 카카오와 카카오 개발자 행사에도 꾸준한 관심 부탁드립니다.
문제 설명 및 풀이
카카오프렌즈 컬러링북
- 제출자 1044명
- 정답자 624명
- 풀러 가기
2차원 배열이 입력으로 주어졌을 때, 상하좌우로 연결된 같은 색깔의 영역이 몇 개인지, 그리고 영역의 최대 크기가 몇인지 구하는 문제입니다. 특정 지점에서부터 시작하여 상하좌우의 칸과 현재 칸의 색깔을 비교하여, 색깔이 같은 인접한 칸이 있을 경우 그 지점에서 같은 과정을 반복하는 식으로 영역의 크기를 구할 수 있습니다. (Flood fill을 검색해보세요.)
출제된 문제 중 가장 많은 분들이 푼 문제인데, 경계지점(상하좌우 중 일부가 없는 경우)에 대한 처리를 하지 않은 코드를 제출하여 정답을 받지 못한 분들이 많았습니다.
보행자 천국
- 제출자 857명
- 정답자 417명
- 풀러 가기
왼쪽 위부터 오른쪽 아래까지 도달할 수 있는 경우의 수를 세는 문제로, 동적 계획법(Dynamic programming)으로 풀 수 있습니다. 먼저 다음과 같이 두 개의 배열을 정의합니다.
H[i][j]: i행 j열에서 오른쪽으로 갈 수 있는 경우의 수
V[i][j]: i행 j열에서 아래쪽으로 갈 수 있는 경우의 수
그리고 각 칸의 조건에 따라 배열의 값을 채워갑니다. H 배열을 계산하는 것을 예로 들면, 자유롭게 지나갈 수 있는 칸의 경우 H[i][j] = H[i][j-1] + V[i-1][j], 회전이 불가능한 칸의 경우 H[i][j] = H[i][j-1]입니다. 자동차가 지나갈 수 없는 칸의 경우에는 H[i][j] = 0이 됩니다. V 배열도 비슷하게 채울 수 있습니다.
왼쪽 위부터 오른쪽 아래로 H와 V 배열을 채워나가면 문제에서 원하는 경우의 수를 빠짐없이 효율적으로 셀 수 있게 됩니다.
브라이언의 고민
- 제출자 388명
- 정답자 44명
- 풀러 가기
문제의 조건에 의해, 삽입되는 기호는 총 26가지(알파벳 소문자의 수)이며 각각은 한 번씩만 적용될 수 있습니다. 즉, 각 알파벳의 개수와 위치를 세면 어떤 단어에 어떤 규칙으로 적용되었는지 알 수 있습니다.
기호의 개수가 1개 혹은 3개 이상인 경우, 이 기호는 규칙 1에 의해 추가된 기호임을 알 수 있습니다. 기호의 개수가 2개이면서 사이에 들어간 글자(대문자)의 수가 2개 이상인 경우, 이 기호는 규칙 2에 의해 추가된 기호임을 알 수 있습니다. 기호의 개수가 2개이면서 사이에 들어간 글자의 수가 1개일 때는 규칙 1 혹은 규칙 2가 모두 적용될 수 있는데, 이 경우에도 다음의 유일한 예외를 제외하고는 규칙 2가 적용된 기호로 간주할 수 있습니다. aAbBbCa 즉, 다른 기호의 구간 안에 있는 경우입니다.
즉, 각 기호 별로 개수를 세어, 기호의 개수가 2개가 아닌 경우 규칙 1, 2개인 경우 규칙 2(위에서 설명한 경우 제외)로 적용된 기호로 간주하고 그에 맞게 규칙이 올바르게 적용되었는지를 판단하면 됩니다.
이상의 내용이 출제자가 생각한 풀이인데요, 문제의 복잡도에 걸맞게 다양한 방법으로 푸신 분들이 많았습니다. 2차원 배열을 정의하여 각 부분 문자열 별로 올바르게 해석될 수 있는지를 계산하는 다이나믹 프로그래밍 코드가 인상적이었습니다.
4단 고음
- 제출자 333
- 정답자 108
- 풀러 가기
규칙에 따라 생성된 문자열은 다음의 성질을 가지고 있습니다.
+의 개수는*의 개수의 두 배입니다.i번째*의 위치는3*(i-1)이하입니다. (위치는 0-index) 즉, 뒤에서부터j번째*뒤에는2*j개 이상의+가 있어야 합니다.
그리고 문제를 풀 때 다음의 성질을 사용합니다.
- 같은 길이의 문자열 중 계산되는 값이 최소인 경우는 다음의 경우입니다.
*..*++..++즉, 모든*이 앞에 위치한 경우입니다.*의 개수를k라고 했을 때 이 값은3 ^ k + 2 * k입니다. - 특정한 문자열의
+*를*+로 바꾸면 결과값은2 * 3 ^ l만큼 증가합니다. 이 때l은 변환이 일어나는 위치 뒤에 있는*의 개수입니다. (ex. 가장 뒤의*를 한 칸 뒤로 옮기면 결과값이 2만큼 증가합니다.)
그러면 특정 문자열의 값은 같은 길이의 문자열 중 값이 최소인 경우를 계산하고, 그 문자열과 구하려는 문자열의 차이를 더하면 됩니다. *++*+*+++의 경우를 예로 들면, ***++++++의 값은 33이고, 이 문자열에서 세 번째 *를 세 칸 뒤로, 두 번째 *를 두 칸 뒤로 차례로 옮기면 구하려는 문자열이 되므로 그 값은 33 + 3 * 2 + 2 * (2 * 3) = 51입니다.
특정한 값이 주어졌을 때 그 값을 나타내는 문자열의 수를 구하는 원래 문제로 돌아와서, 입력된 값에 대해 그 값을 나타내는 문자열은 모두 길이가 같음을 보일 수 있습니다. 그러면 입력된 값과 해당 길이 문자열로 얻을 수 있는 최소값의 차를 구하고, *를 옮겨서 그 값만큼의 차이를 얻을 수 있는 경우의 수를 구하면 됩니다. 위의 예제에서는 [2, 3]이 되겠네요 (*를 뒤로 옮기는 횟수) 입력되는 값의 범위가 크지 않기 때문에 가능한 경우를 적절한 가지치기와 함께 전체 탐색해도 시간 안에 답을 구할 수 있습니다.
캠핑
- 제출자 383
- 정답자 114
- 풀러 가기
금방 떠올릴 수 있는 해법으로 모든 가능한 쐐기 조합에 대해 문제의 조건(영역 내에 다른 쐐기가 없음)을 만족하는지를 일일이 계산하는 O(n^3) 해법이 있습니다만, n이 최대 5,000이므로 시간 안에 답을 구할 수 없습니다. (그럼에도 일부 참가자 분들은 최적화를 잘 해서 O(n^3) 코드로 정답을 받으셨습니다..)
먼저 다음과 같은 2차원 배열을 만듭니다.
S[i][j]: x좌표가 [0, (x좌표 중 i번째로 작은 값)], y좌표가 [0, (y좌표 중 j번째로 작은 값)]인 쐐기의 개수
위와 같이 부분합 배열을 구하면 특정 영역 내에 있는 쐐기의 개수를 O(1)에 구할 수 있습니다. 모든 쐐기 조합에 대해 영역 내의 쐐기의 개수가 0인지를 확인하면 됩니다. 부분합 배열을 계산하는 과정, 모든 쐐기 조합에 대해 계산하는 과정 모두 O(n^2)에 실행됩니다.
※ 대회 중 채점 데이터가 문제의 설명과 다른 경우가 있었습니다. 여기에서 공개되는 최종 순위는 해당 오류를 수정하여 문제에서 설명된 조건에 맞는 데이터로만 채점이 진행된 결과입니다.
신비로운 유적 탐험
- 제출자 81
- 정답자 25
- 풀러 가기
두 트리의 최대 공통부분을 찾는 문제입니다. 루트가 지정되어 있기 때문에 차례로 내려가면서 두 트리의 자식을 비교하여 노드 간 대응되는 조합을 찾으면 됩니다.
다음과 같은 함수를 정의합니다.
f(a, b): 첫 번째 트리의 a 노드, 두 번째 트리의 b 노드를 각각 루트로 하는 서브트리의 최대 공통부분의 크기
a를 루트로 하는 서브트리, b를 루트로 하는 서브트리의 최대 공통부분의 크기를 구하기 위해서는 먼저 각 서브트리의 자식 간 모든 조합에 대해 공통부분의 크기를 구합니다. 즉, a1, a2, a3가 a 노드의 자식, b1, b2가 b 노드의 자식인 경우, f(a1, b1), …, f(a3, b2)의 6가지 경우의 값을 모두 구합니다. 그리고 여기에서 최대값을 얻을 수 있는 조합을 찾으면 됩니다.
이 때 이 문제를 Minimum-cost flow 문제로 접근하여 정답을 구할 수 있습니다. Flow graph를 아래 그림과 같이 구성하고, 각각의 capacity를 모두 1로 하되 cost로 각 조합에 대한 결과를 할당합니다. 원래 Minimum-cost flow 문제는 최소 비용의 경우를 구하는 문제이지만 이 문제에서는 공통부분의 크기가 최대가 되도록 조합을 구해야 하므로, cost를 음수로 할당하여 해결할 수 있습니다.
그러면 a 노드와 b 노드를 루트로 하는 서브트리의 최대 공통부분의 크기는 여기에서 구한 최소 비용에 다시 음수를 취하고 1을 더하면 됩니다.
플로우 문제이기 때문에 외부 코드를 사용해서 푼 참가자가 많았고, 서브트리의 자식 간 대응 관계를 구할 때 Hungarian method를 이용하여 푼 분들도 있었습니다.
대망의 결과 발표
그러면 엄청난 경쟁률을 뚫고 본선에 진출할 참가자를 발표합니다! 본선 참가자를 발표하기 전에, 채점 기준에 대해 다시 한번 설명드리겠습니다.
- 모든 문제의 배점은 동일합니다.
- 각 문제의 모든 테스트 케이스를 통과한 경우 점수를 획득하며, 부분 점수는 없습니다.
- 같은 수의 문제를 맞힌 동점자의 경우 ‘최고 점수에 도달한 시각 + 페널티’가 작은 순으로 순위가 결정됩니다.
- 페널티는 점수를 받은 문제에 대해, 문제를 맞히기 전까지 제출한 횟수마다 4분씩 가산됩니다. (즉, 풀지 못한 문제에 대해서는 페널티가 적용되지 않습니다.)
예선에 출제된 6문제에 대해, 모든 문제를 맞힌 참가자가 12명, 5문제를 맞힌 참가자가 19명, 4문제를 맞힌 참가자가 40명입니다. 이상의 71명은 9월 9일에 열리는 카카오 코드 페스티벌의 본선에 진출하시게 됩니다! 추가로, 3문제를 맞힌 82명 중 공지된 순위 결정 기준에 따라 상위 29명의 참가자 역시 본선 진출자가 되셨습니다. 본선 참가 대상자 여러분께 참가 등록에 대한 이메일을 발송했으니 확인해주세요! :)
예선에서 3문제 이상을 맞힌 상위 147명의 참가자에 대한 순위표를 공개합니다. 본선에 참가하시는 분들께는 축하의 말씀을, 아쉽게 참가 대상자가 되지 못하신 분들께는 위로의 말씀을 드립니다.
그럼 다시 한번 카카오 코드 페스티벌에 관심을 가지고 참가해주신 여러분들께 감사의 말씀을 드리며, 9월 9일에 있을 본선 및 이후에 카카오에서 개최할 개발자 행사에도 많은 관심 부탁드립니다!
Source: 카카오 코드 페스티벌 예선전 이야기
