이전에는 다항식을 예고했었지만, 다항식에 대해 글을 작성하기에는 아직 정보가 부족하다고 판단되어 그냥 적당히 작성해볼만하고, 알아두면 좋을 것 같지만 그렇게 많이 알려져있다고 생각되지는 않는 그래프 이론의 아이디어들을 들고 왔다.
1. dial's algorithm
일반적인 무향 그래프의 한 점에서 다른 점들로의 최단경로를 검색하는 것은 다익스트라 알고리즘을 통해 수행할 수 있다는 사실이 잘 알려져있다. 그러나, 다익같은 경우에는 로그가 하나 붙기 때문에, 비정상적으로 정점이나 간선이 많은 경우에 대해서는 적용하기 힘들다. 하지만 만약 특수하게 각 간선들에 대한 가중치가 작다면, dial's algorithm을 사용하면 O(NK+M)만에 이를 수행할 수 있다는 것이 알려져있다. 이때, N은 정점개수, M은 간선개수, K는 각 간선들의 가중치의 최댓값이다.
구체적으로, 해당 알고리즘은 총 K+1개의 queue를 관리하게 되는데, 각 queue의 인덱스는 어떤 정점의 최단경로의 거리에 대한 정보를 들고 있게 된다. 초기에는 0번 정점을 queue[0]에 삽입한다. 그 뒤, 모든 queue 내부의 원소가 사라질때까지 queue들을 순서대로 순회하며, k+1번째 queue를 순회해야 한다면 0번으로 돌아온다.
queue[x]를 탐색중이라 하고 그 내부의 정점v에 대해서, 더 효과적인 방법이 있고 수행하지 않은 다른 인접한 정점에 대해, queue[(d[v]+edge)%(k+1)]번째 queue에 인접한 정점을 집어넣는다. 왜 queue가 정확히 k+1개 필요한가? 우리가 현재 보고 있는 queue에서부터 아무리 멀리 뻗어나가봐야 k만큼 더 나아갈 수 있기 때문에, 한 queue 내부에 있는 정점들은 항상 동일한 최단거리를 가지게 된다. 즉, 그 다음 queue들을 침범하지 않기 때문에 이런 아이디어를 적용 가능한 것이다.
해당 논리는 사실 다익스트라와 동일하지만, 다익스트라에서 현재 가장 짧은 최단경로를 가지는 원소를 검색하는 시간이 O(1)이기 때문에 더욱 빠를 수 있는 것이다.
음...사실 해당 아이디어를 적용하는 문제가 존재하는지는 잘 모르겠다. 걍 나중에 문제를 뚫을 때에 요긴하게 쓸 수 있을지도 모른다.
2. O(1) LCA
그냥 간단하게 말하겠다. 어차피 LCA는 잘 알려진 구조이며, 이걸 O(1) 안에 구한다는 것이 무엇을 의미하는지 굳이 말하지 않아도 알 것이다.
일단 오일러 투어 테크닉을 적용한다. 답은 어떤 두 정점에 대해서, ETT로 펼친 배열 상에서 가장 깊이가 작은 정점이라는 관찰을 할 수 있다. 따라서 RMQ를 O(1) 안에 처리할 수 있으면 충분한데, 갱신이 없는 경우의 RMQ는 sparse table등을 통한 O(nlogn)의 전처리를 통해 O(1) 내에 처리할 수 있다는 사실을 알 수 있다.
뭐 솔직히 LCA를 O(1) 내에 구해야 하는 상황이 얼마나 될진 잘 모르겠으나...그래도 꽤 유용한 아이디어같다.
3. Pie for a Pie trick
해당 아이디어는 15457번: A Pie for a Pie (acmicpc.net)에서부터 그 이름이 유래했다는 것 같다.
15457번: A Pie for a Pie
There should be $N$ lines in the output. Line $i$ should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie's pie $i$. If no gift exchange starting with pie $i$ is happy, then line $i$ sho
www.acmicpc.net
근데 아직 문제를 안읽어봐서 그냥 내가 본 문제 기준으로 설명하겠다.
Problem - 1242B - Codeforces
codeforces.com
해당 문제를 간략히 요약하자면, 완전 그래프가 주어지고 간선에 가중치가 있으며, 그 가중치가 0 혹은 1이고, 가중치가 1인 간선이 많아야 10^5개인 상황에서 스패닝 트리의 비용을 찾는 것이다. 일단 몇가지 관찰을 통해, 해당 문제를 가중치가 0인 간선들로 이루어지는 컴포넌트의 개수를 구하는 문제로 바꿀 수 있다.
이러한 것은 bfs같은 것을 통해 할 수 있기야 하지만, 그 경우 시간복잡도는 간선의 개수에 지배당하여 상당히 비효율적이게 된다. 이 비효율성의 원인은 더 방문할 필요가 없는 정점에 방문해야 하는지의 여부를 체크하기 때문인데, 즉 이런 부분만 적당히 해결하면 문제가 해결될것이라고 생각할 수 있다. 이 경우에 생각해볼 수 있는 것은, 아직 방문하지 않은 정점들을 셋에다가 집어넣고, 어떤 정점에서 탐색을 할 때 그 셋 내부에 있는 원소들 기준으로 탐색하는 것이다. 이경우에도 효율성이 개선되지 않은게 아닌지 의문이 들 수도 있지만, 사실 잘 생각해보면 셋 내부에 있는 원소로 접근할 수 없는 시점에서, 그 두 정점 사이에 간선이 존재하지 않는다는 결론이 도출된다. 그런데 잘 생각해보면, 간선이 없는 두 정점의 쌍의 개수가 10^5정도로 bound되어있다. 따라서, bfs를 하던 도중 셋 내부의 원소와 인접하지 않는 횟수는 많아야 O(m)이다(m: 가중치 1 간선의 개수). 따라서 문제를 대충 10만로그정도 되는 스케일에 해결할 수 있다는 사실을 알 수 있다.
pie for the pie? 문제에 대해서는 직접 보고 한번 짜봐야 할 것 같다.
추신)pie for the pie 문제의 풀이를 보고 알았다. 이거 그냥 굳이 인버스 그래프에 대해 다룬다기보단 엄청나게 간선이 많은 그래프 내에서 범용적으로 쓸 수 있는 아이디어같다. 즉, 아직 탐색하지 않은 정점을 방문하는 것을 효과적으로 처리하는...그런 트릭이라고 할 수 있다. 비슷한 아이디어를 대충 구간그래프가지고 scc하는거에서 본 적 있는 것 같은데 어떤 문제였는진 기억이 안난다. 그냥 생각보다 트릭이라는 이름이 붙기도 애매한 정도의 생각해볼법한 아이디어지만, 만약 몰랐다가 알게 되었다면 굉장히 유용할 것이라 생각된다.
4. incremental SCC
정말, 겨우 이해했다. Offline Incremental SCC (tistory.com)를 50번정도 읽고 코드 작동까지 완벽히 분석해서 겨우 이해한 것 같다.
Offline Incremental SCC
이번에도 역시 소멤에 투고한 글. ----------------------------------------------------------------------------------------------- 본 글에서는 간선이 하나씩 추가됨에 따라 SCC를 관리하는 Incremental SCC를 오프라인으로
cheet0se.tistory.com
나의 이해속도가 너무 느린 것일수도 있지만, 그래도 다른 이해 못하는 사람이 존재할 수도 있기 때문에 이 아이디어에 대한 더욱 구체적인 절차를 설명하겠다. 기본적 아이디어는 위의 글에 존재하기 때문에 이것을 먼저 읽어야 할 것이다.
위의 글에도 나와있듯이, 아이디어의 핵심은 분할정복을 하는 것이다. 분할정복을 통해서 해결하는 것은 정확히 다음과 같다: "u->v로 가는 간선이 등장했으며, u와 v가 scc 상에서 동일한 컴포넌트에 존재하는 최초의 시점은 몇번째 간선이 추가되는 때인가?"
사실 나는 왜 해당 문제를 푸는지가 문제를 해결하는 역할을 하는지(즉, 위의 조건들만으로 유니온 파인드를 하며 정점들을 관리하는 것이 scc를 관리하는 것과 동치라는 사실)가 자명하지 않았다. 이에 대해서, 나는 임의의 순간에 대해서도 두 경우가 동일하다는 사실에 대한 나름의 증명?직관?을 설명하겠다.
만약 어떤 순간에 두 정점이 같은 컴포넌트 상에 존재하지 않는다고 하자. 그 경우에 두 정점이 유니온 파인드를 통해 합쳐지지 않았음은 자명한데, 왜냐하면 둘이 유파를 통해 합쳐졌다면 분명히 어떤 간선들을 통해, 다른 정점들과 동일한 scc 관계로 묶였을 것이기 때문이다.
만약 어떤 순간에 두 정점이 같은 컴포넌트 상에 존재한다면? 그렇다면 두 정점을 포함하는 적절한 사이클이 존재한다는 사실을 유도 가능하다. 또한, 그 사이클의 모든 간선들은 이미 "존재"하며, 또한 그 시점에서 scc가 형성되었기 때문에 그 모든 간선들은 그 순간 이전까지 전부 추가되었거나, 혹은 지금 추가되게 된다. 따라서 적절한 정점들의 나열을 통해 유파적으로 동일한 컴포넌트 상에 위치하게 된다.
따라서 위의 조건만 분할정복을 통해 확인하면 된다는 것이다. 그렇다면 분할정복은 어떻게 작동되는가? 내 생각에, 핵심은 scc를 총 "두개의 부분"으로 나누어서 계산하는 것이라 생각한다. 어떤 구간에 대해 문제를 푼다는 것은, 그 이전의 모든 리프들을 방문했다는 것과 동일하다. 각 리프들을 방문할 때마다, 실제 scc를 유파를 통해서 미리 합쳐두었다는 사실을 알 수 있다. 따라서 우리는 단순히 현재 구간의 [L,M)에 존재하는 간선들만 추가해도 충분하다는 사실을 알 수 있다. 시간복잡도에 대해 설명하자면, 한 번의 분할정복 스텝에서 걸리는 시간복잡도는 총 O(구간 내 간선의 개수)정도이다. 단지 그 간선들만을 유파를 통해 이미 병합된, "간선이 없는" 고립점들로 이루어진 그래프에 추가하고(왜냐하면 그 이전에 사용된 모든 간선들은 전부 어떤 두 정점이 scc를 이루도록 하기 위해 사용되었기 때문이다. 만약 초기그래프에 간선이 몇개 더 있었다면 어떨지 궁금할수도 있지만, 사실 첫 입력에서 주어진 모든 초기간선들도 간선을 추가하는 쿼리로 간주하면 그런 문제를 겪지 않아도 된다.), 그에 대한 scc를 찾아낼 것인데, 이 경우 우리가 봐야할 정점은 O(M)일...것이기 때문이다. 한 간선은 분할정복의 전체 과정에서 로그번 등장하므로, 총 시간복잡도는 아주 대략적으로 O(MlogM)정도가 된다.
아직 짜보진 않아서 짜봐야한다. 연습문제(가 루4다ㄷㄷ...)는 다음이 있다.
8496번: Godzilla
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i m (1 ≤ n, m ≤ 100,000), oznaczające liczbę węzłów i połączeń w sieci kablowej. W kolejnych m wierszach znajdują się opisy połączeń. Każdy z wierszy zawiera dwie licz
www.acmicpc.net
19028번: Link Cut Digraph (acmicpc.net)
19028번: Link Cut Digraph
After reading the paper Incremental Topological Ordering and Strong Component Maintenance, you came up with the following problem. You are given a graph with $n$ vertices. There are no edges initially. There are $m$ operations. Each operation is first to a
www.acmicpc.net
링컷 다이그래프는 이제 짜봤는데 음...대충 어떤 느낌인지 알 것 같다. 일단 짜면서 코사라주 알고리즘 하나는 확실하게 외운 것 같다.
5. 후기
incremental scc라고 해서 엄청나게 마니악한 아이디어나 개념을 도입할 줄 알았는데, 의외로 할만한? 아이디어를 썼던게 인상적이었고, 그 아이디어의 사용방식이 무언가 유명한 다른 문제들(폴란드의 유명한 그 문제라거나)과 비슷하고 응용가능성이 꽤 있는 것 같아 인상적이었다. 그리고 LCA를 O(1) 안에 구하는 것이 솔직히 가능할줄 몰랐는데, 가능하다는 사실을 배웠고, 음...다이얼 알고리즘은 그냥 그런게 있구나...하고 생각하게 되었다. 솔직히 어디에 써야할지 모르겠다. 그리고 PiePie trick은 이전에 비슷한 문제를 세그를 통해 풀어야 하나 하고 접근했던 것 같은데, 그냥 셋으로도 해결이 된다는 사실을 알게 되어 inverse graph에 대한 직관이 늘어난 것 같다. 저 문제도 꼭 풀어봐야지
아마 다음 주제는 아주 "웰노운"인 자구들에 대해 다루게 될 것 같다. 사실 방금 어떤걸 쓸지 구경하다가 다이나믹 아호코라식이라는걸 발견했는데 그런게 된다니 굉장히 놀랍다. 하지만 다음시간은 변함없이 자구다.
