/* 이분 매칭은 네트워크 플로우 알고리즘과 연계되는 개념. A 집단이 B 집단을 선택하는 방법에 대한 알고리즘. 효과적으로 매칭시키다라는 말은 최대매칭을 의미. 이분 매칭 알고리즘은 각 용량을 1로 설정한 네트워크 플로우문제로 표현 가능. 네트워크 플로우 에드몬드 카프 알고리즘은 시간복잡도가 O(V * E^2). 하지만 이분 매칭에 한해 더 빠르고 효율적으로 알고리즘 설계 가능. DFS 사용. 이분 매칭을 간단히 풀 때의 시간 복잡도는 O(V * E). */ #include #include #define MAX 101 //정점의 갯수 using namespace std; vector a[MAX]; int d[MAX]; //특정한 정점을 점유하고 있는 노드의 정보를 담는 배열. bool c[MAX]; /..

/* 네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘. 일반적으로 최대 유량(Max Flow) 문제라고 정의함. 최대 유량 문제는 각 간선에 정해진 용량이 있을 때, A 에서 B로 최대로 보낼 수 있는 유량의 크기를 구하는 문제. 기본적으로 최대 유량 문제는 단순하게 가능한 모든 경우의 수를 탐색하는데, 이 때 BFS(너비 우선 탐색)을 일반적으로 이용. 이것을 에드몬드 카프(Edmonds-Karp) 알고리즘이라 함. 최대 유량 알고리즘은 순서가 상관 없음. 남아있는 양이 1이 넘으면 계속해서 흘려 보내주면 알아서 최적화. 기본적으로 BFS를 사용하여 모든 가능한 경로를 다 찾아서 남아있는 용량만큼 유량을 흘려 보내주는 것을 반복. 음의 유량도 함께..

/* 유향 그래프에서 모든 정점이 모든 다른정점에 대해 도달 가능한 경우, 강하게 연결 되었다라고 함. 강한 결합 요소는 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향그래프의 분할임. 그래프가 강하게 연결되었는지, 그래프에서 강한 연결 요소를 찾는 것은 선형시간에 가능. SCC 알고리즘이라 불림. SCC는 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다는 특징이 있음. 사이클이 발생하는 경우 무조건 SCC. SCC를 추출하는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 있음. 구현은 코사라주가 쉽고 적용은 타잔이 쉬움. 타잔 알고리즘은 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘. 부모에서 자식으로 나아가는 알고리즘으로 DFS알고리즘이 사용됨. SCC 자체로는 큰 의미가 없..

/* 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 그 순서를 결정해 주기 위해 사용하는 알고리즘. 위상 정렬 알고리즘은 두가지 답을 알 수 있음. 현재 그래프가 위상 정렬이 가능한 그래프인지 , 가능하다면 결과는 무엇인지. 예시) 대학생 되기 >> 학과 사이트 가입하기 >> 4학년 되기 >> 정보처리기사 합격하기 >> 자격 서류 제출하기 >> 졸업시험 신청하기 >> 졸업 위상 정렬은 여러 개의 답이 존재할 수 있다는 점에서 매력적. 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용 가능. 즉, 사이클이 없는 방향 그래프. 위상 정렬은 스택, 큐 모두 이용가능. 1. 진입차수가 0인 정점을 큐에 삽입. 2. 큐에서 원소를 꺼내 연결된 모든 간선 제거. 3. 간선 제거 이후 진입..

/* 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 쓰임. 가장 적은 비용을 하나씩 선택해야 했던 다익스트라 알고리즘과는 다르게 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행. 플로이드 와샬 알고리즘 또한 다이나믹 프로그래밍 기술에 의거. */ #include using namespace std; const int number = 4; int INF = 10000000; //자료 배열 초기화. int a[4][4] = { {0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0} }; void floydWarshall() { //결과 그래프 초기화. int d[number][number]; for (int i =..

/* 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 음의 간선은 포함할 수 없음. 다이나믹 프로그래밍을 이용하는 이유는 최단거리는 여러 개의 최단 거리로 이루어져 있기 때문. 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용.(갱신함) */ /* 1. 출발 노드 설정. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신. 5. 3 ~ 4 반복. */ ////선형 탐색으로 구현했을 때. 가장 간단히 구현할 수 있으나, 노드갯수에 비해 ////간선..