카카오 코드 페스티벌 본선 이야기

KENNETH

7년 ago

카카오 코드 페스티벌 본선 이야기

드디어 본선의 막이 열렸습니다!

지난 9월 9일 토요일, 카카오 코드 페스티벌의 오프라인 본선이 진행됐습니다. 예선에서의 엄청난 경쟁률을 뚫고 당당히 본선에 진출한 100여명의 실력자들이 함께 했는데요. 합병 후 카카오의 첫 개발자 행사인 만큼, 처음이라는 설렘을 담아 구석구석 정성스러움을 가득 담아 대회를 준비했습니다.

▶ 행사 후기가 궁금하시다면?

코드 페스티벌의 핵심인 문제도 정말 열심히 준비했습니다! 참가자들도 “문제 모티브가 재미있어 다른 대회보다 더 즐기는 마음으로 참여할 수 있었다”는 긍정적인 피드백을 주셨는데요, (이런 피드백 무한 감사, 정말 힘이 납니다!) 본선에 출제되었던 문제에 대한 설명과 해설을 이제부터 진행하고자 합니다.

문제 설명 및 풀이

코드 페스티벌 본선에는 총 8문제가 출제되었습니다. 3시간이라는 짧은 시간동안 진행되었지만 참가자들의 대단한 실력을 증명하듯 모든 문제에 정답자가 있었습니다. 그럼 이제 문제를 하나하나 함께 살펴보실까요?

▶ 문제 다운로드 (pdf, 2.2MB)

단체사진 찍기

제출자 81명
정답자 78명

8명의 프렌즈가 나란히 서서 단체사진을 찍는데, 각자가 다른 프렌즈와 어느 정도 거리를 두고 서고 싶은지를 입력으로 받고 이 조건을 모두 만족하는 경우의 수를 구하는 문제입니다. 8명이 나란히 서는 모든 경우의 수가 8! = 40,320으로 많지 않기 때문에, 모든 가능한 방법에 대해 조건을 모두 만족하는지를 확인하면 됩니다. C++의 경우 next_permutation 함수를 이용하면 빠르게 코드를 작성할 수 있으며, 이를 사용하지 않고 직접 가능한 경우의 수를 모두 생성하거나 8중 반복문으로 조건을 확인해도 개수가 많지 않아 제한 시간 안에 답을 구할 수 있습니다.

GPS

제출자 65명
정답자 50명

택시가 다니는 거점과 도로의 정보, 그리고 택시가 시간대 별로 보낸 현재 위치가 입력으로 주어집니다. 단 현재 위치와 다음 위치를 연결하는 도로가 없을 경우 이동이 불가능하며, 이와 같은 오류를 최소한으로 수정하여 이동 가능한 경로로 만드는 것이 목표인 문제입니다.

동적 계획법(Dynamic Programming)으로 풀 수 있습니다. 다음과 같은 2차원 배열을 정의하고 순서대로 값을 채워나가면 됩니다.

S[i][j]: 경로의 i번째 값이 j가 되는 경우, i번째까지의 경로가 valid하도록 고쳐야 하는 최소 횟수,
         그러한 수정이 불가능하다면 INF

승차 위치는 오류가 없기 때문에 S[0][j]의 값은 j가 입력된 승차 위치인 경우 0, 그렇지 않은 경우 INF입니다. 그리고 i>0인 경우의 값은 i-1번째의 값을 참조하여 계산할 수 있습니다. 이때 택시가 특정 위치에 계속 머무르는 것이 가능하기 때문에 계산할 때 이를 고려해야 합니다. 모든 값을 구한 뒤 입력된 하차 위치 j에 대해 S[k-1][j]를 구하면 됩니다. O(k(n+m))의 시간복잡도로 답을 구할 수 있습니다.

리틀 프렌즈 사천성

제출자 62명
정답자 49명

2차원 배열이 주어지고, 사천성 게임의 규칙에 따라 블록을 제거하는 방법을 구하는 문제입니다. 단 원래의 사천성 규칙에 비해 경로의 꺾는 횟수가 한 번으로 줄어들었고 모든 블록이 항상 두 개씩만 존재한다는 조건이 추가되었습니다. 그리고 블록은 알파벳 대문자로 표시되기 때문에 최대 26개만 존재할 수 있습니다. 가능한 방법이 여러 가지인 경우 알파벳 순으로 가장 먼저인 문자열을 리턴하는 조건이 있기 때문에, 입력된 초기 상태부터 A부터 Z까지 확인하며 같은 글자의 두 블록이 제거 가능한지 확인하는 과정을 반복하면 됩니다. 게임판의 크기가 크지 않기 때문에 단순한 방법으로도 경로 확인이 가능한데, 그중 한 가지는 각 블록에서 상/하/좌/우로 다른 블록이나 장애물에 막히지 않고 갈 수 있는 위치의 집합을 구한 뒤 두 집합의 공통 원소가 있는지를 확인하는 방법이 있습니다.

튜브의 소개팅

제출자 70명
정답자 47명

2차원 배열이 입력으로 주어질 때, 왼쪽 위에서 오른쪽 아래로 이동하면서 길이가 최소인 경로, 길이가 같다면 대화 시간의 합이 가장 작은 경로를 구하는 문제입니다. 단 총 대화 시간의 합은 입력된 s를 넘지 않아야 합니다. 먼저 다음과 같은 3차원 배열을 정의합니다.

S[i][j][k]: 왼쪽 위에서 (i, j)까지 k의 길이로 이동할 때 대화 시간의 최솟값

이를 채우는 방법은 Dijkstra 알고리즘 등을 이용하면 됩니다. 모든 값을 계산한 뒤 S[m-1][n-1][k] <= s인 최소의 k가 최소 경로의 길이, 배열에 저장된 값이 대화 시간의 합이 됩니다.

몸짱 트레이너 라이언의 고민

제출자 30명
정답자 12명

헬스장의 예약 내역이 입력으로 주어질 때, 예약한 회원들 간의 락커의 거리를 최대로 하는 배치를 구하는 문제입니다. 단 영업시간을 통틀어 할당된 락커 간 최소거리를 최대화하는 것이 목적이기 때문에 손님이 입장한 순간 거리를 최대로 하는 위치에 배정해주는 것보다 앞으로 입장할 손님을 고려하여 배치하는 것이 최적입니다. 결국 회원의 수가 최대인 시간대의 최적 배치를 구하면 기타 시간대에는 그 배치의 부분집합을 사용하면 되므로, 락커의 크기와 락커를 사용하는 최대 인원에 의해 답이 결정됩니다.

문제를 살짝 바꾸어, 락커의 크기와 최소 거리가 입력으로 주어졌을 때 최대 락커의 수를 구하는 문제를 생각해봅시다. 이 문제를 풀 수 있으면 원래의 문제인 락커를 사용하는 최대 인원에 대해 최소 거리를 구하는 문제도 풀 수 있습니다. 선택된 모든 락커의 거리가 d 이상이 되도록 최대의 개수로 락커를 선택하기 위해, 각각의 락커를 그래프의 정점으로 두고, 거리가 d 이상인 락커를 간선으로 잇는 그래프를 만듭니다. 이렇게 만들어진 그래프에서 최대 완전 부분 그래프를 구하면 그 크기가 답이 됩니다. 최대 완전 부분 그래프를 구하는 효율적인 방법은 알려져 있지 않지만, 이 문제의 경우 그래프의 크기가 크지 않고, 자명한 경우에 대해서는 그래프를 찾지 않고도 답을 구할 수 있기 때문에 문제의 크기를 더 줄일 수 있습니다. 가령 거리가 1인 경우는 모든 락커를 사용하는 경우이고, 거리가 2인 경우는 락커를 한 칸씩 건너 사용하는 경우(체크무늬 형태)입니다. 이와 같이 오래 걸리는 경우를 제외하고, 탐색 과정에서 적절한 가지치기(pruning)를 하면 됩니다. 단 이 경우에도 제한 시간 안에 모든 경우에 대한 답을 구하기 힘들 수 있는데, 답을 구해야 하는 경우의 수가 많지 않기 때문에 (락커의 크기가 최대 10이고 락커를 사용하는 최대 인원은 100명으로, 가능한 모든 조합에 대해 답을 구한다고 해도 그 수가 많지 않습니다.) 모든 가능한 경우에 대해 답을 구해놓고 이를 리턴하는 식으로 코드를 작성하는 것도 가능합니다.

네오의 귀걸이

제출자 8명
정답자 5명

주어진 점에 대해, 서로 꼭짓점이 연결되는 직사각형의 형태로 구성된 ‘기하학적으로 아름다운 귀걸이’를 만들 수 있는 경우의 수를, 점이 추가 혹은 삭제되는 각각의 경우에 대해 계산하는 문제입니다. 점의 개수 및 점을 추가하거나 삭제하는 변화의 수가 최대 100,000이기 때문에 O(n log n)의 시간복잡도로 해결해야 합니다.

각각의 점 (x_i, y_i)에 대해 z_i = y_i - x_i를 정의합니다. 즉, z_i는 (x_i, y_i)를 지나는 기울기가 1인 직선의 y절편이 됩니다. 이를 기준으로 내림차순 정렬을 한 뒤 다음과 같은 배열을 정의하여 채웁니다.

Dp_1[i][j]: z를 내림차순 정렬했을 때, i번째 값을 절편으로 가지고 기울기가 1인 직선 위에 존재하는 점 중,
            x좌표로 내림차순 정렬했을 때 j번째에 위치한 점이 직사각형의 오른쪽 아래 점일 때의
            가능한 귀걸이의 경우의 수

이 배열의 값은 왼쪽 위에서 오른쪽 아래의 순서대로 계산하고, 값을 계산할 때에 해당 위치의 점이 가지는 특성값 k를 z에 더하여 참조해야 할 절편의 값을 알 수 있으며, 해당 직선 내에서 x좌표가 [x-k, x]인 구간을 참조하여 Dp_1값을 모두 더하면 됩니다. 즉, 다음과 같이 Dp_1의 누적합 배열을 만들면 이분탐색을 통해 Dp_1[i][j]를 O(log n)에 계산할 수 있습니다.

Dp_1sum[i][j] = Dp_1sum[i][j-1] + Dp_1[i][j] (sum of Dp_1[i][k] for k = [0, j])

위와 비슷하게 오른쪽 아래에서부터 올라오는 경우에 대해서도 배열을 정의합니다.

Dp_2[i][j]: z를 내림차순 정렬했을 때, i번째 값을 절편으로 가지고 기울기가 1인 직선 위에 존재하는 점 중,
            x좌표로 내림차순 정렬했을 때 j번째에 위치한 점이 직사각형의 왼쪽 위 점일 때의
            가능한 귀걸이의 경우의 수

이 배열의 값은 오른쪽 아래에서 왼쪽 위의 순서대로 계산합니다. Dp_1을 계산할 때와 다르게 해당 점과 직사각형으로 연결될 오른쪽 아래 꼭짓점의 특성값이 여러 가지가 될 수 있음을 주의해야 합니다. 특정한 점에 대해 값을 계산하면서 뒤에 계산할 점에 대한 전처리를 진행하는 방식으로 계산을 진행하면 됩니다. 해당 점을 오른쪽 아래 점으로 두면서 직사각형으로 연결될 수 있는 점은 특성값의 성질에 의해 z값이 같은 직선 상의 연속된 점이므로, 세그먼트 트리 등을 이용하여 각각의 점을 왼쪽 위 점으로 하는 경우의 수를 차례로 더해가면 됩니다. 그래서 이 배열을 계산하는 과정도 마찬가지로 O(n log n)에 완료될 수 있으며, 이후의 연산을 위해 위의 경우와 같이 Dp_2sum 배열을 계산합니다.

그러면 초기 상태에 대해 가능한 귀걸이의 경우의 수는 점 E에 대해 Dp_1의 값을 계산하면 됩니다. 점이 추가되는 경우에는 추가되는 점에 대해 유효한 Dp_1의 값과 Dp_2의 값을 이분탐색으로 찾은 뒤, 필요한 값을 곱하여 계산할 수 있고, 점이 삭제되는 경우에는 삭제되는 점에 대한 Dp_1과 Dp_2 값을 가져와 그 점을 지나는 경우의 수를 구하고, 전체 경우의 수에서 이 값을 빼면 됩니다.

스마트한 프로도

제출자 10명
정답자 3명

그래프에서 연결하는 정점이 같은 두 간선을 인접한 간선으로 부르고, 서로 인접한 간선이 없는 간선의 집합을 매칭이라고 부릅니다. 주어진 그래프에 대해 초기 매칭과 최종 매칭이 입력으로 주어지고, 이를 매칭의 조건을 항상 만족하면서 간선을 추가하거나 삭제하여 변환하는 방법을 구하는 문제입니다. 초기 매칭 M_0와 최종 매칭 M_t에 대해, 다음과 같이 집합 H를 정의합니다. H = (M_0 - M_t) U (M_t - M_0) 즉, 두 매칭에 공통으로 속한 간선을 제외한 간선의 집합이 됩니다. 이 집합에 속한 간선을 인접한 간선끼리 부분집합으로 묶으면 모두 다음의 경우 중 하나에 속하게 되며, 이는 M_0과 M_t가 모두 매칭의 조건을 만족한다는 점을 이용하여 보일 수 있습니다.

M_0 - M_t에 속하는 단일 간선
M_t - M_0에 속하는 단일 간선
사이클을 이루는 간선의 집합, 여기에 속한 간선은 M_0 - M_t에 속한 간선과 M_t - M_0에 속한 간선이 번갈아가며 이어진다.
일직선으로 이어지는 간선의 집합이면서 두 끝이 모두 M_0 - M_t에 속하는 경우, 여기에 속한 간선은 M_0 - M_t에 속한 간선과 M_t - M_0에 속한 간선이 번갈아가며 이어진다.
일직선으로 이어지는 간선의 집합이면서 두 끝 중 하나 이상이 M_t - M_0에 속하는 경우, 여기에 속한 간선은 M_0 - M_t에 속한 간선과 M_t - M_0에 속한 간선이 번갈아가며 이어진다.

첫 번째와 두 번째에 속하는 경우는 단순히 간선을 삭제하거나 추가하면 됩니다. 세 번째의 경우는 M_0 - M_t에 속한 간선을 삭제하면 다섯 번째 경우가 되며, 네 번째의 경우는 한쪽 끝을 삭제하면 다섯 번째 경우가 됩니다. 다섯 번째 경우에 해당하는 간선에 대해서는 M_t - M_0에 속하는 끝 간선을 추가한 뒤, 번갈아가며 삭제 또는 추가 연산을 적용합니다. 이상의 과정에서 간선의 수는 k-2 이하로 내려가지 않아야 한다는 조건이 있는데, 각 부분집합에 대해 적용되는 연산은 독립적으로 적용이 가능하므로 부분집합에서 |M_t - M_0| - |M_0 - M_t|가 큰 순서대로 연산을 적용함으로써 간선의 수를 항상 k-2 이상으로 유지하는 것이 가능합니다.

IU와 콘의 보드게임

제출자 5명
정답자 1명

삼각형의 세 변을 이루는 고무줄을 규칙에 따라 움직여 만들 수 있는 새로운 모양의 수를 구하는 문제입니다. 고무줄의 모양은 오목해야 한다는 조건이 있는데, 이 조건을 만족하도록 B와 C를 잇는 고무줄을 이동시켜 위 그림과 같은 모양을 만든 상황을 생각해봅시다. B와 C를 잇는 고무줄이 거치는 점을 순서대로 P_1, …, P_k라고 할 때, B에서 P_1로 그은 연장선과 C에서 P_k로 그은 연장선, 그리고 선분 BC로 만들어지는 삼각형이 있을 때, P_2, …, P_k-1은 모두 삼각형 안에 들어가게 되며, 삼각형 영역 중 고무줄 위쪽에 속하는 부분에는 점이 없어야 합니다. 그리고 모든 고무줄은 오목한 모양으로만 이동이 가능하므로 A와 B를 잇는 고무줄, 혹은 A와 C를 잇는 고무줄은 삼각형 내부의 점을 지날 수 없습니다. 삼각형 안에 있는 점을 지날 수 있는 고무줄은 B와 C를 잇는 고무줄이 유일하고 이들 점이 오목한 형태로 이어져야 하므로, P_1과 P_k가 정해지면 B와 C를 잇는 고무줄의 모양은 유일하게 정해지게 됩니다. 즉, 각 고무줄에 대해 양 끝 점을 정한 뒤 만들어지는 모양이 규칙을 만족하는지 보면 됩니다. 단 이 경우 살펴봐야 하는 모양의 수가 O(n^6)이 되어 제한시간 안에 모두 살펴볼 수 없습니다.

더 생각을 발전시켜 보면, 각 고무줄의 왼쪽 끝점만 정해지면 그에 따라 오른쪽 끝점이 유일하게 결정됨을 알 수 있습니다. 그렇게 각 고무줄에 대응되는 왼쪽 끝점을 정하고, 만들어지는 모양이 문제에서 제시된 조건을 만족하는지를 보면 됩니다. 삼각형의 꼭짓점에서 각 고무줄의 왼쪽 끝점을 지나는 연장선을 그었을 때 만들어지는 삼각형의 내부에 점이 없으면 조건이 성립하는 경우임을 알 수 있습니다. 그래서 총 O(n^3)의 경우의 수를 살펴보면 됩니다.