이분 매칭 알고리즘 (Bipartite Matching) 두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프(Bipartite Graph)라고 말합니다. 이러한 이분 그래프에서 예를 들어, 한쪽 그룹은 X 그룹, 다른 한쪽 그룹은 Y 그룹이라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것이 이분 매칭(Bipartite Matching)입니다. 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 매칭을 한다는 것은 어떤 정점이 그것이 가리키는 위치의 다른 정점을 점유한 상태를 말하며 각 정점은 한 개씩만 점유 가능하고 여러개의 정점을 점유할 수 없습니다. 간선의 용량이 1인 것은 바로 이러한 이유에서..

DFS 알고리즘 (Depth First Search) 깊이 우선 탐색(DFS)은 BFS와 달리 스택 자료구조를 사용하여 깊이를 우선적으로 탐색하는 알고리즘입니다. 또한 재귀적 함수로도 구현이 가능합니다. 위와 같은 이진 트리에 대하여 깊이 우선 탐색을 해보겠습니다. 깊이 우선 탐색은 기본적으로 노드를 스택에 넣고 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문이 완료되었으면 다시 방문하지 않은 노드를 찾아서 스택에 넣는 방식입니다. 가장 먼저 방문하는 노드 1을 스택에 넣고 방문 완료(visited)합니다. 스택은 큐와 달리 나중에 들어온 것이 먼저 나가는 후입선출 방식입니다. 인접해있던 노드 2를 스택에 넣고 방문 완료합니다. 위 과정을 통해 노드 7까지 스택에 삽입되었다면 노드 7, 6, 3은..