알고리즘/이론 (46) 썸네일형 리스트형 이분매칭 [1. 개요] 이분 매칭을 설명하기에 앞서 이분 그래프에 대한 개념 정의 그래프의 모든 정점이 두 그룹으로 나누어 질 때 서로 다른 그룹의 정점들은 연결되지만 같은 그룹의 정점들은 서로 연결하지 않는 형태의 그래프 두 집합 간의 대응 관계를 표현하기 위해 사용 https://testkernelv2.tistory.com/338 매칭 그래프에서 끝점을 공유하지 않는 간선의 집합을 의미한다. 여기서 끝점을 공유하지 않는다는 의미는 아래와 같다. 두개 이상의 간선이 공유하는 정점이 있는 경우. 아래와 같은 형태의 그래프에서 어떤 조건을 만족하는 edge 만 선별하였다고 가정했을 때, 빨간색 간선이 선별된 edge 그래서 매칭 문제(최대 매칭 문제) 는 그래프에서 가장 큰 매칭을 찾는 문제를 말하며, 가장 큰 매.. 네트워크 유량 - 예제1 [1. 문제 설명] https://algospot.com/judge/problem/read/MATCHFIX [2. 풀이 접근] [3. 코드] 네트워크 유량, 포드-풀커슨 [1. 개요] 그래프에서 간선에는 가중치라는 개념이 있다. 여기서 가중치 대신 용량이라는 개념을 적용하여, 일종의 파이프라고 모델링을 하고 이 간선을 통해 물을 흘려보낸다고 하자. 출발지에서 목적지까지 물을 흘려보낸다고 했을 때, 이 간선에 흐르는 양을 유량이라고 부를 수 있다. 이렇게, 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 흐름 혹은 유량을 보낼 수 있는지 계산하는 문제를 네트워크 용량 문제라고 한다. [2. 유량 네트워크] 각 간선에 용량(Capacity) 라는 추가 속성이 존재하는 방향 그래프를 말한다. 이 간선을 통해 유량을 흘려 보낼 수 있다 정점 u 에서 정점 v 로 가는 간선에 대해서 아래와 같이 표기하도록 한다. 용량: c(u, v), capacity 유량: f(u.. bfs - 예제2 [1. 문제 설명] https://algospot.com/judge/problem/read/HANOI4 [3. 코드] bfs - 예제1 [1. 문제 설명] https://algospot.com/judge/problem/read/CHILDRENDAY [2. 풀이 접근] 먼저 모든 어린이들에게 같은 수의 장난감을 주고, 욕심쟁이 어린이들에게는 원래 가진 것에서 하나 씩 더 주면 1차적인 조건을 만족 시킬 수 있다. 그래서 구하고자 하는 c 는 아래와 같은 조건이 성립한다. n + m 이상이다. c = kn + m 형태로, c 를 n 으로 나눈 나머지는 m 이다. d 에 포함된 숫자로만 구성되야 한다. 위와 같이 여러 조건을 동시에 만족하면서 답을 찾아야 할 때 일부 조건을 없앤 더 단순한 문제를 푼 후, 조건을 하나씩 추가해 가는 전략이 있다. 단, 어느 조건을 무시하고 문제를 푸느냐에 따라 난이도가 달라 질 수 있다. 여기서는 1번 조건을.. bfs [1. 개요] dfs 와 달리 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 가중치가 없는 그래프에서, 어떤 시작 정점에서 다른 모든 정점까지의 최단 경로를 계산 할 수 있다. 탐색 중, 처음 방문하는 정점이 있다면 방문 예정이라고 체크하고, (발견 여부라고 보는 것이 좀 더 정확?) Queue 에 푸쉬한다. dfs 와 비교하여 bfs 에서 모든 정점은 3가지 상태를 갖는다. 아직 발견되지 않은 상태 발견되었지만, 아직 방문하지 않은 상태 => 정점의 큐에 저장 된 상태 방문된 상태 [2. bfs 와 최단 거리] bfs 는 보통 딱 하나의 용도로 사용되는데, 두 정점 간의 최단 경로 문제이다. 가중치가 없는 그래프에서 사용 가능 어떤 시작 상태에서 타겟으로 하는 상태까지 가장 빨리 도달하는데.. dfs - 절단점 [1. 개요] DFS 를 응용해서 해결 할 수 있는 문제 중 하나로, 어떤 무방향 그래프에서 절단점이란 이 점을 제거함으로 인해 edge 가 제거되고 이로 인해, 컴포넌트가 두개 이상으로 나뉘어지는 정점을 말한다. 최초 그래프가 하나의 컴포넌트로 이루어 졌는데, 어떤 정점을 제거하여, 그래프가 두개 이상의 컴포넌트로 나뉘어지면 전체 그래프는 연결되어 있지 않을 수 있다. 이러한 절단점을 찾기 위한 가장 단순한 방법은 아래와 같은데 모든 정점에 대해서, 정점을 제거하고 dfsAll() 을 수행해서 컴포넌트 개수의 변화가 있는지 확인한다. 탐색 과정에서 얻는 정보를 이용하면, 한번의 dfs 로 모든 절단점을 찾아 낼 수 있다. 참조) https://testkernelv2.tistory.com/441 [2. .. dfs - 예제1 [1. 문제 설명] https://algospot.com/judge/problem/read/WORDCHAIN [2. 풀이 접근] [3. 코드] DFS - 오일러 서킷, 트레일 [1. 개요] dfs 를 이용하여 해결 할 수 있는 문제 중 오일러 서킷은 다음과 같은 문제를 말한다. 그래프의 모든 edge 를 정확히 한번만 사용해서 시작점으로 되돌아 오는 경로 무방향 그래프, 방향 그래프 모두에서 해결 가능하다. 기본적으로 오일러 서킷이 존재 할 수 없는 경우 그래프가 두 개 이상의 컴포넌트로 나뉜 경우 차수가 홀수 인 정점이 존재하는 경우 => 어떤 점으로 들어갔는데, 이 점의 차수가 1이면 나올 수 없다. => 이 점이 시작점이 아닌 경로의 끝점인 경우, 오일러 서킷을 완성 할 수 없다. 오일러 서킷이 존재 하는 경우 모든 정점의 차수가 짝수 => 단, 방향 그래프에서는 incoming edge 개수와 outgoing edge 개수가 같아야 한다. 모든 edge 가 하나의 컴포.. 아호-코라식 예제 [1. 문제 설명] https://algospot.com/judge/problem/read/NH [2. 풀이 접근] 종만 북 참조 [3. 코드] 이전 1 2 3 4 5 다음
