2021 국대 멘토링 일지 - 1주차

이번 주부터 국대 멘토링 교육이 시작되었습니다. 내신 준비로 시간이 충분하지 않아 일부 문제들은 풀이만 생각하고 구현을 아직 해 보지 않았는데, 시험이 끝나는 대로 구현해 볼 예정입니다. 제가 배정받은 문제 세트는 다음과 같습니다.

 

#1. Trous de Loop (BOJ 18368)

조건을 만족하는 가장 긴 구간을 찾는 문제이므로 투 포인터를 이용합니다. 각 구간에서 자기 내부의 길이 $d$ 구간 중 구간 합이 최대인 것을 찾아야 하는데, 이 문제는 사실 누적합을 이용하면 투 포인터를 돌리면서 구간 내의 최댓값을 빠르게 찾는 문제가 되고, 이는 덱으로 해결 가능합니다. 따라서 문제가 쉽게 풀립니다.

 

Time Complexity: $O(N)$

#2. Highway Modernization (BOJ 18370)

트리에서 간선 하나를 제거하고 다른 간선을 이어 트리를 만들 때 지름의 최솟값과 최댓값을 구하는 문제입니다. 어떤 간선을 자르기로 했다면, 그 간선을 기준으로 트리 A와 트리 B로 나뉠 것입니다. 트리 A의 점 X와 트리 B의 점 Y를 이을 때 지름은 max(X에서 시작하는 A 내부의 최장 경로의 길이 + Y에서 시작하는 B 내부의 최장 경로의 길이 + 1, A의 지름, B의 지름)이 됩니다. 이것을 각 간선별로 빠르게 구할 수 있으면 될 것입니다.

 

A의 지름을 구할 수 있다면, X에서 시작하는 A 내부의 최장 경로의 길이는 최대 A의 지름이고, 최소 (A의 지름 + 1) / 2의 floor입니다. 이는 만약 지름이 여러 개라면, 모든 지름이 지나는 한 점이 존재하기 때문입니다. 한쪽 서브트리의 지름은 트리 DP로 구할 수 있고, 조금 귀찮은 dfs를 통해 루트 방향 서브트리의 지름도 구할 수 있습니다. 따라서 문제가 해결됩니다.

 

Time Complexity: $O(N)$

#3. Cow Optics (BOJ 10031)

문제를 단순하게 정리하면, 원점에서 쏜 광선과 목표 지점에서 사방으로 쏜 광선 사이 교점의 수를 구하는 문제가 될 것입니다. 이 광선들은 처음 발사 지점으로 돌아오거나, 유한 번 반사됨을 보일 수 있으므로 따라서 유한 개의 선분/반직선으로 표현할 수 있습니다. 광선이 다시 원점을 지나면 안 된다는 조건은, 목표 지점에서 쏜 광선을 원점을 지나기 직전에 끊어 주면 됩니다.

 

광선의 교점 수를 구할 땐 원점에서 쏜 광선을 기준으로 봐 줄텐데, 원점에서 쏜 광선이 가로 방향일 때 / 세로 방향일 때를 따로 생각하며 스위핑 세그먼트 트리를 이용하면 쉽게 할 수 있습니다.

 

Time Complexity: $O(N \log N)$

#4. 애완 트리 (BOJ 19547)

$S=1$인 경우에만 풀면 됩니다. $E \le 400N$으로 가정해도 됩니다. 트리 DP를 너무나도 하고 싶게 만드는 문제입니다.

 

트리의 지름을 구할 때에는 현재 노드에서 아래까지의 최대 깊이와 현재 최대 지름을 들고 다닙니다. 이 아이디어를 비슷하게 적용하면 $DP[x][y]$: $x$번 노드 서브트리까지만 봤을 때, 지름이 $E$ 이하이고 가장 깊은 리프 노드까지의 거리가 $y$인 경우의 수로 정의합니다.

 

두 개의 DP배열 $DP[u]$, $DP[v]$를 $DP[x]$ 역시 하나 합칠 때 $O(400N)$ 시간이 들어서 총 세제곱 시간에 매우 쉽게 풀립니다. TL ML이 이렇게 큰 게 잘 이해가 되지 않았습니다.

 

Time Complexity: $O(N^3)$

#5. Dam (ARC 072 D)

아직 풀이를 찾지 못했습니다.