NEMOSTAR5

이분 매칭은 네트워크 플로우 알고리즘과 연계되는 개념이다. 이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘이다. '사람'이라는 집단과 '노트북'이라는 두개의 집단이 등장합니다. 효과적으로 매칭시켜준다는 말은 다시 말해 '최대 매칭(Max matching)'을 의미하는 것입니다. 모든 사람 각각이 노트북을 선택하여 가장 많이 연결되는 경우를 찾는 문제라고 볼 수 있습니다. 그림을 한번 다음과 같이 플로우로 표현해보도록 합시다. 네크워크 플로우와 정확히 일치하게 됩니다. 위와 같이 이분 매칭 알고리즘은 네트워크 플로우로 표현할수 있습니다. 각 용량(Capactiy)를 1로 설정한 네트워크 플로우 문제를 이해할 수 있는 것입니다. 다만 우리가 이전에 공부했던 에드몬드 카프 알고리즘은 시간 복잡..

네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다. 이러한 알고리즘은 교통 체증, 네트워크 데이터 전송 등의 다양한 분야에 활용되고 있다. 표현 방식은 유량(Flow)/용량(Capacity)이다. 즉 1에서 2로 가는길은 12명이 갈 수 있는 용량에 실제로는 0명이 가게 되었다는 소리이다. 이제 간단하게 하나의 간선으로 용량과 용량을 표현해보면, 위와 같이 A에서 B로 갈 수 있는 용량은 8, B에서 C로 갈수 있는 용량은 6, C에서 D로 갈 수 있는 용량은 7이라고 해보자. 이때 A에서 D로 최대한 많은 용량을 보내려고 할 때 가장 합리적인 양은 얼마일까? 바로 6이다. 바로 이러한 문제를 해결하는 핵심 알고리즘이 네트워크 플로우 알고리즘이다...

강한 결합 요소란 그래프 안에서 '강하게 결합된 정점 집합'을 의미한다. 서로 긴밀하게 연결되어 있다고 하여 강한 결합 요소라고 말한다. SCC는 '같은 SCC에 속하는 두 정점은 서로 도달이 가능하다'라는 특징이 있다. 총 4개의 집합이 존재하는데 각 집합에 있는 정점끼리는 서로에게 도달할 수 있는 것을 알 수 있다. 사이클이 발생하는 경우 무조건 SCC에 해당한다는 특징이 있다. 그래서 위와 같이 방향 그래프일 때만 의미가 있다. 무향 그래프라면 그 그래프 전체는 무조건 SCC이기 때문이다. SCC를 추출하는 대표적인 알고리즘은 코사라주 알고리즘(Kosaraju's Algorithm)과 타잔 알고리즘(Tarjan's Algorithm)이 있다. 일반적으로 코사라주 알고리즘이 더 구현이 쉽지만 타잔 알..

위상 정렬은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 순서가 정해져있는 작업의 대표적인 예시는 다음과 같다. 그래프의 흐름은 사실 '조건'으로 해석할 수 있다. 위와 같이 여러개의 순서가 정해져있을 때 조건에 부합하는 일직선의 순서를 찾아보자. 위상 정렬 : 1 -> 5 -> 2 -> 3-> 4 -> 6-> 7 위와 같이 정렬을 하면 순서대로 작업을 수행했을 때 성공적으로 '7'까지 갈 수 있다. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 이것은 사이클이 발생하지 않는 방향 그래프라는 의미이다. 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. 위상정렬 알고리즘은 두가지 해결책을 낸다는 특징이 ..