푸으름

Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알고리즘 이분 그래프는 두 개의 정점 그룹이 존재할 때 모든 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프 이러한 이분 그래프에서 예를 들어, 한 그룹은 X그룹, 다른 한 그룹은 Y그룹이고 간선의 방향은 X->Y라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것 ✏️예시 먼저 알파벳 그룹과 숫자 그룹이 있다고 가정을 하면 A에서 갈 수 있는 숫자는 1과 3 B에서 갈 수 있는 숫자는 1과 2 C에서 갈 수 있는 숫자는 5 D에서 갈 수 잇는 숫자는 3 E에서 갈 수 있는 숫자는 2 A부터 매칭을 시작하면 각 점에서는 한 개의 숫자만 갈 수 있으므로 A는 1과 연결(총..

Algorithm 공부 - 탐색(깊이 우선 탐색과 너비 우선 탐색) 깊이 우선 탐색(Depth-First-Search) ● 그래프 완전 탐색 기법 ● 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정한 후 최대 깊이까지 탐색을 마친 후 다른 분기로 이동 ● 노드의 개수를 V, 엣지의 개수를 E라 하면 시간 복잡도는 O(V+E) ● 단절점 찾기, 단절선 찾기, 위상 정렬, 사이클 찾기 등의 문제에 활용됨 ● 탐색 방법 1. 인접 리스트로 그래프 표현하기 + 방문 여부를 체크할 배열 만들기 + 스택에 시작 노드 삽입하기 2. 스택에서 노드를 POP한 후 그 노드와 인접 노드 삽입하기, 없다면 다음 노드로 이동 3. 스택 자료구조에 값이 없을 때까지 계속해서 반복 백준 2751번 수 정렬하기2 https..