suyeonme

이분매칭(Bipartite Matching)이란? 이분 그래프(Bipartite Graph)에서 그래프의 최대 유량을 구하는 알고리즘으로 최대 매칭 수를 구할 수 있다. 최대 매칭수란, 어떤 정점이 다른 정점을 점유한 상태이며 각 정점은 한 개씩 점유가 가능한 경우를 말한다. 따라서 간선의 용량이 1인 경우에 해당한다. 즉 간선의 용량(capacity)이 1인 네트워크 플로우 문제이며, DFS(Depth-first-search)로 구현할 수 있다. 시간복잡도는 [] 으로, 에드몬드카프 알고리즘보다 효율적이다. 이분 그래프(Bipartite Graph)란? 두개의 정점 그룹이 존재하고 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프이다. 아래 이미지를 보면, U와 V 두개의 정점 그룹이..

네트워크 플로우(Network-Flow) 알고리즘이란? A지점에서 B지점으로 데이터가 얼만큼 많이 흐르고 있는지를 측정하는 알고리즘으로 , 최대 유량 문제(Maximum flow problem)를 해결하는데 사용된다. 최대 유량 문제란, 네트워크상에서 얼마나 많은 양의 데이터를 보낼 수 있는지,즉 최대 유량(Max Flow)을 찾는 문제이다. 최대 유량 알고리즘은 유량을 보내는 순서가 상관이 없다. 용어 유량(flow): 현재 흐르는 데이터의 양 용량(capacity): 간선에 흐를 수 있는 최대 데이터의 양 일반적으로 BFS(Breadth-first search)를 이용하며, 에드몬드 카프(Edmonds-Karp) 알고리즘이라고도 한다. 시간복잡도는 O(VE^2)이다. 도로의 교통 흐름, 전자 회로의 ..

강한 연결 요소(Strongly Connected Component, SCC)란? 그래프안에서 강하게 결합된 정점 집합을 의미한다. 강한 결합 요소의 특징 같은 집합에 속하는 두 정점은 서로 도달이 가능하다. 사이클이 발생하는 경우 무조건 SCC에 해당한다. 따라서 방향그래프일 때 의미가 있다. 타잔 알고리즘(Tarjan's Algorithm)이란? 타잔 알고리즘(Tarjan's stronly connected components algorithm)은 SCC를 추출하는 대표적인 알고리즘으로 모든 정점에 대해 DFS를 수행하여 SCC를 탐색한다. 이 때 부모 노드로 돌아올 수 있는 경로에 한해서 SCC가 성립된다. SCC 그룹을 정점으로하여 전체 그래프를 구성한 경우, 사이클이 발생하지 않는 방향 그래프..

위상 정렬(Topology Sort)이란? 순서가 존재하는 작업을 수행할 때, 순서를 결정하기 위해 사용하는 알고리즘이다. 위상 정렬은 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)에만 적용할 수 있으며 여러개의 결과가 존재할 수 있다. 방향성이 있지만 사이클이 없어야 진입차수가 존재할 수 있다. 진입차수(in-degree), 진출 차수(out-degree)란? 진입차수(in-degree): A노드를 향하는(A노드로 들어오는) 간선의 개수 진출 차수(out-degree): A노드에서 외부로 향하는(나가는) 간선의 개수 노드 2의 경우, 진입차수는 2, 진출차수는 0이다. 구현 방법 Stack Queue 구현 순서 진입차수가 0인 정점을 큐에 삽입한다. 큐에서 노..

플로이드 와샬 알고리즘(Floyd Warshall Algorithm)이란? 음수 사이클이 없는 그래프에서 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘으로, 거쳐가는(경유) 정점을 기준으로 거쳐가는 경로가 기존의 경로보다 더 효율적인지 판단하여 최단 거리를 구한다. 정점의 개수만큼 3중 반복문을 수행하기때문에 O(V^3)만큼의 시간 복잡도를 갖는다. 동적 프로그래밍 기법을 사용한다. 음수 사이클이 존재하지 않으면 음의 가중치를 가질 수 있다. (≠ 다익스트라 알고리즘) 음수 사이클 사이클의 모든 경로의 합이 음수가 되는 사이클이다. 1 --> 2 --> 3 --> 1의 경우, (1 -3 -2) = -4 이므로 음수 사이클이 존재한다. 구현 순서 인접 행렬을 생성하고 간선의 정보를 저장한다..

다익스트라 알고리즘(Dijkstra Algorithm)이란? 그리디 알고리즘/다이나믹 프로그래밍을 이용한 대표적인 그래프의 최단 경로(Shortest Path)를 구하는 알고리즘이다. 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다. 다익스트라 알고리즘은 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리 정보를 그대로 사용한다. 최단 거리는 여러개의 최단거리로 이루어져있다고 볼 수 있다. 따라서 다익스트라 알고리즘은 다이나믹 프로그래밍 기법을 사용한다. * 인공 위성 GPS에 가장 많이 사용된다. 그래프의 최단 경로를 구하는 알고리즘 비교 알고리즘 특징 BFS 간선의 가중치가 모두 같은 그래프의 경우 다익스트라 알고리즘(Dijkstra A..

크루스칼 알고리즘(Kruskal Algorithm)이란? 최소 비용으로 모든 노드를 연결하기 위해서 사용하는 알고리즘으로 대표적인 최소 신장 트리(MST, Minimum Spanning Tree)를 만드는 대표적인 알고리즘이다. 가장 적은 비용(weight)을 탐욕적(Greedy Algorithm)으로 확인하여 가장 적은 비용으로 사이클이 발생하지 않게 모든 노드를 연결한다. 시간복잡도는 O(E log E)이다. 간선을 가중치순으로 정렬하므로 E log E만큼의 시간이 소요된다. (=퀵정렬의 시간 복잡도) 반복문에서 V-1만큼의 시간이 소요된다. 최소 신장 트리(MST, Minimum Spanning Tree)란? 신장 트리(Spanning Tree): 그래프의 모든 정점을 연결하고 사이클이 없는 그래프..

합집합 찾기(Union Find) 알고리즘이란? 대표적인 그래프 알고리즘으로, 여러개의 노드가 존재하는 경우 두 개의 노드를 선택하여 선택된 노드가 서로 같은 그래프에 속하는지 확인하는 알고리즘이다. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리운다. 크루스칼 알고리즘(Kruskal Algorithm)등 고급 그래프 알고리즘에 사용된다. 사이클(Cycle)이 있는지 확인하는 문제 구현 방법 노드의 부모가 자기 자신이 되도록 초기화한다. 두개의 노드를 연결한다. 이 때 더 작은 노드가 부모가 되도록 합친다. -- unionFind 재귀를 사용하여 두개의 노드가 같은 그래프에 속해있는지 확인한다. -- findParent 알고리즘 구현 // 부모노드를 찾는다. const getParent = (..