티스토리 뷰
블로그를 너무 방치해 둔 거 같아서 최근 풀었던 문제를 모아서 올려보기로 했다.
BOJ 17474 수열과 쿼리 26
Segment Tree Beats 구현하면 된다.
BOJ 1763 트리 색칠
이런 유형의 문제는 Best Vertex를 고른 다음, 그 부모와 합쳐주는 방식으로 해결하는 것이 전형적이다. 그 정점을 다음에 갈 수 있다면, 무조건 그 정점으로 가는 것이 이득이기 때문에 아예 부모 정점과 합치는 것이다. 이 문제도 마찬가지로 풀릴 것 같으니, 몇 가지 변수를 추가해서 해결해 보자. $X[i]$를 그 정점을 방문하고 나서 흐르는 시간의 양이라고 하고, $B[i]$를 그 정점을 방문하고 나서 얻는 추가적인 Cost라고 두자. Exchange Argument를 사용하면 $C[i] / X[i]$가 가장 큰 정점이 Best Vertex임을 알 수 있다. $C[i], X[i], B[i]$를 부모와 합칠 때 적절히 갱신해주자. 제한이 작아서 Heap 등을 사용하지 않고 그냥 매번 찾아줘도 시간 안에 문제를 해결할 수 있다.
BOJ 14510 Blazing New Trails
풀이를 알고 있던 문제이다. Alien Trick을 사용하면 문제를 해결할 수 있다. 특별한 간선들에 $x$만큼의 가중치를 더하고, 이 때 스패닝 트리에 포함된 특별한 간선의 개수와 그때의 답을 반환하도록 하면 이분 탐색으로 문제를 해결할 수 있다. 이 때 답을 항상 찾을 수 있는 이유는 다음과 같다. 처음에 모든 간선들을 가중치 순으로 정렬했다고 하면, $x$가 점점 커짐에 따라 특별한 간선들은 점점 뒤쪽으로 밀려날 것이다. 이때 가중치가 같은 간선들의 순서는 아무렇게나 둬도 항상 MST를 찾을 수 있기 때문에, 특별한 간선들의 순서가 '한 칸씩' 뒤로 밀려난다고 생각해도 된다. 어떤 특별한 간선이 한 칸씩 뒤로 밀려날 때마다 MST에 포함된 특별한 간선의 수의 변화량은 항상 1 이하일 것이다. (디테일은 생략) 그러므로 $x$를 변화시키면, 답에 포함된 특별한 간선의 수가 $w$가 되는 순간이 항상 존재한다.
물론 실제로 구현할 때 특별한 간선들의 순서를 한 칸씩 움직여서 답을 구할 필요는 없고, Alien Trick을 사용하는 다른 문제처럼 $x$만큼 더했을 때 답에 포함되는 특별한 간선 개수의 최솟값과 그때의 답을 구해 주면 충분하다. $f(k)$를 특별한 간선이 $k$개 포함될 때 답이라고 하면, 윗 문단에서 $f(k)$의 볼록성을 증명한 것이나 다름없기 때문에 최솟값만 알면 $f$에 대한 정보를 충분히 얻을 수 있다.
BOJ 3311 Traffic
일단 오른쪽 끝 정점들에서부터 BFS를 돌려서 아예 가능성이 없는 왼쪽 끝 정점들을 제거하자. 이제 어떤 오른쪽 정점 $v$를 끝점이라고 하면, 시작점으로 가능한 정점들의 집합은 왼쪽에서 구간을 이룬다. 즉, 시작점으로 가능한 정점 중 가장 위에 있는 정점과 가장 아래 있는 정점을 알면, 개수도 알 수 있다. SCC로 묶고 DAG 상에서 DP를 돌려 주면, 이를 구할 수 있다.
BOJ 17955 Max or Min
1.5년 전에 계절학교 모의고사에서 풀었던 문제인데, 어떻게 푸는지 까먹어서 다시 풀었다. ㅋㅋ
$k$일 때 답을 $f(k)$라고 하면, $f(k)$를 구할 때 각각의 값이 $k$보다 작은지, 같은지, 큰지만 중요하기 때문에 각 수들을 $-1, 0, 1$로 표현할 수 있다. 모든 수를 $0$으로 만드는 것이 목표이므로 수열에 $0$이 없으면 불가능하다. $0$에서 시작해서 인접한 $-1, 1$들을 $0$으로 만들어보는 것을 몇 번 해 보면, $0$이 아닌 수는 무조건 한 번은 건드려야 하고, $-1$에서 $1$로 바뀌거나 $1$에서 $-1$로 바뀔 때 추가적인 작업이 한 번 더 필요함을 알 수 있다. 좀 더 관찰을 해보면, $-1$과 $1$이 연속되어 나올 때는 중간에 튀어나온 $1$(혹은 $-1$)들을 모두 $-1$(혹은 $1$)로 만든 다음에 남은 $-1$들을 $0$으로 만들어주면 된다는 것을 알 수 있다. $1$과 $-1$이 반복되어 나오는 구간이 중요한 것 같으니, 얘네들을 관리하면 될 것 같다. $k=1$부터 시작해서 $k$를 $1$씩 키우면, 각 원소가 최대 두 번 업데이트된다는 것을 알 수 있다. 이제 세그먼트 트리로 각 구간의 답, 왼쪽 ($1, -1, \cdots$) chain 정보, 오른쪽 ($1, -1, \cdots$) chain 정보를 관리하면 $O(N log N)$ 시간에 문제를 해결할 수 있다.
BOJ 17667 Virus Experiment
이 문제는 19년 당시 합숙교육 때 JOIOC를 치면서 봤던 문제고, 끝나고 풀이도 들었던 것 같지만 역시 기억이 안 나서 다시 풀었다. 위, 아래, 왼쪽, 오른쪽 정점의 상태에 따라 $2^4=16$가지 경우를 미리 전처리해놓으면, 현재 감염된 정점들이 있을 때 다음에 감염될 정점을 빠르게 찾을 수 있다. $HW$개의 정점에 대해서, 각 정점이 시작점일 때 감염되는 정점들을 dfs로 확인하되, 이미 전에 봤던 시작점이 포함되면 dfs를 즉시 종료하자. 최솟값을 찾는 것이기 때문에, 만약 현재 dfs에서 이전에 이미 봤던 시작점이 포함된다면 결과는 최솟값이거나 최솟값보다 클 것이고, 다시 세 줄 필요가 없다. 이 알고리즘의 시간복잡도는 $O(H^2W^2)$이다. 하지만 단순히 확인하는 시작점의 순서를 랜덤으로 섞어 주면, $i$번째 dfs에서 방문하는 정점의 수가 대략 $O(\frac{HW}{i})$개이기 때문에 시간복잡도가 $O(HWlogHW)$ 정도로 줄어든다. 랜덤을 쓰지 않고 SCC를 유니언 파인드 등으로 관리하는 풀이도 존재한다.
BOJ 17366 %
올바른 괄호 문자열에서 매칭되는 괄호 쌍을 정점으로 보면 트리 구조가 나타난다는 것을 알 수 있다. 이제 쿼리가 주어지면 트리에서 두 정점의 거리를 구하는 것과 유사하게 최단거리를 구할 수 있다. 각각의 위치에서 왼쪽 부모 괄호로 올라오는 최단거리와, 오른쪽 부모 괄호로 올라오는 최단거리를 구하는 것은 어렵지 않다. 조상까지의 거리를 빠르게 구하기 위해, 스파스 테이블을 구축하면 임의의 조상까지의 거리 정보를 $O(logN)$에 구할 수 있다. 이제 각각의 위치에서 구한 LCA까지의 거리 정보를 잘 합쳐 주면, 두 위치 사이의 최단거리를 구할 수 있다. 말로 하면 쉽지만 예외처리할 게 조금 있고, 구현도 쉬운 편은 아닌 것 같다. 총 시간복잡도는 $O((N+Q)logN)$이다.