unordered_map이 PS하는 블로그

https://justicehui.github.io/hard-algorithm/2020/01/24/hld/ : 이 글이 이론의 전반적인 이해에 큰 도움이 되었다. GOAT. 오일러 투어 테크닉, LCA 등의 쉬운 트리 이론은 트리 문제 하나로 전부 정리된다고 생각한다. 해당 문제를 풀 수 있으면 심화 트리 이론을 공부할 수 있는 것이고, 해당 문제를 풀 수 없다면 기초부터 다시 다지고 올라와야한다. 여기서 쉬운 트리 이론과 심화 트리 이론을 당당하게 나누어 말할 수 있는 이유는 난이도 차이가 실제로 매우 크기 때문이다. 심화 트리 이론의 첫 단계라고도 말할 수 있는 HLD는 쉬운 트리 이론은 물론이거니와 세그먼트 트리까지 완벽하게 장착하고 있어야 이해할 수 있는 이론이다. 반대로 말하면, 쉬운 트리 이론..

최대 유량 문제 (Maximum Flow) 최대 유량 문제(Maximum Flow)란 방향 그래프에서 각 간선의 용량이 정해져 있을 때, 정해진 출발점에서 도착점까지 보낼 수 있는 최대의 유량을 계산하는 문제를 말한다. 위와 같이 생긴 방향 그래프의 1번 정점에서 7번 정점까지의 최대 유량인 상황은 아래 그림과 같다. 간선에 적힌 a/b는 용량이 b인 간선에 현재 a의 유량이 흐르고 있다는 것을 말한다. 이 경우의 유량은 11이다. 더 이상의 유량이 없다는 것은 어떻게 알 수 있을까? 최소 1의 유량이 흐를 수 있는 출발점에서 도착점까지 가는 경로를 증가경로(Augmented Path)라고 한다. 위 그래프에서 증가경로는 없다는 사실을 눈으로도 쉽게 확인할 수 있으며, 임의의 그래프에 대해서도 DFS/B..

단절선 [BOJ 11400] (P5 & Class 6) https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 단절선이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 간선을 제거했을 때 두 개 이상의 컴포넌트로 나누어지는 간선 DFS Spanning Tree 단절점을 구하는 알고리즘과 상당히 비슷하다. DFS Spanning Tree에 대한 기본적인 내용은 단절점 글을 참고! https://unorderedmap.ti..

단절점 [BOJ 11266] (P5 & Class 6) https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 단절점이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나누어지는 정점 위 그래프에서 빨간색 정점이 1, 6, 7이 단절점이다. 1, 6, 7 중 하나를 없애면 그래프가 2개 이상의 덩어리로 분리되기 때문이다. DFS Spanning Tree 한 그래프에서 특정 정..