RUN@KAIST 8/9 방학 연습 풀이

1. 회색 영역

해당 데이터가 어떤 막대에 들어가게 되는지 판별할 수 있는 기준이 전부 문제에 적혀 있다. 기준에 따라 각 막대에 들어간 개수를 세주자. 

가장 큰 값을 들고 있는 막대가 마지막 막대이니, 전체 막대의 개수를 알 수 있다. 막대 개수와 각 막대의 높이를 알면 문제에 적힌 대로 답을 계산할 수 있다.

2. 편집 거리

문제 디스크립션이 많이 엉망이다 ㅠㅠ 다시 문제를 정리하면 다음과 같다.

초기 문자열 S와 최종 문자열 T가 주어진다. 입력 문자열은 처음에 S가 들어있고 출력 문자열은 비어있다. 입력 문자열의 맨 앞 글자를 삭제하고 출력 문자열의 맨 뒤에 글자를 추가하는 다양한 연산들이 주어진다. 연산 후에 입력 문자열은 비어야 하고, 출력 문자열은 T 여야 한다. 복사를 제외한 연산의 개수를 스크립트의 길이라 할 때 가장 짧은 편집 스크립트를 찾자.

일단 이러한 형태의 "편집 거리" 문제는 동적 계획법으로 해결하는 방법이 아주 잘 알려져 있다. LCS (최장 공통 부분 문자열) 과 굉장히 비슷한 형태의 동적 계획법으로 해결할 수 있는데, 상태 정의는 DP[S의 몇 글자가 제거되었는가][T의 몇 글자가 출력되었는가] 와 같고, 문제에 주어진 모든 연산을 이러한 상태들의 전이로 표현할 수 있다. 우리는 P[0][0]을 초기 상태로 해서, DP[S의 길이][T의 길이]를 최종 상태로 하는 동적 계획법을 해결하면 된다. O(nm) 시간 / 공간 복잡도로 이 동적 계획법을 해결하고, 답을 역추적하는 (최소 횟수 뿐만 아니라 정확한 sequence를 찾는) 방법을 완전히 이해하고 있다고 가정한 후 풀이를 시작한다.

nm이 3억 정도이기 때문에 저 동적 계획법을 알면 시간 제한은 쉽게 맞출 수 있지만, 메모리 제한이 문제이다. 역추적 배열과 DP 배열을 모두 O(nm)으로 잡으면 문제의 메모리 제한을 절대 넘길 수 없기 때문이다. 사실, 여기서 DP 배열은 선형 시간 복잡도로 줄일 수 있다. DP[i][*] 가 DP[i-1][*]에만 의존하기 때문에, O(m) 크기 배열을 두개 정도 잡은 후 바로 전 행 (DP[i-1][*]) 만 가지고 현재 행을 계산하는 식으로 하면 되기 때문이다. 하지만, 이러한 방식으로 역추적 배열을 줄일 수는 없다.

일단 이 문제의 제한이 원문의 제한 (32MB)와 다르기 때문에 이를 어렵지 않게 줄일 수 있는데, 역추적 배열에 저장되는 정보가 단 4가지 (a / c / d / x) 종류임을 활용하는 방식이다. 4가지 정보를 저장하는 데 드는 비트는 고작 2개밖에 없고 (00 / 01 / 10 / 11), 고로 1바이트 (char) 변수에 역추적 배열 원소 4개를 저장할 수 있다. Trace[0][4*i] + Trace[0][4*i] * 4 + Trace[0][4*i+2] * 16 + Trace[0][4*i+3] * 64를 저장한다 생각하면 된다. 이는 비트마스크를 활용해서 우겨넣을 수 있다. 계산하면 72MB 정도의 배열만 가지고 역추적 배열을 온전히 가질 수 있는 셈이다. 이렇게만 해도 메모리 제한을 맞춰서 통과시킬 수 있다.

하지만, 이 문제는 놀랍게도 역추적 배열을 온전히 저장할 필요 없이 O(nm) 시간 복잡도와 선형 메모리에 해결할 수 있는 방법이 알려져 있다. Hirschberg's Algorithm이라고 불리는데, 분할 정복을 활용한 알고리즘이다. 이 알고리즘에 대해 설명하겠다.

먼저 DP를 사용해서 최댓값을 찾는다는 것의 그래프 이론적인 해석을 생각해 보자. DP 배열은 사실 거대한 격자 모양의 DAG라고 생각할 수 있고, (i, j)에서는 (i+1, j) / (i+1, j+1) / (i, j+1) 로 가는 세 개의 가중치 있는 방향성 에지가 있을 것이다. DP[0, 0]이 기저이고, DP[n, m]이 최종 상태일 때 최솟값을 구하고 역추적한다는 것은 (0, 0) 정점에서 (n, m) 정점으로 가는 최단 경로 (가장 가중치 합이 작은 경로) 를 찾는 문제와 동치이다. 

문제를 일반화해서 (sx, sy)에서 (ex, ey)로 가는 최단 경로를 찾는다고 생각해 보자. 최단 경로는 자명히 mx = (sx + ex) / 2 선을 지날 것이다. 만약에 최단 경로가 (sx, sy)에서 (mx, T) 를 거쳐서 (ex, ey)로 간다는 사실을 알았다고 생각해 보자. 우리는 (sx, sy)에서 (mx, T)로 가는 최단 경로를 찾고, (mx, T)에서 (ex, ey)로 가는 최단 경로를 찾는 식으로 더 작은 문제를 해결하면 된다 (분할). 그리고 이들이 찾은 최단 경로 사이에 (mx, T) 를 지났다는 정보를 추가해 주면, 우리 역시 최단 경로를 찾을 수 있다 (정복). 트리의 중위 순회를 하듯이, (sx, sy) -> (mx, T) 최단 경로 찾음 + (mx, T) 지났다는 정보 추가 + (mx, T) -> (ex, ey) 최단 경로 찾음 과 같이 구현해 주면 편리하다.

아무튼, 이제 핵심은 T를 찾는 것인데, (ex - sx) * (ey - sy) 번의 연산을 사용해서 동적 계획법을 그냥 돌려주면 된다. 시작점을 [sx, sy]로 했을 때, [mx, T] 로 가는 최단 경로의 길이를 알고, 끝점을 [ex, ey]로 했을 때, [mx, T]에서 오는 최단 경로의 길이를 모두 알면 이 중 최솟값을 주는 T가 무엇인지 알 수 있다. [sx, sy]에서 [mx, T]로 가는 경로의 길이는 그 전에 하던 동적 계획법과 똑같은 방식으로 하면 되고, [mx, T]에서 [ex, ey]로 가는 경로의 길이도 그 전에 하던 동적 계획법을 거꾸로 하면 된다. 모두 DP[i-1][*] 혹은 DP[i+1][*]만 알면 DP[i][*]를 알 수 있기 때문에 선형의 공간 복잡도로 해결 가능한 DP이다.

이 알고리즘의 시간 복잡도는 어떻게 될까? T(x, y) = T(x / 2, y - k) + T(x / 2, k) + O(xy) 이다. 재귀호출 단계가 한 단계씩 깊어질 때마다. 총 영역 (xy)의 합이 반으로 줄어든다, 고로 시간 복잡도는 O(nm + nm/2 + nm/4 + nm/8 + ...) = O(nm)이다. 공간 복잡도는 선형이다.

3. Hidden Tree

준비중

4. 점 분리

흰 점과 검은 점을 기준으로 컨벡스 헐을 만들어 보자. 만약에 두 컨벡스 헐이 교집합을 가진다면 (점이나 모서리가 겹치는 것도 교집합이라 한다.) , 절대 둘을 직선으로 분리할 수 없다. 한편, 두 컨벡스 헐이 교집합을 가지지 않는다면, 항상 그 사이에 분리하는 직선을 만들 수 있다. 이는 귀류법으로 생각하면 대충 증명할 수 있다.

문제는 두 볼록 다각형이 교집합을 가지는가를 판별하는 문제로 단순화 되었다. 두 볼록 다각형이 교집합을 가지는 경우는 두 가지 경우 뿐이다.

 * 한 볼록 다각형이 다른 볼록 다각형 안에 완전히 들어가 있다.

 * 한 볼록 다각형의 선분과 다른 볼록 다각형의 선분이 만나는 점이 존재한다. 

첫번째 경우는 볼록 다각형의 각 점들이 다른 볼록 다각형 안에 들어가 있는지를 판별하면 되고, 두번째 경우는 모든 선분의 쌍을 돌면서 교차하는 선분 쌍이 존재하는 지 판별하면 된다. O(1) 선분 교차 판별 알고리즘은 종만북 등에도 나와있으니 설명을 생략한다. 입력이 크지 않기 때문에 O(nm) 알고리즘으로 충분하다.

예제가 좀 강해서 다행이지만, 코너 케이스가 많은 문제이다. 다음과 같은 경우들을 유의하자!

 * n = 1, n = 2

 * 세 점이 한 직선 상에 있음

 * 두 선분이 평행함

5. 스무고개

특징의 개수가 11 이하로 상당히 작다는 것을 활용해 보자. 한 특징을 두 번 묻지는 않을 테니, 한 특징에 대한 우리의 정보는 세 가지 중 하나이다 : 모르거나, 참임을 알거나, 거짓임을 알거나. 이렇게 되면, 현재 무슨 정보를 가지는 지를 상태로 가지는 동적 계획법을 생각해 볼 수 있다. 정보는 3^M 가지의 경우의 수가 있고 3^11 = 200000 정도이니 이렇게 접근해 보자.

초기에는 아무 것도 모르는 상태에서 시작해서, 최종적으로 우리는 찾아낸 정보로 유일한 물체를 찾을 때까지 (즉, 찾아낸 정보를 만족하는 물체가 단 하나일 때까지) 질문을 할 것이다. 상태 전이는 다음과 같다. 이번 상태에서 우리가 X라는 특징을 모르고, 그에 대해서 질문을 했다고 하자. 우리는 질문을 통해 X가 참이거나 거짓임을 확인할 수 있다. 가장 운이 안 좋을 때 몇 번의 질문을 해야 하는지를 구해야 하기 때문에 이 참 / 거짓 중 질문 횟수를 최대로 하는 결론이 우리가 X를 질문한 이후 더 해야할 질문의 개수이다. 가능한 X를 모두 돌면서, 추가 질문 횟수의 최솟값을 찾으면 현재 상태에서 추가해야 하는 최소 질문 수를 알 수 있다. 

이렇게 하면 O(3^M *(NM)) 의 시간 복잡도가 걸리고, 시간 초과가 난다. 각 상태마다 현재 정보를 만족하는 물체가 유일한지 아닌지를 계산해야 하고, 이것이 O(NM) 시간을 소모해 오버헤드가 심하기 때문이다. 이는 또 하나의 동적 계획법으로 해결할 수 있다. cnt[특징] = 현재 특징을 만족하는 물체의 개수라고 했을 때, 모르는 특징이 없다면 단순히 현재 특징을 만족하는 게 있는지 없는지를 찾아주고, 있다면 그 특징을 아는가 / 모르는가를 기준으로 상태를 나누자. 이 최적화를 추가하면 O(3^M * M + N) 시간 복잡도로 문제를 해결할 수 있다.

6. 트리 유사도

먼저 관찰해야 하는 것은, 삽입과 삭제는 역연산의 관계를 가지기 때문에, T1에 무언가를 삽입해서 T2를 만드는 대신 T2에서 노드를 삭제한다고 생각해도 좋다. T2에서 노드를 제거한 후, T1과 T2에서 똑같이 삽입을 하면, 결국 상황은 T1에 무언가가 삽입된 상황이기 때문이다. 고로 굉장히 골치아프게 생긴 노드 추가를 고려하지 않아도 된다.

트리에 대해서 편집 거리를 잘 살펴보자. 루트는 제거할 수 없으니, 루트 아래에 있는 포레스트들에서 적당히 노드를 매칭시키고 삭제시켜야 할 것이다. 순서가 중요하니, 두 포레스트 F1, F2에서 첫번째 트리들의 루트를 생각해 보자. 경우는 세 가지다.

 * F1에서 첫번째 트리의 루트를 제거

 * F2에서 첫번째 트리의 루트를 제거

 * 첫번째 트리의 루트를 F1, F2 모두에서 제거하지 않으니, 첫번째 트리를 살려야 한다. F1에서 첫번째 트리, F2에서 첫번째 트리를 매칭 시킨 후, 이 트리를 제거시킨 나머지 포레스트 F1, F2를 매칭. (매칭하고자 한 루트는 제거할 수 없으니 똑같이 포레스트에 대한 점화식으로 정의된다.)

여기서 관찰해야 하는 것은, 만약에 노드들을 DFS preorder 순으로 번호를 부여했다면, 세 연산을 진행했을 때 포레스트들의 형태가 DFS preorder가 연속한 정점의 부분집합으로 정의된다는 거다. 고로 포레스트를 DFS preorder의 구간으로 표현할 수 있다. 상태 전이가 $O(1)$이니 $O(N^2M^2)$ 에 문제가 풀린다.

7. 학회원

문제에서 연결 관계가 모두 raw string 형태로 주어져서 상당히 귀찮다. 일단 스트링을 전부 이름 단위로 split하자. 그리고 std::map을 활용하여 주어진 모든 이름에 번호를 붙여주자. 그러면 모든 입력이 정수로 변환되니 편하다.

먼저 사람이 아니라 학회인 번호들을 전부 체크해 주자. 문제를 그래프로 모델링하자. A_0번 학회가 A_1 ... A_(n-1)을 포함한다는 것을 A_0 -> A_1, A_0 -> A_2, A_0 -> A_3과 같은 n-1개의 간선으로 생각해 주면, A_0번 학회에서 도달 가능한 사람의 수가 A_0번 학회의 학회원임을 알 수 있다. 어떤 학회에 속하는 다른 학회에 속하는 다른 학회에 속하는... 사람이 학회원이고, 저러한 포함 관계는 그래프에서의 경로에 대응하기 때문이다.

1번 학회에서 도달 가능한 사람의 수는 DFS와 같은 탐색 알고리즘으로 간단하게 셀 수 있다.

8. Cubist Artwork

먼저 가로로 보이는 최대 높이 수열과 세로로 보이는 최대 높이 수열을 정렬하고 시작하자. 정렬해도 답에는 아무 상관이 없다.

만약에 H라는 높이의 블록이 가로축에서 A번 보이고 세로축에서 B번 보였다고 하자. 그렇다면 H 높이의 블록은 최소 max(A, B)만큼 필요함을 알 수 있다. 고로 모든 H에 대해서 H * min(A, B)의 합이 답의 하한이다. (답이 이것보다 작아질 수 없다는 뜻이다.)

그보다 작은 답을 찾을 수 없으니, H * min(A, B)의 합만큼만 블록을 사용하는 답은 찾을 수 있을까? 블록을 대각선으로 나열하는 식으로 답을 찾을 수 있다. 예를 들어 높이 3이 가로로 5번, 세로로 3번 보인다면

3oooo

o3ooo

oo333

과 같이 나열하는 식이다. A나 B가 0이 될 수 있지만 이 때는 맨 오른쪽 혹은 아래쪽 (최대 높이가 있는 다른 영역)에 나열하는 등으로 해결할 수 있다. H * min(A, B)에 답을 찾을 수 있고 그보다 작은 답은 불가능하니 답은 H * min(A, B)의 합이다.

이제 문제는 H * min(A, B)의 합을 빠르게 구하는 방법이다. 여러 방법으로 구할 수 있는데, 그 중 하나는 등장하는 모든 수들의 리스트를 뽑아서, 이 수들이 A나 B에서 몇 번 등장하는 지를 이진 탐색등으로 세는 식이다. 어떻게든 O(nlgn)에 가능하다.