초등부 1. 수 고르기 풀이 작성자: 박현민 부분문제 1 (N 3) 경우의 수가 많지 않아, 각 형태를 모두 조건으로 분리하여 O(1)에 처리할 수 있다. 부분문제 2 (N 20) O(2N )으로 N 개 중 K개의 수를 고르는 모든 방법을 찾고, 각각 전체 점수를 O(K 2 ) 또는 O(N 2 )으로 계산하고 그 중 최댓값을 찾으면 된다. O(2N N 2 )에 해결할 수 있다. 부분문제 3 (K = 1) 주어지는 N 개의 수 중 최댓값을 찾으면 된다. O(N )으로 충분하다. 부분문제 4 (K = 2) 수 2개를 O(N 2 )으로 고르고, 각각 전체 점수를 계산하고 그 중 최댓값을 찾으면 된다. 부분문제 5 (주어지는 N 개의 수가 단조증가로 정렬되어 있다.) 각 수의 점수를 자신의 수 와 자신의 왼쪽에 있는 수 중 선택된 수의 개수 로 분리해보자. 이 때, 자신의 수 는 어떤 수를 선택하느냐에 따라 달라지고, 자신의 왼쪽에 있는 수 중 선택된 수의 개수 는 해당 수가 선택된 수들 중 왼쪽에서 몇 번째에 있느냐에 따라서 결정된다. 즉, 선택된 수들 중 가장 왼쪽에 있는 수는 그 값이 0이고, 두 번째인 수는 1이고, 세 번째인 수는 2인 것처럼, 오른쪽으로 갈 때마다 1씩 증가하는 규칙을 가진다. 전체 점수를 계산할 때에도 역시 분리해보면 ( 자신의 수 의 합)과 ( 자신의 왼쪽에 있는 수 중 선택된 수의 개수 의 합)으로 나타낼 수 있는데, 이 때 두 번째 괄호를 살펴보면 각 값은 언급한 것처럼 선택된 수들 중 가장 왼쪽에 있는 수부터 0, 1, 2,, N 1 이다. 즉 두 번째 괄호를 계산하면 언제나 N (N 1) 2 이다. 이제 첫 번째 괄호로 다시 돌아오면, 이제 다른 수와 관계가 없으므로 자신의 수 가 각자 커질 수 있는 한 최대한 커지는 것이 좋음을 알 수 있다. 주어지는 N 개의 수가 단조증가로 정렬되어 있으므로, 가장 오른쪽 수부터 K 개를 고르면 그 것이 가장 첫 번째 괄호의 값을 크게 하는 방법이다. 부분문제 6 부분문제 5를 해결했다면, 주어지는 N 개의 수를 O(N 2 )이나 O(N log N )으로 정렬한 후 동일한 아이디어를 사용할 수 있다.
초등부 2, 중등부 1. 종이접기 풀이 작성자: 이재웅 부분문제 1 (k = 1) 직접 모든 경우의 수를 시도해 본 다음 가능한 모든 입력에 대해 답을 저장한 후 출력해주면 된다. 부분문제 2 (U, R만 존재) 가로와 세로로 접는 방법이 고정되어 있을 경우 접는 순서는 중요하지 않다는 것을 관찰할 수 있고, U와 R을 각각 k번 실행할 때 점의 규칙성을 찾아서 출력해주면 된다. 부분문제 3 (k 8) 종이를 접은 순서의 역순으로 펼칠 때마다 뚫린 점의 개수가 2배로 늘어나고 새로 추가되는 점의 위치는 접은 방향과 기존 점의 위치에 의해 결정됨을 알 수 있다. 예를 들어, 0번 위치에 뚫린 점이 있는 종이를 오른쪽으 로 펼치면 점은 2배로 늘어나는데, 펼쳐진 종이의 왼쪽에는 0번 점이 그대로 있고 오른쪽에는 1번 점이 있게 된다. 기존의 점과 새로 생긴 점은 접은 선을 기준으로 대칭을 이루므로, 2차원 배열 등을 통해 점의 위치를 기록하면 다음 단계에서 점의 위치 또한 구할 수 있게 된다. 기존 점의 위치와 종이를 펼치는 방향에 따라 새로 생기는 점의 위치를 조건문을 통해 미리 구해놓은 다음, 종이를 차례차례 펼쳐가면서 점들의 변화를 저장한 후 최종 상태를 출력해주면 된다.
초등부 3, 중등부 2. 등산 마니아 풀이 작성자: 구재현 부분문제 1 (그래프가 직선) 두 정수 i, j 를 골랐을 경우 (i < j) 다양성이 j 1 이다. j 를 고정할 경우, 가능한 i 의 개수는 j 1 이다. 고로 모든 1 j N 에 대해 (j 1)2 의 합을 계산하고 출력하면 된다. 부분문제 2 (그래프가 성게) 두 정수 i, j 를 골랐을 경우 (i < j) 다양성은 i = 1 일 때 1, 아니면 2이다. i = 1 인 쌍은 N 1 개 있고, 그렇지 않은 쌍은 (N 1)(N 2) 2 개 있다. 고로 답은 (N 1)2 이다. 부분문제 3 (그래프가 완전 이진 트리) 문제의 조건이 복잡하지만, 결국 N = 2d+1 1 인 깊이 d의 완전 이진 트리가 주어진다는 뜻이다. i 의 깊이, j의 깊이, 그리고 1번 정점에서 처음으로 이 두 정점이 갈라지는 위치 k 의 깊이, 이 세 가지를 고정하자. (k를 보통 i, j의 Lowest Common Ancestor (LCA)) 라고 부른다). i 의 깊이와 j 의 깊이 모두가 k 의 깊이보다 큰 경우, 둘 중 하나만 k 의 깊이보다 큰 경우로 케이스를 나눠서, 가능한 i, j, k 의 경우의 수를 2의 지수승 꼴의 수로 계산할 수 있다. d = O(log N ) 이니 O(d3 ) = O(log3 N ) 시간에 문제가 해결된다. 부분문제 4 (N 100) 모든 가능한 i < j를 순회하자. LCA(i, j) 를 두 정점 i, j 의 Lowest Common Ancestor라고 하고, depth[i] 를 i 번 정점과 1번 정점의 거리라고 하면, 답은 depth[i] + depth[j] - depth[lca(i, j)] 가 된다. 두 정점의 LCA는 O(N ) 시간에 계산할 수 있다. 전체 문제가 O(N 3 ) 시간에 해결된다. 부분문제 5 (N 5000) dist(i, j) 를 두 정점 i, j 의 거리라고 정의하면, 고정된 쌍 i < j 에 대해서 다양성은 dist(1,i)+dist(i,j)+dist(j,1) 2 2 이다. 모든 두 정점 간의 거리를 O(N ) 번의 깊이 우선 탐색으로 계산해 둘 수 있다. 전체 문제가 O(N ) 시간에 해결된다. 부분문제 6 각 쌍에 대해서 다양성의 합을 센다는 것은, 각 쌍에 대해서 조건을 만족하는 어떤 간선의 수를 센다는 것이다. 반대로, 모든 간선에 대해서, 이 간선이 특정 쌍의 다양성에 기여하는 조건을 파악하고, 이 간선이 다양성에 기여하는 쌍의 개수를 세어주자. 트리의 루트를 1번 정점으로 두자. v 와 v 의 부모를 잇는 간선에 대해서, v 의 서브트리에 i 혹은 j 정점이 있다면, 이 간선은 1번 정점과 두 정점 중 하나를 잇는 경로 상에 있으니 다양성에 기여한다. 둘 다 없다면, 이 간선이 없다 하더라도 1, i, j 번 정점 사이를 오가는 데는 문제가 없고, 다양성에 기여하지 않는다. 고로, v 와 v 의 부모를 잇는 간선에 대해서 문제의 정답은, 전체 트리에서 두 개의 정점을 고르면서 v 의 서브트 리에서 최소 하나의 정점을 뽑는 경우의 수와 동일하다. v 의 서브트리에 속하는 정점의 개수를 O(N ) 에 전처리 한다면 이 경우의 수는 간단한 수식으로 셀 수 있다. 전체 문제가 O(N ) 에 해결된다.
초등부 4. 사탕 돌리기 풀이 작성자: 구재현 부분문제 1 (Q = 1) 다음과 같은 그리디 알고리즘을 사용할 수 있다. 현재 깡통에 있는 사탕 중 다른 위치로 옮겨져야 하는 사탕을 아무거나 고른다. 그런 것이 없다면 아무거나 고른다. 해당 사탕이 목적지에 도달할 때까지 계속 가지고 다닌다. 이러한 그리디 알고리즘을 구현했을 때 원하는 최종 상태가 나왔다면 문제를 해결할 수 있다. 알고리즘의 정당 성은 따로 증명하지 않으나, 전체 문제 풀이에서 자연스럽게 따라온다. 부분문제 2 (N = 2) 1번 깡통에 있는 2번 사탕의 개수와, 2번 사탕에 있는 1번 사탕의 개수는 동일하다. 이 숫자를 C 라고 하자. 한 번의 사탕 돌리기로 두 사탕을 바꿔주면, C 를 하나씩 줄여줄 수 있다. 고로 C Q 면 답은 1, 아니면 0이다. 부분문제 5 먼저, 최종 상태를 만들 수 있는 최소 작업 수를 Qmin 이라고 하면, Qmin + 1, Qmin + 2... 번의 작업으로도 원하는 상태를 얻을 수 있다. Qmin 번의 작업 이후에, 1번 깡통에서 아무 사탕이나 집은 후 한 바퀴 도는 식으로 남은 작업을 처리하면 되기 때문이다. 고로 최소 작업 수인 Qmin 을 구한 후 이것이 Q 이하인지를 판별하는 식으로 문제를 해결한다. 어떠한 사탕이 목표로 하는 깡통에 들어가 있지 않을 경우 이 사탕을 어긋난 사탕 이라고 정의하자. 큰 틀에서, 대략 다음과 같은 그리디 알고리즘을 사용할 수 있다. 현재 깡통에 있는 사탕 중 다른 위치로 옮겨져야 하는 사탕을 아무거나 고른다. 해당 사탕이 목적지에 도달할 때까지 계속 가지고 다닌다. 모든 사탕이 제 자리에 갈 때까지 반복한다. 이 알고리즘의 가장 큰 문제점은 현재 깡통에 있는 사탕 중 다른 위치로 옮겨져야 하는 사탕이 없을 수 있다는 것이다. 일단은 운이 좋게 그러한 일이 절대 일어나지 않는다고 가정한 후 논리를 전개하자. 첫 번째 관찰은, 어긋난 사탕을 제자리에 놓았을 때, 해당 깡통에 어긋난 사탕이 하나 이상 존재하거나, 현재 위치 가 1이다. 만약에 현재 위치가 1이 아니면서 어긋난 사탕이 존재하지 않는다고 한다면, 제자리에 놓게 될 사탕을 포함하여 총 K + 1 개의 사탕이 해당 위치에서 어긋나지 않게 되는데, 같은 색을 가진 사탕이 K 개이기 때문에 이는 모순이다. 고로, 사탕을 제 자리로 돌리는 과정은 하나의 사이클을 이룬다. 이를 정리 사이클 이라고 부르자. 두 번째 관찰은, 앞서 한 가정을 유지했을 때 이 알고리즘이 최적이라는 것이다. 어떠한 사탕 x 가 다른 위치 y 로 옮겨지기 위해서는, x y 일 때 최소 y x 번 꺼내져야 하고, 그렇지 않을 경우 N x + y 번 꺼내져야 한다. 이 사실은 어떠한 전략을 사용하더라도 피할 수 없으니, 우리가 사탕을 꺼내야 하는 횟수의 최소 한도는 정해져 있다고 할 수 있다. 한편 위 알고리즘은 항상 이 꺼내야 하는 횟수의 최소 한도만큼의 연산을 사용한다. 고로 위
알고리즘은, 나쁜 경우가 없다는 가정 하에, 최적이다. 이제 전체 알고리즘으로 넘어가자. 현재 내가 있는 위치에서 어긋난 사탕이 존재한다면, 우리는 정리 사이클 을 한 바퀴 돌면서 남은 사탕들을 최적의 연산으로 정리해 줄 수 있다. 어긋난 사탕이 없지만 다른 위치에 있다면, 해당 위치에서도 정리 사이클을 구해주자. 우리는 고로 사탕들을 여러 개의 최적인 정리 사이클로 분해할 수 있 다. 여기서 세 번째 관찰은, 두 개의 정리 사이클을 하나의 정리 사이클로 합쳐줄 수 있다는 것이다. 정리 사이클 A, B 가 있을 때, B가 사탕을 교환하는 임의의 깡통에서 멈춰서, (A의 사탕 내려놓기) (B의 사탕 집고 B의 정리 사이클 완료) (다시 A에서 집으려 했던 사탕, 혹은 내려놓은 사탕을 집은 후 A의 정리 사이클 완료) 의 요령으로 두 사이클을 한번에 처리할 수 있다. 이렇게 되면 우리는 정리 사이클이 1번 깡통에서 사탕을 교환한다는 가정 하에 최적의 알고리즘을 찾았다. 모든 사탕들의 원호상 거리를 모두 더한 후, 이를 N 으로 나누면 된다. 1번 깡통에서 정리 사이클이 사탕을 교환하지 않는다는 것은, 1번 깡통에 1번 사탕만이 존재한다는 것이다. 이 사탕들에 대해서는 낭비를 피할 수가 없으니 답을 1 늘리는 것은 불가피하며, 아무 사탕이나 집고 정리 사이클을 만난 후, 정리 사이클을 처리하고 다시 그 + 1 번 안에 정리가 가능하다. 이제 전체 문제는 입력으로 주어진 사탕에 사탕을 1번 깡통에 넣는 식으로 거리합 N 대해서 거리 합을 구한 후, 단순 수식으로 쉽게 구현할 수 있다. 시간 복잡도 O(N K), 공간 복잡도 O(1) 에 문제가 해결된다. 부분 문제 3은 정리 사이클로 사탕을 분해하는 방법이 유일하여, 임의의 방법으로 분해할 생각을 하지 않아도 괜찮다. 부분 문제 4는 이 풀이와 다른 접근을 사용하는 O(N 2 K) 알고리즘을 위해서 주어졌다. 해당 알고리즘에 대한 설명은 생략한다.
중등부 3. 버블버블 풀이 작성자: 윤창기 X = max(a1,, AN )이라고 하자. 모든 풀이에 앞서, 수 하나를 바꿀 때는 1 이상 X 이하의 정수값에 대해서 시도해보면 충분하다는 사실을 알 수 있다. 정수가 아닌 실수로 수를 바꾸는 경우, 가장 가까운 정수로 답을 바꾸어도 교환 횟수가 변하지 않는다. 부분문제 1 (N 200, X 200) 수 하나를 바꿀 수 있는 경우가 O(N X)가지이므로, 모든 경우에 대해 버블 정렬을 직접 시도하는 경우 O(N 3 X) 의 시간복잡도로 구현에 따라 점수를 받을 수 있다. 추가적으로 버블 정렬의 교환 횟수는 i < j이지만 Ai > Aj 인 1 i < j N 의 개수 와 같으며, 이를 수열의 inversion count라고 한다. 단순히 inversion count를 계산 하는 방법은 O(N 2 )시간이 걸리지만, Ai 를 변경할 때는 i번째 수와 관련된 inversion에만 변화가 생긴다는 점을 관찰하여 O(N 2 X)에 문제를 해결할 수도 있다. 부분문제 2 (N 3 000, X 3 000) 수열의 inversion count는 다음 질의를 처리할 줄 알면 쉽게 구할 수 있다. 현재 집합에서 x보다 작은 수의 개수를 반환한다. (1 x X) 집합에 x를 하나 넣는다. (1 x X) 두 질의는 세그먼트 트리, 펜윅 트리 등의 자료구조를 이용하여 매번 O(log X)의 시간에 답할 수 있으며, 때문에 O(N log X) 시간에 수열의 inversion count를 구할 수 있다. 이를 이용하여 Ai = x일 때 inversion count가 어떻게 바뀌는지를 위 질의를 응용하여 구할 수 있으며, 가능한 모든 경우에 대해 시도함으로써 O(N X log X) 의 시간복잡도에 문제를 해결할 수 있다. 부분문제 3 (N 15 000, X 15 000) (1 i N, 1 j X)에 대해 다음의 두 수열을 정의하자. Gi,j : A1,, Ai 1 중 j보다 큰 수의 개수 Li,j : Ai+1,, An 중 j보다 작은 수의 개수 Pn 정의로부터 수열의 inversion count는 I = i=1 Gi,Ai 가 됨을 알 수 있다. 또한, Ai 를 j로 바꿨을 때 inversion count는 I (Gi,Ai + Li,Ai ) + (Gi,j + Li,j )가 됨을 알 수 있다. 따라서 G, L을 이용하여 가능한 O(N X)가지의 경우마다 O(1) 시간에 inversion count를 계산할 수 있다. 또한, G, L의 경우 간단한 dynamic programming 방법으로 총 O(N X) 시간에 계산할 수 있다. G, L을 모두 저장하는 데 많은 메모리가 필요할 수 있으나, 이는 Gi,j 를 구할 때 Gi 1,j 의 값만 필요하다는 사실을 이용하면 필요한 메모리를 O(N )으로 줄일 수 있다. 부분문제 4 (N 300 000, X 1 000 000) 바꿀 위치 j를 고정하고, i < j에 대해 Ai 가 inversion count를 얼마나 늘리는지 생각해보자. Aj 를 [1, Ai 1]의 수 중 하나로 바꾸는 경우 1, [Ai, X]의 수 중 하나로 바꾸는 경우 0만큼 inversion count가 늘어난다. 마찬가지로 k > j에 대해서는 Aj 가 [1, Ak ]에 들어가도록 바꿀 때 0, [Ak + 1, An ]에 들어가도록 바꿀 때 1만큼 inversion count가 늘어난다. 따라서 lazy propagation을 지원하는 최솟값 세그먼트 트리를 이용하여, Aj 를 변경했을 때 inversion count의 최솟값을 O(N log X) 또는 O(N log N ) 시간에 구할 수 있다.
중등부 4, 고등부 3. 화려한 정사각형 풀이 작성자: 구재현 좌표 범위의 최댓값을 X 라 표기한다. 부분문제 1 (N, X 50) 격자 위의 정사각형은 왼쪽 아래 모서리의 x 좌표, y 좌표, 그리고 변의 길이로 표현할 수 있다. 고로 모든 가능한 O(X 3 ) 개의 정사각형을 나열한 후, 이들 안에 들어있는 점들의 서로 다른 색이 K 개 인지를 배열에 마킹하면 된다. 전체 문제가 O(X 3 N ) 에 해결된다. 부분문제 2 (K 50, X 2500) 왼쪽 아래 모서리의 x 좌표, y 좌표를 고정하자. 각각의 색에 대해서, 해당 색의 점을 포함하기 위해 필요한 변의 길이 최솟값을 계산하고, 이의 최댓값을 변의 길이로 취할 것이다. DP [X][i][j] 를 (i, j) 를 왼쪽 모서리로 하는 정사각형이 색 X 의 점을 포함하기 위해 가져야 하는 최소 변의 길이라고 하자. 색 X 의 점이 (i, j) 위치에 있다면 이는 0이고, 아니면 이는 min(dp [X][i + 1][j], DP [X][i + 1][j + 1], DP [X][i][j + 1]) + 1 이라는 점화식으로 계산 가능하다. 전체 문제가 O(KX 2 ) 에 해결된다. 부분문제 3 (K = 2) 두 점 (x1, y1 ), (x2, y2 ) 를 포함하는 최소 크기 정사각형의 변의 넓이는 max( x1 x2, y1 y2 ) 이다. 이는 두 점의 L 거리 (체비셰프 거리) 와 동일하다. 색깔 1의 점과 색깔 2의 점을 각각 하나 골라서 위 값을 최소화해야 한다. 즉, 체비셰프 거리 상 가장 가까운 두 점 쌍을 찾는 것이다. 평면을 45도 회전하면, 위 거리는 x1 x2 + y1 y2 형태의 L1 거리 (맨하탄 거리)로 변환된다. 일반성을 잃지 않고 x1 x2, y1 y2 라고 하자 (4방향으로 모두 회전시키면서 해 보면 된다). 우리는 고정된 (x1, y1 ) 에 대해서 x1 x2, y1 y2 를 만족하며 x2 + y2 를 최소화하는 점을 찾아야 한다. 이는 x 좌표에 대해 스위핑을 하고, y 좌표에 대해서 x + y 의 최솟값을 저장하는 세그먼트 트리를 관리하면 된다. 시간 복잡도는 O(N log N ) 이다. 부분문제 4 (N 50) 부분문제 4에서 6까지는 정사각형을 찾는다고 생각하지 않고, 각 변의 길이가 w, h 일 때 max(w, h) 를 최소화 하는 직사각형을 찾는다고 생각한다. 직사각형은 x 축에 수직한 두 변 x = xs, x = xe, y 축에 수직한 두 변 y = ys, y = ye, 이렇게 총 4개의 정수로 표현할 수 있다. 직사각형의 4개의 변 중 하나에 점이 닿지 않는다면, 점이 닿을 때까지 해당 변을 안쪽으로 당기면서 max(w, h) 를 유지하거나 줄일 수 있다. 이는 우리가 고려해야 할 (xs, xe, ys, ye ) 쌍의 후보가 O(N 4 ) 개라는 것을 뜻한다: xs, xe 는 입력으로 주어진 O(N ) 개의 x 좌표 중 하나고, y 축에 대해서도 동일하기 때문이다. 고로 모든 가능한 O(N 4 ) 개의 정사각형을 나열한 후, 이들 안에 들어있는 점들의 서로 다른 색이 K 개 인지를 배열에 마킹하는 식으로 확인하면 된다. 시간 복잡도는 O(N 5 ) 이다.
부분문제 5 (N 150) xs, xe 를 고정시키고, xs x xe 를 만족하지 않는 점들을 모두 무시해 주자. 이제 y 좌표만이 중요하니, 1 차원에서 이 문제를 해결하면 된다. 점을 y 좌표 순으로 정렬한 후, ys 를 고정해 주고 ye 를 늘려주면서, 서로 다른 색이 K 개가 되면 답을 갱신하자. 1차원 문제가 O(N 2 ) 에 풀리니 전체 문제는 O(N 4 ) 에 풀린다. 부분문제 6 (N 600) 부분문제 5와 동일하게 1차원 문제를 해결한다. ys 를 고정해 주고 ye 를 늘려주면서, 서로 다른 색이 K 개인 것이 확인되면 처음부터 시작하는 것이 아니라 ys 를 한 칸 늘려준 후 (가장 왼쪽 점을 제거한 후) 다시 ye 를 서로 다른 색이 K 개일 때까지 늘려주는 것을 반복한다. 이러한 방식을 Sliding Window 혹은 Two Pointers라고 하며, 점이 한 번 구간에 들어가고 한 번 나가니 O(N ) 에 1차원 문제가 해결된다. 정렬을 해야 한다고 생각할 수 있겠지만, 맨 처음에 점을 y 좌표 기준으로 한번만 정렬해 주면 굳이 매번 정렬할 필요가 없다. 전체 문제는 O(N 3 ) 에 풀린다. 부분문제 7 (N 2500) 길이 R 이하의 화려한 정사각형이 존재하는가? 라는 결정 문제로 문제를 변형해서 해결한다. 이 문제를 해결할 수 있다면, 최소의 R을 이분 탐색으로 찾을 수 있다. R 을 고정할 경우, xs, xe 로 가능한 후보는 O(N ) 개가 된다. 왼쪽 변에 점이 닿는 경우가 N 개이고, 오른쪽 변에 점이 닿는 경우가 N 개이니 2N 개만 시도해 보면 되기 때문이다: 둘 다 닿지 않는 경우는 앞과 비슷하게 왼쪽이나 오른쪽 점에 부딪힐 때까지 구간을 움직여 주면 된다. 이제 부분문제 6처럼 1차원 문제를 O(N ) 에 푼 후 그 답이 R 이하인지를 2N 번 확인해 주면, 결정 문제가 O(N 2 ) 에 풀리고, 전체 문제는 O(N 2 log X) 에 풀린다. 부분문제 8 부분문제 7과 동일한 결정 문제를 Plane sweeping을 사용하여 효율적으로 해결한다. 길이 R 의 x 좌표 구간 [xc, xc + R]를 왼쪽에서 오른쪽으로 움직이자. xc 가 증가하는 과정에서 N 개의 점들은 xc = xi R 시점에 구간에 삽입되고, xc = xi + 1 시점에 구간에서 제거된다. 문제를 해결하기 위해서는, 점들이 추가되고 제거될 때, 모든 K 개의 색의 점을 포함하는 길이 R 의 구간이 있는지를 빠르게 판별해야 한다. distinct[y] 를 [y R, y] 구간을 덮었을 때 얻을 수 있는 서로 다른 색의 개수라고 정의하자. distinct[y] = K 인 x가 존재한다면, 답이 존재한다고 판별할 수 있다. 점 하나가 추가되고 제거될 때 distinct[y] 가 어떠한 식으로 변경되는지 살펴보자. 각 색에 대해서, 해당 색의 점들의 y 좌표들을 std::multiset 과 같은 자료 구조로 관리하자. y 좌표가 yj 인 점을 추가할 때, 기본적으로 이 점이 새롭게 distinct[i] 를 1 증가시킬 구간은 [yj, yj + R] 이 된다. 하지만, 이미 yj 의 직전에 있는 점이 합집합을 덮고 있어서 더하지 않아도 되는 구간, 직후에 있는 점에 가로막혀서 더하지 않아도 되는 구간들이 존재한다. 이 구간은 yj 의 양 옆으로 인접한 점들의 좌표만 알면 케이스 처리로 구할 수 있다. 고로, std::multiset의 lower bound 함수를 사용하면 새롭게 기여하게 되는 구간을 O(log N ) 에 계산할 수 있다. 삭제에서도 역시, distinct[i] 가 1 감소하는 구간을 아주 유사한 방식으로 계산할 수 있다. 이제 문제는 구간에 대해서 특정 수를 더하고, 전체 배열에 값이 K 인 원소가 있는지를 체크하는 구간 쿼리 문제 가 된다. 배열의 특정 원소의 값은 항상 K 이하이므로, 세그먼트 트리에 Lazy propagation을 사용하여 해결할 수 있다. 결정 문제가 O(N log X) 에 해결되니, 전체 문제도 O(N log2 X) 에 해결되어 만점을 받을 수 있다.
고등부 1. 줄임말 풀이 작성자: 김준원 S의 길이는 N, T 의 길이는 M 이라고 하자. 부분문제 1 (S와 T 가 a 만으로 이루어져 있다) 모든 문자가 a 이기 때문에, S는 a 가 N 개, T k 는 a 가 km 개 있는 문자열이다. 언제 S가 T k 의 줄임말이 될까? 모든 문자가 a 이므로, T k 의 길이가 S보다 길거나 같으면 줄임말이 된다. 이제, km N 인 최소의 k를 찾는 문제가 된다. 답은 N M을 소숫점 아래에서 올림한 값이 된다. C언어 코드로는 (N + M - 1) / M과 같이 쓸 수 있다. 부분문제 2 (N 100, M 100) 본 문제를 풀기 위해서 조금 더 쉬운 다음 문제를 생각한다. 두 문자열 A와 B가 주어졌을 때에, B가 A의 줄임말인가? 아래는 이 문제를 O( A + B )에 해결하는 알고리즘이다. ( A 는 A의 길이, B 는 B의 길이) 1. A의 가장 왼쪽에서부터 B의 첫번째 글자를 찾는다. 2. 위에서 찾은 인덱스 다음부터 B의 두번째 글자를 찾는다. 3. 위에서 찾은 인덱스 다음부터 B의 세번째 글자를 찾는다. 4. 5. 위 과정을 끝까지 진행할 수 있으면(즉, B의 마지막 글자까지 모든 글자를 A에서 찾을 수 있으면) B는 A 의 줄임말이다. 그렇지 않고 중간에 실패하면, B는 A의 줄임말이 아니다. 위 알고리즘은 문자열 A에서의 위치와, 문자열 B에서의 위치를 동시에 관리한다는 의미에서 투 포인터 (Two pointers) 알고리즘이라고 부르기도 한다. 이 알고리즘을 이해했다면, 바로 부분문제 2를 풀 수 있게 된다. S가 T 의 줄임말인지, T 2 의 줄임말인지, T 3 의 줄임말인지, 이를 차례대로 줄임말이 될 때까지 판별한다. 줄임말이 되는 것이 불가능하지 않은 이상 답은 언제나 N 이하이고, 따라서 만약 T 1,, T N 까지 검사한 결과 S가 어떤 것의 줄임말도 아니라면, -1을 출력한다. 시간 복잡도는 O(N 2 M )이다. 부분문제 3 (N 10 000, M 100) 부분문제 2의 풀이는 동일한 작업을 공연히 N 번 반복한다. 위 알고리즘을 단 한 번만 수행하는 최적화를 수행할 수 있다. 문자열 T 의 처음과 끝을 이어붙이자. 즉, S가 T 의 줄임말인지 판별하는 도중 T 의 끝에 도달하더라도 다시 T 의 처음으로 돌아가서 알고리즘을 계속 진행한다. 문제의 답은 새로운 알고리즘이 끝날 때까지 문자열 T 를 몇 바퀴 돌았는가 로 쓸 수 있다. 또한, 만약 S의 어떤 글자에서 T 를 한 바퀴 돌았음에도 답을 얻지 못했다면, -1을 출력해야 한다. 이 때의 시간 복잡도는 O(N M )이다. 부분문제 4 (M 1 000) 더 빠른 시간에 작동하는 알고리즘을 만들려면, 이제 T 를 한 칸씩 도는 시간 을 절약해야 한다. T 에서의 각 인덱스 i와 각 알파벳 문자 c에 대해, 다음과 같은 값을 기록(전처리)한 표(2차원 배열)을 만든다. next[i][c]: T 에서 i번째 또는 그 이후에 첫번째로 등장하는 문자 c의 인덱스
위와 마찬가지로, next[i][c]를 구할 때 T 의 처음과 끝을 이어붙여 생각하자. 이와 같은 표를 한 번 만들고 나면, 앞선 알고리즘에서 T 의 다음 인덱스를 찾는 작업 을 한 칸씩 이동하면서 하지 않아도 된다. 가야 할 다음 인덱스 의 번호는 이미 우리가 만들어둔 표에 적혀 있기 때문이다. 그래서, 이제는 표를 만드는 시간을 제외하고 문제를 O(N )에 풀 수 있게 된다. next 배열은 가장 쉬운 방법으로 만들면 O(M 2 )에 만들 수 있고, 이 때에 부분문제 4를 O(N + M 2 )의 시간 복잡도로 해결할 수 있게 된다. 부분문제 5 next 배열을 더 빠르게 채우면 부분문제 5를 풀 수 있다. 아이디어는 다음과 같다. 알파벳 c를 고정하고, next[1][c], next[2][c],..., next[n][c]를 모두 채우는 방법을 생각한다. 먼저, T 에서 알파벳 c가 등장하는 인덱스들을 모두 기록해두고, 정렬된 배열로 만들어두자. 그러면 next[i][c] 는 방금 만든 배열에서 i 이상인 최소 원소가 된다. 이 사실을 알면, 이분 탐색(lower bound 등의 함수를 이용 할 수 있다)을 이용해 next[1][c],..., next[n][c]를 O(M log M )에 채우거나, 투 포인터 알고리즘을 이용해 O(M )에 채울 수 있다. 위 방법을 이용해 next 배열을 채우면 전체 문제를 O(N +ΩM log M ) 또는 O(N +ΩM )의 시간에 풀 수 있으며, (Ω 26는 알파벳의 개수) 두 복잡도 모두 만점을 받기 충분하다.
고등부 2. 순서 섞기 풀이 작성자: 윤교준 배열 A가 이미 비내림차순으로 정렬되어 있다면, 답은 0이다. 이제, A가 비내림차순이 아니라고 가정한다. 부분문제 1 (N 8) 길이 N 의 배열 A에서 한 번의 순서 섞기 연산을 수행할 때, 나올 수 있는 결과의 종류의 수는 O(2N )이다. 왜냐하면, 배열 A의 좌측 혹은 우측 끝을 고르는 작업을 총 N 번 시행하기 때문이다. 순서 섞기 연산은 배열의 값의 순서만을 바꿀 뿐, 값을 바꾸지는 않는다. 고로, 배열 A는 여러 번의 순서 섞기 연산을 통해, O(N!) 종류의 값을 가질 수 있다. 따라서, BFS를 이용하여, 배열 A가 정렬되기 위하여 필요한 연산의 최소 횟수를 O(N! 2N ) 혹은 O(N! N 2N ) 에 구할 수 있다. 부분문제 2 (답은 2 이하) 답이 0인 경우는, 배열 A가 비내림차순인 경우이다. 이제, 답이 1인 경우의 필요충분조건을 알아보자. 답이 1이기 위한 필요조건 순서 섞기 연산을 f 라고 표현하자. 이제, 순서 섞기 연산의 역연산, 즉 f 1 를 생각하자. 만일, A에 f 를 취하여 B를 얻었다고 하자. 이때, 배열 A에서 좌측의 수 로 선택된 수를 차례대로 배열 AL 에 저장하고, A에서 우측의 수 로 선택된 수를 차례대로 배열 AR 에 저장하자. A에서, 좌측의 수 는 왼쪽부터 연속하게 붙어있고, 우측의 수 는 오른쪽부터 붙어있는 형태이다. 따라서, A = AL + AR 임을 알 수 있다. 또한, fr 을 원소의 상대적인 순서를 유지하며 합친 것과 같다. 여기서, 임의의 배열 T 에 배열 B는 두 배열 AL, A 대하여, Te는 T 의 원소를 역순으로 배치한 배열을 의미한다. 따라서, 배열 B에 대한 역연산 f 1 는 다음과 같이 서술할 수 있다: 1. B를 원소의 상대적인 순서를 유지하며, 두 개의 배열 BL, BR 로 나눈다. fr 2. A = BL + B 이제, 배열 A가 단 한 번의 f 연산으로 정렬 가능하다고 가정하자. 이는, A를 정렬한 배열 S에 대하여, S에 f 1 연산을 취하여 A를 얻을 수 있음을 의미한다. S를 나눈 두 배열 SL, SR 은 모두 정렬되어 있다. A = SL + Sf R 이므로, A는 증가하다가 감소하는 형태를 가져야 한다. 따라서, 답이 1이기 위한 필요조건은 배열 A가 증가하다가 감소하는 형태를 가지는 것 이다. 답이 1이기 위한 충분조건 이제, 배열 A가 증가하다가 감소하는 형태를 가진다고 가정하자. 우리는 A를 단 한 번의 순서 섞기 연산을 이용하여 정렬할 수 있음을 보일 것이다. A의 최댓값을 기준으로, (자신 포함) 왼쪽의 수를 모아둔 배열을 AL, 오른쪽의 수를 모아둔 배열을 AR 라고 fr 은 정렬된 상태이다. 하자. 가정에 의하여, AL 과 A fr 을 순서를 유지하며 합친 형태이다. 여기서, 합병 정렬 알고리즘의 A에 연산 f 를 취한 결과 배열 B는, AL 과 A 아이디어를 이용하면, 정렬된 상태의 B를 얻도록, 두 배열을 합치는 방법이 항상 존재함을 알 수 있다. 따라서, 증가하다가 감소하는 형태 를 가지는 배열은 항상 한 번의 연산으로 정렬할 수 있다.
위의 두 논의를 통하여, 답이 1인 경우의 필요충분조건은 배열의 원소가 증가하다가 감소하는 형태를 가진다 임을 알 수 있다. 배열 A가 이 조건을 만족하는지는 O(N )에 쉽게 확인할 수 있다. 답이 2인지는, 이 부분문제에 한하여, 답이 0과 1이 아니다 라는 조건으로 확인할 수 있다. 부분문제 3 (1 Ai 2) 배열 A에서 연속한 1들과 연속한 2들을 각각 하나의 1과 2로 합쳐도 무방하다. K 배열 A에 K개의 2가 존재한다고 하자. 배열 A에서 번째 2를 가준으로, 이 수까지를 AL, 이 수의 오른쪽을 2 K f 개의 연속한 2가 존재하도록 AR 로 나누자. 두 배열 AL, AR 를 합치는 적당한 방법이 존재하여, 배열 B에 2 할 수 있다. 즉, K개의 연속한 2 를, 한 번의 연산을 통해 K 2 개의 연속한 2 가 존재하도록 만들 수 있고, 이것이 최적의 전략이다. 따라서, 답은 dlog2 Ke + 1이다. 이에 대한 엄밀한 증명은 생략한다. 부분문제 4 (모든 Ai 가 서로 다르다) 부분문제 3의 풀이의 아이디어를 확장할 수 있다. 배열 A가 총 K번 증가하다가 감소하는 형태 를 가진다면, K 비슷한 논리로, 한 번의 연산을 이용하여, 번 증가하다가 감소하는 형태 를 가지는 결과 배열을 얻을 수 2 있다. 이 전략 또한 최적이며, 답은 dlog2 Ke + 1이다. 부분문제 5 배열 A에서 인접한 수가 서로 같다면, 이 두 수를 하나로 합쳐주어도 답이 변하지 않음을 알 수 있다. 이러한 성질을 이용하면, 부분문제 5 또한 부분문제 4와 동일한 풀이로 해결할 수 있다. 전체 시간 복잡도는 O(N ), 공간 복잡도는 O(N ) 혹은 O(1)에 해결할 수 있다.
고등부 4. 경계 로봇 풀이 작성자: 윤교준 하나의 센서는 2r의 구간을 감시할 수 있으므로, 2rN < L라면, 답은 1이다. 또한, 2rN L라면, 항상 완벽한 경계가 가능하다. 이제, 2rN L가 성립한다고 가정하자. 부분문제 1 (N 10, L 100, r 10) 다음 네 가지 관찰이 요구된다: 관찰 1-1 로봇이 내려놓은 센서은 다시 집어 옮기지 않아도 충분하다. 관찰 1-2 로봇이 아직 집지 않은 센서 위를 지나간다면, 그 센서를 무조건 가져가는 최적해가 존재한다. 관찰 1-3 센서의 위치는 정수만 고려해도 충분하다. 관찰 2-1 로봇이 K개의 센서를 옮겼다면, r, 3r, 5r,, (2K 3)r, x에 배치하는 것이 최적이다. 여기서, (2K 3)r x (2K 1)r이다. 모든 K에 대하여, 가능한 모든 센서 배치를 생각하자. 관찰 2-1에 의하여, 이러한 배치는 O(rN )이다. (엄밀하 게는, O(L)이다.) 센서 배치가 주어졌을 때, 로봇이 움직여야 하는 거리는 BFS를 통하여 계산할 수 있다. 현재 로봇의 위치, 로봇이 집은 센서의 총 개수, 배치가 완료된 센서의 집합, 총 세 개의 정보로 현재 상태를 완벽하게 표현할 수 있다. 상태의 수가 총 O(N 2N L)이므로, O(L N 2N L) = O(N 2N L2 )의 시간복잡도로 부분문제를 해결할 수 있다. 부분문제 2 (N 30, L 2000, r 30) 다음의 추가적인 관찰이 요구된다: 관찰 3 잉여의 센서를 가지고 있는 로봇은 무조건 전진하는 최적해가 존재한다. 센서의 최종 배치를 Y1, Y2,, YK 라 하자. 로봇의 최적 전략은 다음 DP를 이용하여 계산할 수 있다: DP[n] := 현재, 로봇이 Yn 에 위치하고, 어떠한 센서도 가지고 있지 않으며, 옮긴 n개의 센서는 각각 Y1, Y2,, Yn 에 위치시켰을 때, 이를 위하여 로봇이 움직여야 하는 최소 거리. DP[1],, DP[K]의 값을 모두 알고 있다면, 배치 Yi 를 달성하기 위하여 필요한 최소 이동 거리는 O(K 2 ) 혹은 O(K)에 계산할 수 있다. DP 배열 또한 O(K 3 )에 모든 값을 계산할 수 있다. 따라서, O(LN 3 )의 시간 복잡도로 본 부분문제를 해결할 수 있다.
부분문제 3 (N 500) 다음 관찰이 요구된다: 관찰 4-1 센서 배치 Yi 가 주어졌을 때, 로봇이 xl 에서 왼쪽으로 방향을 바꾸었다면, Xi xl 를 만족하는 i의 개수와 Yj xl 을 만족하는 j의 개수가 같다. 관찰 4-2 센서 배치 Yi 가 주어졌을 때, 로봇이 xr 에서 오른쪽으로 방향을 바꾸었다면, Xi < xr 을 만족하는 i의 개수와 Yj < xr 을 만족하는 j의 개수가 같으며, Xi xr 을 만족하는 i의 개수가 Yj xr 을 만족하는 j의 개수보다 작다. YK = (2K 1)r을 만족하는 모든 배치 Yi 에 대하여, 관찰 4에 의하여 로봇이 지그재그로 움직이는 과정을, 부분문제 2와 유사한 DP로 표현할 수 있다. 이 DP 배열은 O(K 2 )에 계산할 수 있다. 답을 계산하는 과정은, 로봇이 마지막 센서를 처리하기 위하여 움직여야 하는 경로를 예외적으로 계산해준다면, O(K) 혹은 O(K 2 )에 할 수 있다. 따라서, O(N N 2 ) = O(N 3 )의 시간 복잡도로 본 부분문제를 해결할 수 있다. 부분문제 4 (N 2500) 부분문제 3의 DP를 구현하였다면, 누적 합 아이디어를 이용하여, DP 계산을 O(K)에 할 수 있다. 이 경우, 시간 복잡도는 O(N 2 )이다. 부분문제 5 다음 관찰이 요구된다: 관찰 2-2 관찰 2-1에서 유의미한 x의 값은 오직 두 개이다. 관찰 2-3 관찰 2-1에서 유의미한 K는 오직 하나다. 따라서, 전체 시간 복잡도는 O(N ), 공간 복잡도는 O(N ) 혹은 O(1)이다.