본문 바로가기

분류 전체보기

 (134)
126. Kruskal's Algorithm 크루스칼 알고리즘(Kruskal's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 알고리즘 중 하나로, 다음과 같은 방법으로 작동한다. 1. 확인하지 않은 간선들 중 가중치가 가장 작은 간선 하나를 고른다. 2. 현재까지의 최소 스패닝 트리에서 선택한 간선이 연결하는 두 정점이 연결되어 있지 않다면, 이 간선을 최소 스패닝 트리에 추가한다. 3. 모든 간선을 확인했다면 종료한다. 그렇지 않다면 1번으로 돌아간다. 설명이 매우 간단하게 끝난다. 예시를 통해서 자세히 살펴보자. 앞에서 나온 그래프이다. 여기서 가중치가 작은 간선들부터 하나씩 확인하면서 최소 스패닝 트리를 만든다. 먼저 가중치가 $2$인 간선들이 최소 스패닝 트리에 추가된다. 다음으로 가중치가 $3$인 간선을 확인하는데, 정점..
125. Minimum Spanning Tree 무향 연결 그래프의 스패닝 트리(신장 트리, Spanning Tree)는 그래프의 모든 정점을 포함하는 트리이다. 쉽게 말해서 그래프에서 (그래프가 분리되지 않도록) 간선들을 제거해서 트리 구조가 남았을 때 이를 스패닝 트리라고 한다. 하나의 그래프에 여러 개의 스패닝 트리가 존재할 수 있다. 간선에 가중치가 있는 그래프는 스패닝 트리에 포함되는 간선의 가중치의 합이 다양하게 나올 수 있는데, 이중 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리(최소 신장 트리, Minimum Spanning Tree, MST)라고 한다. 이 최소 스패닝 트리가 꽤 다양한 곳에서 사용되므로 알아 두면 좋다. 무향 연결 그래프에서 최소 스패닝 트리를 구하는 방법은 여러 가지가 있는데, 이 블로그에서는 세 가지를 ..
124. Disjoint Set & Union-Find 이번에 다루는 내용은 트리 구조를 응용한 것이다. 집합론에서 분리 집합(Disjoint Set)은 공통 원소가 없는 두 집합을 의미한다. 컴퓨터과학에서 이 개념은 한 개 이상의 집합으로 확장되며, 한 개의 집합 또는 어떤 두 집합도 공통 원소를 갖지 않는 두 개 이상의 집합을 분리 집합이라고 생각하면 된다. $0$개의 집합 같은 경우는 생각하지 않는다. 분리 집합은 아래의 두 가지 연산에 의해서 여러 활용도를 갖게 된다. 두 집합을 하나로 합친다. (Union) 원소가 현재 어떤 집합에 속해 있는지 확인한다. (Find) 이 두 연산의 이름을 따서 유니온-파인드(Union-Find)라는 이름이 생겨났다. 이 개념을 PS의 관점에서 보면, 일단 각각의 집합은 서로 구별이 가능한 식별자를 갖고 있어야 한다...
123. Topological Sorting 위상 정렬(Topological Sorting)은 DAG의 정점을 재배열하는 알고리즘으로, 정점을 재배열했을 때 간선의 방향은 모두 동일해야 한다. 모든 DAG는 위상 정렬이 가능하며, DAG가 아닌 모든 그래프는 위상 정렬이 불가능하다. 위상 정렬을 하는 방법은 다음과 같다. 1. 아직 선택하지 않은 정점들 중 진입 차수가 $0$인 정점 하나를 선택하고 정렬된 정점 목록의 맨 뒤에 추가한다. 2. 선택한 정점 및 그 정점과 연결된 간선들을 그래프에서 제거한다. 3. 모든 정점이 선택될 때까지 과정 1, 2를 반복한다. 아래의 그래프에서 위상 정렬을 실행하면 다음과 같다. 진입 차수가 $0$인 정점은 $\text{D}$ 하나이므로 정점 $\text{D}$ 및 정점 $\text{D}$와 연결된 간선들을 그..
122. Directed Acyclic Graph DAG(Directed Acyclic Graph)는 사이클이 존재하지 않는 유향 그래프를 의미한다. 정의는 이렇게 간단하지만 응용할 수 있는 분야는 상당히 넓은 편이며, 최근에는 블록체인에서도 많이 다루면서 점점 주목받고 있는 개념이기도 하다. 사회과학에서도 등장한다고 한다. 그래프 이론의 관점에서 DAG의 큰 특징은 다음과 같이 나타낼 수 있다. 진입 차수가 $0$인 정점이 하나 이상 존재한다. 진출 차수가 $0$인 정점이 하나 이상 존재한다. 어떤 정점 및 그 정점과 연결된 간선들을 그래프에서 제거할 경우 남는 정점과 간선들로 이루어진 그래프도 DAG이다. 모든 정점을 순서대로 나열했을 때 간선의 방향이 전부 동일하게(왼쪽 → 오른쪽 또는 오른쪽 → 왼쪽) 할 수 있다. 네 번째 특징에 나온 정점 나..
121. Independent Set & Clique 그래프에 포함된 정점 $0$개 이상을 포함한 집합이 다음 조건을 만족할 경우 그 집합을 그래프의 독립 집합(Independent Set)이라고 한다. 그래프에 존재하는 임의의 간선이 정점 $u$와 정점 $v$를 연결할 때, $u$와 $v$ 중 최소한 한 정점은 집합에 속하지 않는다. 간단히 말하면 독립 집합에 속한 정점들 사이를 직접 연결하는 간선이 없다는 것이다. 이것은 트리에도 똑같이 적용할 수 있고, 트리에 존재하는 독립 집합을 트리의 독립 집합이라고 한다. 또한 독립 집합들 중 가장 많은 정점을 포함하는 집합을 최대 독립 집합(Maximal Independent Set)이라고 한다. 하나의 그래프/트리에 두 개 이상의 최대 독립 집합이 존재할 수도 있다. 독립 집합을 정의할 때의 특이사항은 그래프..
120. Dial's Algorithm 다이얼 알고리즘(Dial's Algorithm)은 간선들의 가중치가 크지 않은 그래프에서 최단 경로를 구할 때 사용할 수 있는 알고리즘으로, $0$-$1$ BFS의 발전된 버전이라고 생각할 수도 있다. 각각의 간선의 가중치가 $0$ 이상 $c$ 이하의 정수일 때 다이얼 알고리즘은 $(c+1)$개의 큐를 사용하여 최단 경로를 구한다. 큐 대신 스택, 벡터 등을 사용할 수도 있다. $c = 1$일 경우 $0$-$1$ BFS와 매우 유사한 형태가 되며, $2$개의 큐를 하나의 덱으로 바꾸면 $0$-$1$ BFS와 같아진다. 다이얼 알고리즘의 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 경로를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치..
119. 0-1 BFS $0$-$1$ BFS는 모든 간선의 가중치가 $0$ 또는 $1$인 그래프에서 사용할 수 있는 최단 경로 알고리즘으로, 한 정점에서 다른 정점들까지의 최단 경로를 구한다. 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 빈 덱에 정점 $k$를 추가한다. 5. 덱의 맨 앞에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자. 6. $u$가 아직 선택되지 않았으면, $u$를 선택하고 $u$와 인접한 정점을 확인한다. $u$와 인접한 각각의 정..

티스토리툴바