2018 코드 페스티벌, 뜨거운 열기와 함께 본선 시작!

지난 8월 25일 토요일, 카카오 코드 페스티벌 오프라인 본선이 진행됐습니다. 예선에서의 엄청난 경쟁률을 뚫고 당당히 본선에 진출한 64명의 실력자들이 함께 했는데요. 작년과는 다르게 카카오 판교 오피스에서 행사를 개최하여 더 뜻깊은 자리가 되었던 것 같습니다.

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

그럼 본선에 출제되었던 문제와 해법을 알아보도록 하겠습니다.

문제 설명 및 풀이

승부 예측

제출자 62명
정답자 62명
문제 풀러 가기

서로 다른 결과의 경우의 수가 총 36 가지임을 알 수 있습니다. 그러므로 모든 경우를 고려하는 완전 탐색 풀이를 구현하면 됩니다.특정 경우에서 동점자가 발생하는 경우가 존재하기 때문에, 동점자가 발생하는 모든 경우를 유의할 필요가 있습니다.

카카오머니

제출자 64명
정답자 59명
문제 풀러 가기

모순이 없다고 가정하고, M 을 구해 봅시다. 편의상 b0 = 0 으로 둔다면, i (1 ≤ i ≤ n)번째 로그에서 카카오머니 잔고의 변화량은 bi - bi-1 입니다.

만약 bi - bi-1 = ai라면, i 번째 로그가 입금인지 출금인지의 여부와 관계없이, 카카오머니 잔고가 ai 만큼 변하여 제대로 기록된 것입니다.

하지만, 만약 bi - bi-1 ≠ ai 라면, 카카오머니 잔고가 부족하여 통장에서 돈을 가져왔을 것입니다. (이 외의 방법이 없습니다.)

통장에서 가져온 금액은 bi - (bi-1 + ai) 원입니다.문제의 지문에서, 통장에서 돈을 가져올 때에는 M 원씩을 여러 번 가져오므로, bi - (bi-1 + ai) 이 M 의 배수여야 한다는 조건을 얻을 수 있습니다.또한, 최종 잔고는 M 원 미만이므로, bi < M 이라는 조건도 얻을 수 있습니다.

위의 관찰 중 첫 번째 조건을 종합해 보면, M 으로 가능한 수들은 bi - (bi-1 + ai) 들의 공약수임을 알 수 있습니다.이들 중 두 번째 조건을 만족하려면, M 이 크면 클수록 좋다는 것을 알 수 있습니다.

따라서, bi - (bi-1 + ai) 들의 최대공약수를 구한 뒤, 이것을 M 으로 놓고, 주어진 로그대로 입출금을 해보면서 모순이 없는지 확인하면 됩니다.

뒤집기

제출자 61명
정답자 60명
문제 풀러 가기

문제를 잘 관찰해 보면, 인접한 두 격자의 색이 다른 경우 두 격자의 현재 상태는 초기 상태와 같다는 성질을 발견할 수 있습니다.

증명) 인접한 두 격자의 현재 상태가 BW 일 때, 원래 WW 거나 BB 였다면, 두 격자는 연결되어 있으므로 현재 상태와 같이 달라지는 경우는 발생하지 않습니다.원래 WB 였다면 상태가 바뀔 때 BW 로 한 번에 바뀔 수 없고, WW 또는 BB 를 거쳐야 하므로 불가능합니다. 따라서 초기 상태가 BW 였음을 알 수 있습니다.

인접한 격자 중 자신과 색이 다른 것이 존재하는 격자들의 경우 위 성질에 의해 색이 정해지고, 그 외의 격자들은 초기 상태에 아무렇게나 칠해져 있어도 현재 상태로 만들 수 있음을 알 수 있습니다.(연결된 컴포넌트들의 경계선에 있는 부분은 색이 정해 지므로, 내부는 아무렇게나 칠해져 있어도 경계선과 동일하게 만들 수 있습니다.)

따라서, 가능한 초기 상태의 수는 2(색이 정해지지 않은 격자의 수) 가 됩니다.

섬

튜브는 연료를 구하러 망망대해로 나가고 싶으나, 사냥꾼이 어떠한 섬을 점거했을 때 길이 막힐 것이 두려워 걱정하고 있습니다. 튜브는 현재 위치에서 안전하게 망망대해로 나갈 수 있을까요?

이 문제는 풀이의 방향이 크게 두 갈래로 나뉩니다. 하나는 출제진이 의도하였던 풀이이고, 하나는 출제진이 예상하지 못했던 방향의 풀이입니다. 첫 번째 풀이를 중심으로 설명하나, 두 번째 풀이에 대해서도 간단히 짚고 넘어가겠습니다.

의도된 풀이 : 그래프의 절점

문제를 다시 요약해 보겠습니다. 우리는 튜브가 도착한 각각의 섬 v 에 대해서, v 와 다른 섬 w 중, w 에 사냥꾼이 있을 때 v 에서 최외곽으로 갈 수 있는 경로가 없어지는 w 가 존재하는가가 궁금한 것입니다.결국에는 “경로” 와 “섬” 에 대한 이야기니, 그래프에 풀어놓고 생각해보면 편리하게 문제를 해결할 수 있습니다.

그래프에 있는 모든 4방향으로 인접한 육지와 바다를 Flood-Fill 로 하나의 정점으로 묶어줍시다. 이제 각각의 정점은 “섬” 이거나 “바다” 로 분류될 수 있습니다. “섬” 과 “바다” 가 맞닿아 있으면 간선을 이어줍시다.최외곽의 바다를 1번 정점이라고 하면, 우리가 풀고자 하는 문제는 다음과 같습니다.

그래프 G 와 튜브가 도착한 각각의 섬 정점 v 에 대해, w ≠ v 가 존재하여, G 에서 w 를 제거했을 때 1 번 정점과 v 번 정점을 잇는 경로가 존재하지 않는다.

왠지 익숙한 느낌이 들지 않나요? 그래프에서 정점 하나를 제거했을 때 경로가 사라지는 형태의 문제이니, “절점”의 개념을 활용할 수 있다고 생각할 수 있습니다.그래프에서 어떠한 정점을 제거하였을 때, 컴포넌트의 개수가 증가하는 정점들을 “절점” 이라고 부릅니다. 절점에 대한 자세한 설명은 지면상 생략하겠으나, 어떠한 정점이 절점인지 아닌지를 판별하는 것은 선형 시간에 가능합니다.

절점 개념을 도입하면, 문제는 다음과 같이 변합니다.

모든 섬 v 에 대해서, “절점인 섬” 을 지나지 않고 1 번 정점에서 v 번 정점을 방문할 수 있는지 아닌지를 판별하여라.

이는 절점을 구하는 알고리즘을 조금만 응용하면 됩니다.1번 정점에서 DFS 를 시작했을 때, 어떠한 점이 절점이면, 해당 점을 거쳐야만 1번 정점으로 갈 수 있는 점들의 집합이 DFS Tree 상의 서브트리로 표현이 됩니다.이는 문제가 “서브트리에 있는 정점에 대해서 마킹을 하시오” 의 형태로 환원이 된다는 것을 의미합니다.서브트리에 있는 정점은 Euler Tour 번호에서 연속된 구간을 이루기 때문에, 구간에 대한 마킹으로 변환할 수 있으며, 이는 변화값 배열을 사용해서 해결할 수 있습니다.

다른 풀이

입력이 결국에는 평면 상의 격자의 모습임을 상기해 보면, 사냥꾼이 점령하고 있는 섬 안에 “둘러싸인” 섬들은 위험한 섬이 된다는 것을 알 수 있습니다.즉, 각각의 섬에 대해서 그 섬이 “둘러싸고” 있는 섬들이 무엇인지를 알면 문제를 해결하는 데 조금 더 가까워질 수 있습니다. 둘러싸고 있는 영역을 Flood-Fill 해 주면 되기 때문입니다.

다른 풀이는 이 “둘러싸고 있는 영역” 을 효율적으로 구하는 데 초점을 맞춥니다.각각의 섬에 대해서 Flood-Fill 로 해당 섬의 영역을 구해주고, 영역의 빈자리를 찾아낸 후, 해당 빈자리를 다시 Flood-Fill 로 구해주는 것이죠.

직관적으로는 이 부분이 매우 자명하나, 이를 알고리즘으로 옮기는 것은 또 다른 난이도입니다. 여기부터는 출제진도 말을 아끼겠습니다 :D위 방법은 절점과 같은 고급 개념이 필요하지 않은 알고리즘이지만, 이러한 부분에서의 난이도가 상당히 있었는지, 초반에 이 문제를 빠르게 푼 대부분의 참가자들은 절점 알고리즘을 사용하였습니다.

보물 상자 열기

먼저, 초기 상태가 회문인 경우에는 답이 모두 0입니다.그렇지 않은 경우, 주어진 문자열을 S[1~N] 이라 할 때, S[i] 가 S[N+1-i] 와 다른 최소의 i 를 b 라 하고, e = N-b+1 로 두면 주어진 문자열을 회문으로 만들기 위해서는 b 번째 석판이나 e 번째 석판을 교체해야 한다는 것을 알 수 있습니다.

또한 [b, e] 구간 밖에서는 석판을 교체할 이유가 없으므로 시작 위치가 i 일 때 소모해야 하는 체력을 H[i] 라 하면,

i < b 인 경우 H[i] = H[b] + (b-i) * c
i > e 인 경우 H[i] = H[e] + (i-e) * c

가 되고 S[b~e] 에 대해서만 문제를 해결하면 됩니다. b 와 e 중 석판 b 를 교체하는 경우를 생각해 보면 시작 위치가 x 번째 석판일 때 가능한 경로를 다음과 같은 2가지로 분류할 수 있습니다.

x->r->b (x에서 오른쪽으로 갔다가 왼쪽으로 이동하여 b로 가는 경우)
x->b->r (x에서 왼쪽으로 이동하여 b로 갔다가 오른쪽으로 가는 경우)

두 경우 모두 [b, r] 의 석판만 교체하여 문자열을 회문으로 만들 수 있어야 가능하고, 또한 [b, r] 에 회문에서 서로 대응되는 두 석판이 모두 포함되는 경우 교체 시 드는 체력이 작은 쪽을 고르는 것이 항상 이득입니다.

모든 r 에 대해 [b, r] 구간을 방문할 때 회문을 만들기 위해 석판을 교체하는 데 드는 체력을 배열 P[] 에 미리 저장해 놓을 수 있습니다.그러면 x 가 주어졌을 때 x <= r 인 모든 r 에 대해 P[r] + (r-x) + (r-b) 의 최솟값이 x->r->b 의 경로 중 최적인 값이고, P[r] + (x-b) + (r-b) 의 최솟값이 x->b->r 의 경로 중 최적인 값입니다.이는 x 를 e 부터 시작하여 왼쪽으로 한 칸씩 밀면서 계산하면 모든 x 에 대해서 O(N) 시간에 계산할 수 있으므로 석판 b 를 교체하는 경우에 소모해야 하는 최소 체력을 O(N) 시간에 계산할 수 있습니다.석판 e 를 교체하는 경우도 대칭적으로 생각하면 마찬가지 방법으로 가능합니다.

따라서 선형 시간에 문제를 해결할 수 있습니다.

조용한 생활관 만들기

제출자 7명
정답자 0명
문제 풀러 가기

먼저, Union 마법을 사용했을 때 사용하기 전보다 더 시끄러워지는 경우는 없습니다.처음은 directed rooted tree 형태의 그래프이고, 최종 상태는 Union 마법을 더 이상 쓸 수 없는 상태여야 하므로 모든 도로의 끝점은 트리의 leaf 일 것입니다.이 점에 착안하여 생각해보면 이 문제는 directed rooted tree 의 edge 들을, leaf 를 끝점으로 하는 여러 경로들로 나누어 각 경로의 시작점과 끝점에 있는 건물의 사람 수의 곱을 최소로 만드는 문제입니다.즉, 건물 i 에 사는 사람의 수를 C[i] 라 할 때, 최종 상태의 모든 경로 u->v 에 대해 C[u]*C[v] 의 합을 최소화하면 됩니다.

처음에 주어진 directed rooted tree 에서, root 가 아닌 노드 u 를 생각해봅시다. 또한, u 를 root 로 하는 subtree 를 subtree(u) 라고 합시다.u 의 부모에서 u 로 들어오는 간선이 있으므로, 최종 상태에는 u 의 조상 중 하나에서 subtree(u)에 포함되는 leaf 로 가는 경로가 하나 있을 것이고, 그 경로에 포함되지 않는 subtree(u)의 edge 들은 subtree(u) 내부의 경로가 될 것입니다.

결론적으로, subtree(u) 내부의 edge 들이 최종적으로 어떤 경로에 포함될지 결정된다면, 외부에 영향을 끼치는 요소는 u 의 조상 중 하나와 연결될 leaf 의 건물에 있는 사람 수 뿐입니다.따라서, 다음과 같은 다이나믹 프로그래밍을 생각할 수 있습니다.

D[u][l] : u 의 조상 중 하나와 연결되는 leaf 가 l 일 때, u 내부 경로들에서 만들어지는 시끄러운 정도의 최솟값

점화식은 다음과 같습니다.

u = l : D[u][l] = 0
u ≠ l : u 의 자식 중 x 가 l ∈ subtree(x)을 만족할 때, D[u][l] = D[x][l] + (u 의 x 가 아닌 모든 자식 v 에 대해, (D[v][l’]+C[u]C[l’]) 의 최솟값들의 합 (단, l' 은 subtree(v)의 leaf))

각 자식 노드 v 에 대해 D[v][l'] + C[u]C[l'] 이 최소가 되는 l' 을 미리 구해놓을 수 있으므로, 시간 복잡도는 각 노드 u 에 대해 subtree(u)의 leaf l 을 선택하는 경우의 수인 O(N2)가 됩니다.위 다이나믹 프로그래밍은 O(N2)의 시간 복잡도를 가지므로, 시간 초과가 발생하게 됩니다. 이를 줄이기 위해서는 한 가지 관찰이 필요합니다.

subtree(u)의 모든 leaf l 에 대해, 좌표평면 상에서 y = C[l] * x + D[u][l] 라는 직선을 그었다고 생각해봅시다. 0 이상의 모든 x 에 대해 그 x 에서 함숫값이 최소가 되는 직선을 구했다고 합시다.만약 어떤 x 에서도 함숫값이 최소가 되지 않는 직선이 있다면, 그 직선은 최적해를 구하는 데에 있어 쓸모가 없습니다. 그 leaf 가 u 의 어느 조상과 연결되든 간에 더 좋은 방법이 존재하기 때문입니다.따라서 정점 u 에 대해 subtree(u)의 모든 leaf 에 대한 값을 저장할 필요가 없고, 위에서 설명한 직선들의 아래쪽 convex hull 만을 들고 있으면 충분합니다.

앞에서 설명한 DP를 이 convex hull 을 이용해서 할 수 있는데, 먼저 u 의 모든 자식 v 에 대해 D[v][l'] + C[u]C[l'] 의 최솟값은 v 의 아래쪽 convex hull 이 x = C[u] 와 만나는 부분임을 쉽게 알 수 있습니다.따라서 이를 미리 계산해 놓을 수 있습니다. 또한 u 의 자식 v 에 대해 subtree(v)에 포함되는 leaf 가 u 의 조상과 연결되는 경우는 v 의 convex hull 이 일정 크기만큼(정확히는 v 가 아닌 모든 자식 c 에서 D[c][l'] + C[c]C[l'] 의 최솟값의 합만큼) 위로 올라간 것임을 알 수 있습니다.따라서, 자식들에 저장된 convex hull 들을 y 축 방향으로 평행 이동시킨 후에 모두 합쳐서 convex hull 을 다시 구할 수 있다면 앞서 설명한 DP 와 정확하게 같은 것을 할 수 있는 것입니다.

먼저 set 을 이용해 Dynamic Convex Hull 자료구조를 만들면 O(log N) 시간에 직선을 추가하는 연산을 수행할 수 있고,어떤 x 좌표가 주어졌을 때 convex hull 에서 해당하는 y 좌표를 이분 탐색을 이용해 O(log2N) 시간에 찾을 수 있습니다.

y축 방향으로 얼마만큼 평행이동되었는지는 따로 저장해 놓으면 쉽게 관리할 수 있습니다.x 좌표가 주어졌을 때 convex hull 에서 y 좌표를 찾는 연산은 D[v][l'] + C[u]C[l'] 의 최솟값을 찾을 때 사용하므로 총 O(N)번 쓰게 되어 여기서 시간 복잡도 O(N log2N)가 발생합니다.자식들의 convex hull 들을 합쳐야 하는데, 자식들 중 가장 직선이 많은 convex hull 에 다른 자식들의 convex hull 의 직선을 삽입하는 small-to-large 방식으로 이를 해결할 수 있습니다.여기에서 직선 삽입은 Heavy-Light Decomposition 과 같은 원리로 최대 O(N logN)번만 수행됩니다. 따라서, 여기서 발생하는 시간 복잡도는 O(N log2N)입니다.

따라서, 총 시간 복잡도 O(N log2N)에 문제를 해결할 수 있습니다.

자석 장난감

제출자 8명
정답자 1명
문제 풀러 가기

이 문제는 그래프에서 규칙에 따라 모든 노드를 제거할 수 있는지 확인하는 문제입니다. 제거하는 규칙은, 어떤 노드 X 가 제거될 때 그 노드에 연결된 다른 모든 노드 A, B, …, D 가 서로 모두 연결되어 있어야 한다는 것입니다.이 조건에서 X, A, B, …, D 는 하나의 Clique(모든 노드 쌍이 연결된 부분 그래프)를 이룬다는 것을 알 수 있습니다.그래프의 한 상태에서 제거될 조건을 만족하는 노드는 어느 것을 먼저 제거하더라도 상관없다는 것을 짐작할 수 있고 증명할 수 있습니다.하지만, 이렇게 조건을 하나하나 확인하면서 제거할 수 있는 노드를 찾아 나가며 진행하는 것은 매우 느린 방법이 됩니다.

빠른 방법 중 하나는 노드를 제거하는 “특정한 순서”를 찾고, 그 순서에 따라서 노드를 제거했을 때 조건을 만족하면서 모든 노드를 제거할 수 있음을 확인하는 것입니다.이 “특정한 순서”는, 만약 모든 노드를 제거할 수 있는 순서가 하나라도 있다면 반드시 모든 노드를 제거할 수 있는 순서가 된다는 성질을 가집니다.모든 노드를 제거할 수 있는 그래프는 Clique 들이 서로 노드를 공유하는 모양으로만 구성되어 있어야 한다는 것을 어렵지 않게 짐작할 수 있고 증명할 수 있습니다.

비교적 단순하게 두 개의 Clique P 와 Q 가 일부 노드를 공유하고 있는 그래프로 설명해 보겠습니다.이 그래프는 모든 노드를 제거하는 것이 가능한 그래프임이 당연합니다. 노드들의 집합 P-Q, Q-P, P∩Q 를 생각해 봅시다.P-Q 나 Q-P 에 있는 노드가 가장 먼저 제거되는 것은 가능하지만, P∩Q 에 있는 노드가 가장 먼저 제거되는 것은 불가능합니다.P-Q 나 Q-P 중 한 집합이라도 모두 제거되어야 P∩Q 에 있는 노드가 제거될 수 있음을 알 수 있습니다.

이제, 아무 노드에서나 시작해서 그래프를 탐색하면서 방문하는 순서대로 노드들을 출력합니다.노드가 출력되면 노드에 연결된 다른 노드들에 모두 카운터를 1 증가시키는 연산을 합니다. 카운터 값이 큰 노드부터 무조건 다음에 출력합니다.

만약 이 탐색이 P-Q(혹은 Q-P) 에 있는 노드에서 시작된다면 P(혹은 Q)가 모두 출력된 다음에야 나머지 노드가 출력될 수 있습니다. 만약 이 탐색이 P∩Q 에 있는 노드에서 시작된다면, 탐색이 최초로 P-Q(혹은 Q-P) 에 들어가는 순간 P-Q(혹은 Q-P) 에 있는 노드가 모두 출력된 다음에야 Q-P(혹은 P-Q) 에 있는 노드가 출력됨을 알 수 있습니다.

모든 경우를 증명하는 것은 복잡하지만 이런 방식으로 출력하면, 출력의 반대 순서가 반드시 제거 가능한 순서가 됨을 알 수 있습니다.

특정한 하나의 순서를 찾았으면 이 순서가 규칙을 지키는 제거 순서인지를 확인해야 합니다.제거 과정에서 매번 규칙을 전부 확인하면 시간이 아주 오래 걸리게 됩니다.하지만, 이 과정을 살펴보면 동일한 노드 쌍의 연결 관계를 반복적으로 확인하고 있음을 알 수 있습니다.동적 프로그래밍과 비슷한 방법으로 반복적으로 확인하는 것을 한 번만 확인하도록 줄여서 빠른 시간에 규칙을 지키는지 확인하는 것이 가능합니다.

이러한 두 가지 과정을 거쳐서 O((N+M)logN) 시간 알고리즘을 구현할 수 있습니다. 대회에서는 O(N sqrt(N)) 정도 알고리즘도 통과할 수 있는 수준으로 채점 데이터가 만들어졌습니다.

헬리콥터

제출자 4명
정답자 0명
문제 풀러 가기

이 문제는 직교 다각형 형태로 주어진 영역을 왼쪽에서 오른쪽으로 비행할 때 단 한 번의 사선 방향을 제외하고는 모두 수직이나 수평으로만 움직일 수 있다고 가정하고 가장 짧은 거리를 찾는 문제입니다.이 문제의 답을 구현하는 것은 매우 어렵지만 아이디어를 설명하는 것은 비교적 간단합니다.

우선, 사선 방향 없이 수직 수평으로만 움직이는 경로를 생각해 봅시다. 주어진 영역 안에서 그러한 최단 경로는 매우 많습니다.최단 경로들을 모두 그렸다고 하면 그려진 경로들은 모여서 하나의 영역을 만들게 됩니다. 이 영역을 “새 영역”이라고 부릅시다. 새 영역을 구하는 것은 O(N) 시간에 가능합니다.

단 한 번의 사선 방향으로의 움직임(사선 성분)에 대해 다음 세 가지를 확인할 수 있습니다.

(1) 최적인 사선 성분은 새 영역 안에 있다.
(2) 최적인 사선 성분은 새 영역의 경계를 끝점으로 가진다.
(3) 최적인 사선 성분은 새 영역의 꼭짓점과 교차한다.

이 세 가지 성질에서 다음과 같은 알고리즘을 만들 수 있습니다. 새 영역의 각 꼭짓점에서 그 꼭짓점에 걸치면서 그 꼭짓점에서 보이는 영역의 경계 위의 두 점을 잇는 모든 선분을 확인합니다.각 꼭짓점에서는 O(N)개의 다른 꼭짓점이 보입니다. 선분들 중 적어도 한쪽이 꼭짓점인 것들은 따라서 O(N)개가 됩니다. 이들 중 최적인 것이 있다면 쉽게 확인할 수 있습니다.이들 중 최적인 것이 없다면 앞에서 확인한 선분들 사이를 회전시켜 가면서 최적인 선분을 찾아볼 수 있습니다.선분을 회전할 때 사선이 만들어 내는 이익은 증가나 감소를 최대 한 번 바꿀 수 있다는 것을 알아낼 수 있어 삼분 탐색으로 충분한 오차 이내까지 선분을 찾아 내려갈 수 있습니다.

이러한 방법으로 O(N2 logN * log109) 시간이 걸리는 알고리즘을 만들 수 있습니다. 대회에서는 O(N3) 정도 되는 알고리즘도 통과할 수 있는 수준으로 채점 데이터가 만들어졌습니다.

결과 발표

그럼 이제, 코드 페스티벌 본선 결과를 공개합니다! 본선은 예선과 같은 방식으로 채점이 진행되었으며, 1등은 출제된 8문제 중 6문제를 풀어주셨습니다.

▶ 순위표 보러 가기

사전에 공지된 대로 우수한 성적을 거둔 상위 31명의 참가자에게 상장 및 상금이 수여되었습니다. 아쉽게 수상권에 들지 못한 분들을 위해 다양한 특별상도 준비했는데요, 수상하신 모든 분들 축하드립니다!

마지막으로 작년에 비해 본선 문제의 난이도가 높다는 피드백이 많았는데요, 그럼에도 불구하고 끝까지 코드 페스티벌에 적극적으로 참여해주신 분들께 감사드립니다.

앞으로 있을 개발자 행사에도 많은 관심 부탁드립니다 :)

코드 페스티벌 2018 본선 이야기