본문 바로가기

알고리즘/그래프

알고리즘/그래프 2020. 5. 11. 최소 공통 조상 최소 공통 조상(Least Common Ancestor, LCA)는 트리에 있는 정점 \(u, v\)에 대해, \(u\)와 \(v\)의 공통 조상 중 가장 가까운 것을 말합니다. 예를 들어 아래와 같은 트리에서, 2번 정점과 7번 정점의 LCA는 1번 정점, 9번 정점과 4번 정점의 LCA는 2번 정점입니다. 그러면 LCA를 구하는 알고리즘에 대해 알아봅시다. 1. \(O(n)\) Navie https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. www.a..
알고리즘/그래프 2020. 5. 10. 위상 정렬 위상 정렬(Topological sorting)은 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 말합니다. 쉽게 말해서 간선 \(u \rightarrow v\)가 있다면, 정점 \(v\)는 무조건 정점 \(u\)이후에 등장해야 합니다. 예를 들어 다음과 같은 유향 그래프에서, $$\{1, 5, 2, 3, 6, 4\}$$ 는 가능한 위상 정렬 중 하나입니다. 방향 그래프에 사이클이 존재한다면, 위상 정렬 역시 존재할 수 없습니다. 따라서 그래프는 항상 '사이클 없는 유향그래프'(Directed Acyclic Graph, DAG)여야 합니다. 그러면 위상 정렬을 구하는 알고리즘에 대해 알아봅시다. https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫..
알고리즘/그래프 2020. 5. 5. 최소 스패닝 트리 우선 '최소 스패닝 트리'가 무엇을 뜻하는 단어인지 먼저 알아봅시다. 우선 '트리'란, 사이클을 갖지 않는 연결 그래프를 뜻합니다. 정점이 \(V\)개인 트리는 \(V-1\)개의 간선으로 모두 연결되어 있게 됩니다. '그래프의 스패닝 트리'는, 그래프에서 일부의 간선을 선택해 만든 트리를 뜻합니다. 따라서 이 연결 그래프는 다음과 같은 스패닝 트리를 가질 수 있게 됩니다. 물론 위 2가지의 형태가 아닌 다른 형태의 스패닝 트리도 존재합니다. '그래프의 최소 스패닝 트리'는, 가중치가 있는 연결 그래프에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 말합니다. 따라서 이 연결 그래프의 최소 스패닝 트리는 이런 형태가 됩니다. 가중치의 합은 17로, 가중치의 합이 이보다 작은 스패닝 트리는 만들 수 없습니..
알고리즘/그래프 2020. 4. 29. 최단 경로 그래프에서 두 정점 사이의 최단 경로를 구하는 알고리즘에 대해 알아봅시다. BFS 간선의 가중치가 모두 1이라면(같다면), BFS를 이용해 한 정점에서 다른 정점들 사이의 최단 거리를 알 수 있습니다. 자세한 설명은 https://anz1217.tistory.com/21 그래프 탐색 (DFS, BFS) 그래프는 정점과 정점들을 잇는 간선들의 집합으로 이루어진 자료구조입니다. 이 글에서는 그래프를 저장하는 방법과, 그래프를 탐색하는 방법에 대해 알아보도록 합시다. 다음과 같은 그래프를 저장한다고 생각해.. anz1217.tistory.com 에서 볼 수 있습니다. 시간 복잡도는 \(O(|V|+|E|)\)입니다. 0-1 BFS 문제를 조금 확장해 봅시다. 간선의 가중치가 모두 0또는 1이라면 어떻게 최단 거..
알고리즘/그래프 2020. 4. 28. 그래프 탐색 (DFS, BFS) 그래프는 정점과 정점들을 잇는 간선들의 집합으로 이루어진 자료구조입니다. 이 글에서는 그래프를 저장하는 방법과, 그래프를 탐색하는 방법에 대해 알아보도록 합시다. 다음과 같은 그래프를 저장한다고 생각해 봅시다. 정점은 총 6개 입니다. \(V = \{1,2,3,4,5,6\}\) 간선은 총 7개 입니다. \(E = \{(1,2),(2,3),(2,5),(2,6),(3,4),(3,6),(4,5)\}\) 일반적으로 그래프를 저장하는 방법에는 3가지가 있습니다. 1. 인접 행렬 $$\left[\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 ..

티스토리툴바