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

[접기]

목차

  • 1. 활동 개요
  • 2. 토의 문제
  • 3. 풀이
    • 3.1. 중량제한
    • 3.2. Line Gimmick
    • 3.3. Buffalo Barricades


1. 활동 개요



2. 토의 문제



3. 풀이


3.1. 중량제한


문제 개요
N개의 정점, M개의 간선으로 이루어진 graph가 주어진다. 각 간선에는 중량 제한이 있으며, $c_i$를 초과하는 물품은 이 간선을 통해 이동하지 못한다. 이때, 어떤 두 정점 $s, t$가 주어질 때, $s \rightarrow t$로 배송할 수 있는 물건의 최대 중량을 구하라.

풀이
이 문제는 3가지 풀이가 존재한다.
  1. Binary Search
$T$의 무게를 가진 물건을 옮겨야 한다고 생각해보자. 이 때, 사용할 수 있는 간선은 $c_i \geq T$인 간선들이다. 이를 이용하여, $T$보다 큰 간선만 남기고 나머지 간선을 제거한 상황에서 $s \rightarrow t$로 갈 수 있는지 확인하면 된다. 시간복잡도는 $O(M\log{max(c_i)})$.
2. Dijkstra
일반적으로 Dijkstra 알고리즘은 어떤 두 정점사이의 최단거리를 찾는데 사용한다. 여기서, 각 정점에 거리를 갱신하는 방법을 바꾸어보자.
$d_i = (maximum\ number\ of\ weight\ can\ transport\ from\ s\ to\ i)$라고 정의하자. 정의에 맞게, $d_s = \infty$로 두자. 가장 처음 Priority에는 $s$정점만을 두고, PQ꺼낸 정점을 $u$라 할 때, 그 정점과 인접한 정점들을 다음과 같이 갱신해주자.
$$d_v = max(d_v, min(d_u, weight(u,v)),\ weight(u,v)는\ (u,v)간선의\ 중량제한$$
기존 shortest path를 찾는것과 비슷한 방법으로 각 $d_i$는 그 정점에 도달할 수 있는 최대 중량이라는 것을 보일 수 있다. 시간복잡도는 $O(M\log{M})$
3 Spanning Tree
중량의 역순으로, 즉 Maximum Spanning Tree를 구하며 $s, t$가 연결되는 첫 시점에서 사용한 간선의 중량이 $s \rightarrow t$로 수송할 수 있는 최대 중량이 된다. (이 또한 기존 MST 알고리즘처럼 증명이 가능하다.) 시간복잡도는 $O(M\log{M})$

3.2. Line Gimmick


문제 개요
'>', '<'로 이루어진 문자열이 주어진다. 플레이어는 각 칸을 밟을 때 다음과 같은 행동을 한다.
각 칸을 시작점으로 했을 때 지울수 있는 칸의 총 갯수는 달라질 수 있다. 이 때, 적당한 칸을 시작점으로 잡아 지울 수 있는 칸으 최대 갯수를 구하라.

풀이
$i$번째 칸은 시작점으로 잡아보자. 이때 $i$보다 작은 부분에서 '>'를 밟을 때, 그 칸보다 크고 $i$보다 작은 모든 칸이 지워져있어야 그 칸을 밟을 수 있기 때문에 $i$보다 큰 구간의 칸으로 이동하게 된다. 반면, '<'를 밟을 경우 왼쪽 구간에 계속 있는다. $i$보다 큰 부분에서도 비슷하게 이동을 한다. 따라서, 작은 구간에의 '>' 개수, 큰 구간에서의 '<'개수를 센 후 '>' 개수가 더 많다면 작은 구간에서 큰 구간의 '<' 개수만큼 '>'를 밟고 오른쪽 끝으로 빠져나간다. 오른쪽 구간이 클 때도 마찬가지로, 특정 개수만큼 밟다가 왼쪽 끝으로 나가게 된다.
이를 이용하여, 모든 시작점에 대해 '>', '<' 개수를 누적합과 같은 방법으로 구해준 뒤 위의 조건에 따라 빠져나가는 방향을 정하고, 밟는 칸의 개수를 세주면 된다.
각 구간에서 k번째 있는 '>','<'위치를 알아야 하므로, 시간복잡도는 $O(N\log{N})$이 걸릴 것이다.

3.3. Buffalo Barricades


문제 개요
나는 버팔로를 가두기 위해 바리게이트를 치고 싶다. 버팔로는 2차원상의 좌표 $(x,y)$에 놓여져 있다. 바리게이트를 칠 때, $(x,y)$에 바리게이트를 치게 된다면 $y$에서 음수방향으로 x축과 평행한 선분이 $x=0$이거나 다른 바리게이트에 부딪힐 때까지 그어지고, $x$에서 음수방향으로 y축과 평행한 선분이 $y=0$이거나 다른 바리게이트에 붇지힐 때까지 그어진다. 이때, 각 바리게이트를 짓는 연산마다 현제 그 바리게이트에만 속하는 버팔로의 개수를 모두 세어라.

풀이
모든 바리게이트가 완성된 후, $i$번 바리게이트에 속하는 버팔로의 수를 $c_i$라 하자. $c_i$만 출력하려고 보니 어떤 $i$번 바리게이트 내부에 속하는 $j$번 바리게이트가 이후에 지어졌기 때문에 $i$번 바리게이트를 지었을 때 속한 버팔로의 수는 $c_i +c_j$가 되는 경우가 발생한다. 이제 이를 처리해보자.
최종 상태에서 $i$번 바리게이트의 (x,y)를 포함하는 바리게이트의 번호를 $d_i$라 하자. ($d_i$는 각 바리게이트에 속한 버팔로의 수를 구하며 동시에 계산할 수 있다.) 이후, $d_i \rightarrow i$간선을 그리면 여러개의 트리로 이루어진 포레스트가 하나 주어질 것이다. 이후, 두 가지 풀이로 문제를 해결할 수 있다.
  1. DSU
$i$번 바리게이트에 속하는 버팔로의 수를 샐 때, $i$와 $i$번의 자손들 중 (이를 $j$라 하자.) $i$번 후에 만들어졌으며, $i \rightarrow j$의 path에 속하는 모든 정점이 $i$번 후에 지어진 바리게이트에 속한 $j$들의 개수를 구해주어야 한다. 이를 간단히 관리하기 위하여 초기에는 간선이 없는 포레스트를 만들고, 바리게이트가 지어지는 역순으로 각 바리게이트에 속하는 버팔로의 수를 계산하자. 그리고 각 바리게이트에 대한 연산이 끝난 후, 자신과 트리상에서의 부모 정점 사이에 간선을 추가해주자. 이 때 위의 조건을 만족하는 버팔로의 수는 현재 정점과 연결된 컴포넌트에 속하는 모든 버팔로의 개수와 동일하다. 이 개수를 DSU 자료구조를 이용하여 풀 수 있다. 이때 이 부분의 시간복잡도는 $O(M\log^*{M})$
2. Segment Tree
위 풀이에서, 리프에서 루트로 값을 갱신해주자. $i$번 정점의 값을 가장 처음으로 사용하는 정점은 $i$보다 늦게 지어진 바리게이트 중 $i$번과 가장 가까운 조상노드가 된다. 그 정점을 $j$라 할 때 단순히 $j$번째에 값을 갱신해주는 것만 해주면 된다. (윗 풀이에서, Union을 할 때 $i$번 노드가 속하는 컴포넌트의 subroot가 $j$가 된다.) 이 경우, 시간복잡도는 $O(M\log{M})$.
전처리 시간복잡도는 $O((N+M)\log{N+M})$이므로, 시간안에 통과시킬 수 있다.
(P. S. 1번 풀이가 시간도 더 빠르고, 코딩도 더 깔끔하다.)