Algorithm

이분 매칭(Bipartite Matching)

이전 게시글인 에 이어지는 알고리즘 개념 글입니다 https://codingsmu.tistory.com/109 이분 매칭(Bipartite Matching)이란? 네트워크 플로우의 개념중에서 이분 그래프(Bipartite Graph)에서의 최대 유량(maximum flow)을 구하는 경우로, 에지의 용량(capacity)이 전부 1인 이분 그래프에서의 최대유량(maximum flow)을 구하는 문제는 이분 그래프에서의 최대 매칭(maximium matching)과 동치이다. 이때 매칭은, 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미로 이분그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉 혹은 에드몬드 카프 알고리즘을 이용해 구해줄 수 있으나, DFS를 이용하여 O(V*E)시간에 쉽게 구현할 수 있다..

최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상(LCA)란? LCA란 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v거나 v의 조상인 노드들 중 가장 깊은 노드이다 예를들어, 아래의 트리에서 노드 4와 3의 LCA는 1번 노드이다 다른 예로는 노드 9, 14의 LCA는 2번 노드이며, 노드 3, 13의 LCA는 3번 노드이다 여기서 한가지 사실을 알 수 있는데 노드 u,v와 이들의 LCA w의 관계이다 u,v의 최단 경로는 u-w-v 형태라는 것이다 이를 아래의 트리에서 빨간 경로로 확인할 수 있다 따라서, 트리 문제에서 최단경로를 빠르게 찾길 원한다면 가장먼저 LCA를 생각해봐야 한다 LCA 구현 방법 1. 노드 u,v 가 서로 만날때까지 부모노드를 따라서 두 노드를 옮겨 보는 방법 : 선형 탐색 두..

단절점(Articulation Point), 단절선(Articulation Bridge)

단절점(Articulation Point)이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나눌 수 있는 정점을 단절점이라고 한다 아래의 그래프에서 하이라이트된 정점들이 A-point이다 단절점 구하는 방법 단절점을 구하기 위해서는 먼저 단절점의 특성에 대해 알아야 한다. 어느 한 정점이 단절점이라면, 단절점에 바로 인접해 있는 정점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어 있지 않아야 한다 예를 들어 5번 정점이 단절점이라고 생각해보자. 5번 정점을 제거하더라도 인접노드인 4, 6을 우회로(4-8-6)로 연결되어 있으므로 5번은 단절점이 될 수 없다 이번에는 4번 정점이 단절점이라고 생각해보자 4번 정점을 제거하게 되면 (2,3) 과 (5,8)은..

세그먼트 트리 Segment Tree

세그먼트 트리란? 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 빠르고 간단하게 구할 수 있는 자료구조 세그먼트 트리에서 노드들의 의미 리프 노드 : 배열의 구 수 자체 리프 노드를 제외한 다른 노드 : 왼쪽 자식과 오른쪽 자식의 최솟값 또는 합을 저장 n = 10인 경우 세그먼트 트리는 다음과 같다 트리 만들기 세그먼트 트리는 포화 이진 트리에 가깝기 때문에 배열에 모든 값이 대부분 가득 차게 됨 따라서 배열로 트리를 만들어 사용 이 경우 임의의 노드의 인덱스가 i일 때 왼쪽 자식의 인덱스는 2*i 오른쪽 자식의 인덱스는 2*i + 1 세그먼트 트리의 구현(C++) #include #include #include using namespace std; // arr : intial a..

강한연결요소 : Strongly Connected Component

강한연결요소 : Strongly Connected Component Concept 방향 그래프 G의 임의의 노드 쌍 u,v에 대해 u->v, v->u로 가는 경로가 존재하면 G는 Strongly Connected 되었다고 한다 따라서 G의 u->v 로 가는 경로가 있을 때, 엣지의 방향을 정반대로 바꾼 transpose G에도 u->v로 가는 경로가 있다면 두 노드 사이에 사이클이 있어 SCC를 만족한다 Kosaraju's Algorithm #include #include #include #include #define MAX 10001 using namespace std; int n, out_len; bool check[MAX], check2[MAX]; vector r[MAX], r2[MAX]; stac..

위상 정렬 Topological Sort

위상 정렬(Topological Sort)이란? 정렬 기준이 '위상'으로 여기서 위상이란 진입차수(incoming edge의 수)를 의미한다 위상 정렬의 특징 - Directed Acyclic Graph(DAG)에서만 가능 - 즉, 방향을 가지며 싸이클은 형성하지 않는 그래프를 말한다 - 보통 일의 순서를 정하는 알고리즘에서 많이 사용됨 위상 정렬 알고리즘 각 노드의 위상(incoming edge의 수)를 저장 위상이 0인 노드를 큐에 푸쉬 큐가 빌 때까지 아래 과정 반복 큐에서 노드를 꺼내 해당 노드와 연결된 노드의 간선을 모두 제거(동시에 연결된 노드의 위상을 하나씩 낮춰줌) 큐에서 꺼낸 노드를 위상정렬에 넣어줌 위상이 0인 노드를 큐에 푸쉬

[이론] 우선순위 큐 (Priority Queue)

우선순위 큐란? 일반적인 큐는 선입선출(FIFO) 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되는데, 우선순위 큐는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다 우선 순위 큐는 최소 우선 순위, 최대 우선 순위 2가지로 구분할 수 있다 최소 우선순위 큐 : 가장 우선 순위가 낮은 요소를 삭제 최대 우선순위 큐 : 가장 우선 순위가 높은 요소를 삭제 스택 vs 큐 vs 우선순위 큐 자료구조 삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터 우선순위 큐의 추상 자료형(ADT) 객체 : n개의 element형의 우선순위를 가진 요소들의 모임 연산 create() ::= 우선순위 큐를 생성 init(q) ::..

[이론] 힙(Heap)

힙(Heap)란?여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조로  최대 힙(max heap)와, 최소 힙 (min heap)두 가지 종류로 나뉘게 된다최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 최대 힙과 최소 힙은 항상 아래의 조건이 성립하게 된다최대 힙 : $key(부모노드) >= Key(자식노드)$최소 힙 : $key(부모노드)  힙의 특징힙의 목적은 삭제 연산이 수행될 때마다 가장 큰/작은 값을 찾아내기만 하면 된다(가장 큰/작은 값은 루트 노드에 있음) 따라서 힙 안에서 데이터들은 느슨한 정렬 상태를 유지한다 즉, 전체 데이터를 정..