- 스패닝 트리 : 그래프 중에서 일부 간선을 선택해서 만든 트리. - 최소 스패닝 트리 : 스패닝 트리 중 간선의 가중치 합이 최소인 트리. 최소 스패닝 트리는 경로 세우기 문제에서 자주 나온다. - 크루스칼 - 모든 간선 중 가장 작은것을 뽑는다. 단, 간선이 사이클을 만드는지 아닌지는 union-find 를 기준으로 수행한다. - 프림 - 임의의 정점을 선택한다. 임의의 정점을 기준으로, 선택한 정점과 선택하지 않은 정점들을 연결하는 간선중에 최소값을 고른다. 이를 모든 정점을 돌 때 까지 2번 단계를 반복한다. 프림 프림부터 수도코드를 알아보겠다. 1. 임의의 정점을 선택한다. 선택표시를 한다. 2. 정점에 연결되어있는 임의의 간선을 PQ에 넣는다. 3. PQ에서 가장 적은 코스트의 간선을 뺀다...
Disjoint-set & Union-Find : 유니온 파인드
Union-Find 서로소, 상호배타 집합이란 서로 중복 표현된 원소가 없는 집합을 의미합니다. 이런 집합을 표현하기 위해서 "대표자" 라는 개념이 도입되는데, 이 대표자를 기준으로 각 집합을 구분할 수 있습니다. 이런 상호베타 집합에서 사용할 수 있는 연산은 아래 세가지로 분류됩니다. - make : 단위집합을 만드는 연산 (초기화 함수) - find : 어떤 한 element가 주어졌을 때, 그 element의 대표자를 구하는 연산. - union : 두 구성요소가 주어지고, 그 두 구성요소의 각 상호배타 집합을 합치는 연산. make는 이런 상호배타 연산을 하기 위해 초기셋팅하는 값입니다. (보통 상호배타집합이 주어지지 않고, 초기에 make()로 모든 엘리먼트를 상호배타집합으로 만든 뒤, 합쳐가며..
그래프 - 플로이드-와샬
플로이드 알고리즘은 모든 노드 쌍의 사이의 최소 비용을 구해주는 알고리즘이다. 플로이드 와샬 알고리즘은 N제한만 맞으면 사용하기 좋다. 예를들어서 아래와 같은 그래프가 존재한다고 해본다면, 플로이드 와샬 알고리즘을 적용하면 N1->N3에서 가는 최소값, N1->N2로 가는 존재하는 모든 쌍의 최소 거리 정보를 구할 수 있다. 물론 익히 알고있는 다익스트라알고리즘을 노드 개수만큼 V번 돌려서, 다익스트라(N1), 다익스트라(N2), 다익스트라(N3) 최소거리를 구할 수 있다. 하지만, 플로이드 와샬은 조금 더 간단하게 DP를 이용해서 문제를 해결한다. DP를 하기 위해 함수를 소개하자면, DP[x][y][k] 같은 3차원 배열을 채워나간다고 가정한다. - x->y 를 방문한다. - 단, 중간에 방문할 수 ..
그래프 - 다익스트라 알고리즘
다익스트라는 최소 알고리즘을 구하는 알고리즘이다. 다익스트라 알고리즘을 보기전에, 다익스트라의 알고리즘의 원형이라고 볼 수 있는 BFS를 알아보겠다. 이 글에서는 BFS의 개념에 대해서 다루지 않는다. 1. BFS - Shortest Path. BFS는 대표적으로 모든 간선의 길이가 1일 때, 가장 짧은 거리를 구할 수 있는 알고리즘이다. 만약 간선이 1이 아니라면 어떨까? 위와 같은 그래프에서 BFS를 적용하려면 아래와 같이 모든 간선을 1로 바꾸는 편법을 써서 BFS로 풀 수 있다. 실제로 이렇게 간선을 추가하는것은 너무 비효율적인 일이니, 이런 그래프 모양을 생각하고 조금 효율적으로 바꿔보겠다. d'(node) = 시작노드부터 - node까지 "임시" shortest path // bfs처럼 확장하..