IT/알고리즘 및 자료구조13 [알고리즘 정리]네트워크 플로우(Network Flow) 알고리즘_에드몬드 카프 알고리즘(Edmonds-Karp algorithm) 네트워크 플로우 코드적으로 이해하는것이 조금 어려울 수 있지만, 개념자체는 간단하게 "도착지(Sink)에 얼마나 물이 나오게 할 수 있느냐?"에 관한 문제입니다. 그림을 보면 쉽게 이해 할 수 있다. 위의 문제에서 각 Source와 각 수도관은 주어진 리터만큼 시간당 물을 보낼 수 있고 하였을때, Sink에는 시간당 얼만큼의 물이 도달 할 수있냐? 딱, 봐도 8L의 물이 도달 할 수 있다는 것을 알 수 있다. 이 문제를 해결 하는 것이 네트워크 플로우다. 용어 정리 & 주요 특징 - (용어 1) Source : 네트위크(물)의 시작점 - (용어 2) Sink: 네트워크(물)의 도착지점 - (용어 3) c(a,b) : a->b로 흐를 수 있는 물의 최대량(용량) - (용어 4) f(a,b) : a->b로 .. 2018. 10. 3. [알고리즘 정리] 위상 정렬 위상 정렬 시간 복잡도 : O(|V|+|E|) indegree : 한 정점에 들어오는 간선 수ex ) a -> c, b -> c 라면 c의 indegree는 2, a,b의 indegree는 0이 된다. 기본 코드 // 해당 노드에 향하는 간선(indegree)이 0인경우 q에 추가한다. for (int i = 1; i 2018. 9. 30. [알고리즘 정리] 이분 매칭 이분 매칭 시간 복잡도 : O(E*sqrt(V)) visit : 방문 여부 확인bs : 현재 노드가 연결된 노드 ex) bs[a]=b; 라면, a와 b가 연결된 상태이다. 기본 코드 bool dfs(int cur) { if (visite[cur]) return 0; visite[cur] = 1; for (int i = 0; i < node[cur].size(); i++) { int next = node[cur][i]; if (!bs[next] || dfs(bs[next])) { bs[next] = cur; return 1; } } return 0; } int binary_match() { int ret = 0; for (int i = 1; i 2018. 9. 30. [알고리즘 정리] 세그먼트 트리 세그먼트 트리 update 시간 복잡도 : Log(N)query 시간 복잡도 : Log(N) c : 현재 노드l, r : 현재 노드의 값의 범위s, f : 찾으려는 값의 범위val : update 되는 값 기본 코드 ll update(ll c, ll l, ll r ,ll f,ll val) { if(!(l 2018. 9. 17. 이전 1 2 3 4 다음
