목록알고리즘/이론 (11)
jjj
이분 매칭 두 그룹 A와 B는 서로 연결될 수 있는 두 그래프이다. 이러한 이분 그래프에서 최대 매칭을 찾는 문제를 간단하게 이분 매칭이라고 한다. // A 와 B의 정점의 개수 int n, m; bool adj[MAX_N][MAX_M]; vector aMatch, bMatch; vector visited; int dfs(int a) { if (visited[a]) return false; visited[a] = true; for (int b = 0; b < m; b++) { if (adj[a][b]) { // 만약 b가 매칭되지 않았을때 // or 매칭이 되었을 경우 b와 매칭된 A그룹의 정점이 // 다른 B 그룹의 정점과 연결이 가능한지 파악 // 가능하다면 그 점과 연결한 후 a 와 b 매칭 if ..
포드 풀커슨 알고리즘은 네트워크 유량을 구하기 위한 문제이다. 특정 시작점에서 특정 끝점까지 한번에 보낼 수 최대 유량값을 찾는 문제이다. 구현 방법 bfs를 이용하여 시작점에서 끝점까지 탐색 ( 그 과정에서 자신으로 들어오는 부모 정점 저장 ) 끝점부터 시작하여 해당 경로를 통해 옮길 수 있는 유량을 확인 ( 경로 중 가장 작은 값) 찾은 유량 값을 갱신 ( 반대 방향은 음수로 갱신) 이 것을 끝점에 닿는 증가경로가 없을 때까지 반복 const int INF = 99999999; int V; // capacity[u][v] : u에서 v로 보낼 수 있는 용량 // flow[u][v] : u에서 v로 보낸 유량 ( 반대 방향일 경우 음수 ) int capacity[MAX_V][MAX_V]; int flo..
크루스칼 알고리즘은 프림 알고리즘과 함께 최소 스패닝 트리를 찾는 알고리즘이다. 스패닝 트리는 모든 정점에 대해 사이클이 없는 그래프이다. 즉 트리 형태이지만 부모- 자식의 형태로 이어질 필요는 없다. 크루스칼 알고리즘은 간선을 정렬한 후 사이클이 존재하지 않게 순서대로 간선을 붙이는 방식으로 구현된다. 사이클이 존재하지 않기 위해서는 두 정점이 같은 컴포넌트로 속해져 있지 않으면 되고, 같은 컴포넌트에 에 속하지 않는 것을 확인하기 위해 상호배타적 조합 ( 유니온 파인드라고 많이 부른다)을 사용한다. #include #include using namespace std; struct DisjointSet { vector parent, rank; DisjointSet(int n) { parent = vec..
플로이드 워셜은 모든 점에서 다른 모든 점까지의 최소 거리를 구하는 알고리즘이다. k라는 정점을 정해놓고 모든 점이 그 점을 경유했을 때 다른 모든 점까지의 최소값을 갱신하면서 모든 점 사이의 최소값을 구하는 방법이다. k를 모든 정점에 대해서 수행한다. 만약 i 정점에서 k까지 이어져 있지 않다면 j for문을 뛰어넘어도 상관이 없을 것이다. const int MAX_V = 1000; // 정점의 개수 int V; // 간선이 없으면 아주 큰 값을 넣는다. int adj[MAX_V][MAX_V]; void floyd() { for (int i = 0; i < V; i++) { adj[i][i] = 0; } for (int k = 0; k < V; k++) { for (int i = 0; i < V; i..
상호 배타적 조합 각각의 점들에 대해 자신이 속한 그룹을 확인할 수 있다. find 과정에서 찾으면서 갱신하기 때문에 find는 빠른시간내에 자신의 그룹 번호를 찾을 수 있다. 그룹 번호는 루트의 번호로 사용한다. #include using namespace std; struct DisjointSet { vector parent, rank; DisjointSet(int n) { parent = vector(n); rank = vector(n, 1); for (int i = 0; i < n; i++) { parent[i] = i; } } int find(int u) { if (u == parent[u]) { return u; } return parent[u] = find(parent[u]); } void ..
방향그래프에서 임의의 두정점에 대해 양 방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 있다고 한다. SCC를 구하는 방법은 크게 2개가 있다. 1.코사라주 알고리즘 2.Tarjan 알고리즘 일단 타잔알고리즘으로 구현하였다. 타잔 알고리즘 타잔 알고리즘은 dfs 한번으로 구현할 수 있다. dfs를 타고 내려가면서 해당 정점을 발견한 순서를 저장한다. 그리고 각각 자신이 갈 수 있는 가장 높은 정점 ( 순서가 가장 빠른 정점 ) 을 반환한다. 그 과정에서 만약 자손들이 갈 수 있는 정점들 중 가장 작은 번호가 자신이라면 그 정점이 루트가 되므로 해당 정점의 자식들로 이루어진 scc를 만든다. ( 정점에 들어갈 때마다 스택에 쌓는데 해당 정점 이후에 들어간 정점들은 모두 그 정점의 자식들이다. ..
먼저 시작점 후보가 되는 정점으로 부터 dfs를 시작하여 간선을 지날 때마다 해당 간선을 삭제한다. 그리고 dfs가 종료된 정점들을 저장한다. 저장된 값의 크기 + 1 이 간선의 개수와 같을 때 해당 값들의 역순이 오일러 회로가 된다. 오일러 회로 방향이 없는 그래프라면 각 정점의 개수가 짝수여야 한다. 하지만 방향이 있는 그래프라면 각 정점마다 나가는 개수와 들어오는 개수가 같아야 한다. 오일러 경로 오일러 경로도 마찬가지로 각 정점마다 나가는 개수와 들어오는 개수가 같아야 한다. 그리고 오일러 경로는 나가는 간선이 하나 많은 시작점 한개와 들어오는 간선이 하나 많은 끝점 한개가 있어야 한다. // 오일러 경로, 회로 모두 파악 가능 bool checkEuler(){ int start = 0; int ..