19/04/08 알고리즘 문제 토론

[접기]

목차

  • 1. 활동 개요
  • 2. 토의 문제
  • 3. 풀이


1. 활동 개요



2. 토의 문제



3. 풀이


3.1. Korv


문제 개요
$N$개의 column을 가진 히스토그림이 하나 주어진다. 초기 각 히스토그림의 높이는 $X_1, X_2, ..., X_n$이다. 이때,
위의 조건을 만족하는 히스토그램을 만들고자 한다. 각 히스토그램의 높이를 1변화하는데는 1의 비용이 들 때, 위와 같은 성질을 만족하는 히스토그램을 만들기 위한 최소 비용을 구하라.

풀이
우선 root가 될 열이 $i$라는 가정 하에 문제를 풀어보자. 이 문제를 쉽게 풀기 위해, 다음과 같은 높이들을 가지는 히스토그램을 만들어보자.
$$b_j=h_j + |i-j|$$
이떄, 문제에서 가정한 수식을 조건을 만족하는 히스토그램이 $b$에서는 어떤 형태를 가지고있을지 고민해보면, $b_i$의 높이가 모두 같은 히스토그램을 만드는대 필요한 최소 비용을 구하는 문제가 된다.

여기서, 높이 $t$를 맞추기 위해 필요한 최소 비용을 구해보자. 다음과 같은 함수
$$f(t) = (높이가 t인 히스토그램을 만들기 위한 최소 비용)$$
이라 정의하면, 아래로 볼록한 2차함수와 비슷한 그림이 만들어지는 것을 확인할 수 있다. 여기서, 극점은 $b_i$의 중간값과 같다. (높이가 $t$일 때 t보다 작은 $b_i$의 개수, t보다 큰 $b_i$의 개수를 구하고, $t+1, t-1$일 때 함수값이 어떻게 변화되는지 확인하면 쉽게 증명할 수 있다.) 따라서, 모든 $i$에 대해 $b$배열을 만들고 그 중간값을 찾아(중간값을 찾는 과정 중 원래의 $h$배열의 높이가 음수 혹은 0이 되는 경우를 잘 고려해야 한다) 필요한 최소 비용을 계산하는 방식으로 답을 구할 수있다. 이 경우 시간은 $O(N^2)$이 걸린다.

이를 빠르게 하기 위해 $b$배열을 좀 더 일반적으로 사용할 수 있는 방법을 연구해보자. $i$번을 root로 선택했다면, $ji$인 $b_k$의 값은 $$b_j = h_i + i - j$$ $$b_k = h_i + k - i$$라 할 수 있다. 이를 위해 왼쪽 구간에 있는 값을 확인하기 위한 $bl$배열과 오른쪽 구간에 있는 값을 확인하기 위한 $br$배열을 만들고, 각 배열의 원소를 다음과 같이 정의하자.
$$bl_j = h_j + n - j$$
$$br_k = h_k + k$$
이후 적절한 root $i$를 선택헀을 때 중간값을 구해야 한다. 어떤 수가 중간값이 되려면 그 수보다 작은 숫자의 수가 $\lfloor{N/2} \rfloor$보다 작거나 같아야 한다. 이때 왼쪽 구간에서 $t$보다 작은 수는 $bl_j < t - n + j$들이고, 오른쪽 구간에서는 $br_k < t - k$들이다. 이를 이용하여 중간값을 Binary Search로, 개수를 Segment Tree와 같은 자료구조를 이용하여 빠르게 계산할 수 있고, 이 떄 시간복잡도는 $O(N \log^2{N})$이다.

3.2. Cow at Large


문제 개요
$N$의 크기를 가진 트리가 주어진다. 여기서 소가 사람들을 피해 도망쳐야 한다. 트리의 간선의 길이는 항상 1이며, 사람과 소 모두 시간당 1의 거리를 움직이며, 동시적으로 움직인다. 소는 사람들을 피해 리프노드에 도달하면 도망친 것으로 간주된다. 사람들은 이를 막기 위해 적절한 리프노드를 골라 소가 항상 도망칠 수 없도록 할 것이다. 이 때, 소가 $1,2,...,N$번 노드에 있을 때 소가 리프노드로 도망치지 못하게 하기 위한 최소 사람의 수를 모두 구하여라.

풀이
임의의 루트를 잡고, 각 노드에서 거리가 l의 위치에 소가 있을 때 해당 서브트리에 속하는 리프노드로소가 가는것을 막기 위한 필요한 사람의 최소 수를 $d_{i,j}$이라 하고, 그 노드에서 가장 가까운 리프까지의 거리를 $md_i$라 하자. 우선
$$d_{i,l} = 1\ \ if\ \ l \geq md_i $$
를 만족한다. (당연하게도, $md_i$보다 멀면 가장 가까운 리프에서 와서 다른 리프로 가는 것을 막을 수가 있기 때문이다.)
이외의 다른 값들은 $$ d_{i,l} = \sum_{u is child of i}{d_{u,l+1}} $$ 이다. (해당 노드로 소가 내려갔을 때 막을 수 있는 최소 사람의 수가 자식 노드에서 거리가 $l+1$떨어진 노드에서 오는 소들을 막기 위해 필요한 최소의 사람 수이기 때문이다.) 이런 식으로 리프부터 시작하는 DP를 한 번 실행한 후 다시 루트로부터 내려가면서 다른 서브트리에 있는 값을 합치며 답을 계산하면 된다. 이 경우 시간복잡도는 $O(N^2)$이 된다.
,
아직은 부족하므로, 시간을 좀 더 줄여야 한다. 생각해보면, $d_{i,l}$에서 $d_{i,l-1}$과 $d_{i,l}$의 값이 다른 경우가 그리 많지 않을 것 같아, 길이에 해당하는 부분을 구간으로 관리를 해주면 될 것 같다는 느낌이 든다. 이를 한 번 보여보자.
[알림:정보(이후 풀이는 완벽하게 증명하지 않았습니다.)]
$c_i = (\#\ of\ l\ which\ d_{i,l-1} \neq d_{i,l})$이라 하자. 이런 분할이 있으려면 그 노드로부터 거리가 다른 리프가 존재해야 한다는 말이다. 따라서 $i$번 노드의 서브트리에서는 $i$번 노드로부터 거리가 서로다른 노드가 $c_i$개 있음을 알 수 있다. 이들의 거리가 모두 다를 떄 $c_i$의 최댓값은 얼마인가? 그 노드와 리프사이이에 노드 개수가 거리가 되므로, 거리 1부터 차례대로 부여하면, $c_i \leq O(\sqrt{N})$임을 파악할 수 있다. (1, ..., T에 대한 합을 계산) 따라서, 각 노드가 가지고 있어야 될 DP 테이블의 수는 $\sqrt(N)$으로 bound된다. 이 정보를 이용하면 $O(N\sqrt{N} \log{N})$의 시간에 풀 수 있다.
(P. S. 이 자료를 적절히 관리하고 update하기 위해 log가 붙었는데, $O(N\sqrt{N})$만에 할 수 있다면 알려주세요!)