kark's

프림 알고리즘또한 MST 를 해결하는 알고리즘이다. 이 알고리즘의 특징은 그리디한 방식으로 문제를 접근하며, 프림 알고리즘은 어떠한 자료구조를 사용하는지에 따라 효율성이 달라진다. Priority Queue 를 활용하면 간선의 선택을 효율적으로 할수있고 이경우 시간복잡도는 O((V+E log V)) 가 된다. ① 시작 정점을 기반으로 인접한 정점을 확인한뒤 우선순위 큐에 가중치 기준으로 데이터를 넣어준다. 이때 시작 정점은 방문된 상태라고 표기해준다. ② 큐에서 추출된 정점을 방문으로 표기해준뒤 인접한 정점을 확인한뒤 ①의 과정과 마찬가지로 큐에 넣어준다. ③ 위 과정을 반복하며 모든 정점을 방문하게 되면 MST가 구해진다. 시작 1번 정점으로 부터 인접한 정점과 가중치를 확인 큐에 넣어주고 1 정점은 ..

신장 트리는 그래프 내 모든 정점을 거치며 사이클이 없는 트리다. N개의 정점이 있다면 간선의 수는 N-1 로 구성된다. 최소 신장트리란 각 간선의 비용을 최소화하여 구성된 모든 정점을 거치는 트리이다. 이번 글은 크루스칼(Kruskal) 알고리즘으로 해결한다. 크루스칼 알고리즘은 MST를 해결하기 위한 방법중 하나이며, 크루스칼 알고리즘 방식으로 문제를 접근하기 위해서는 유니온 파인드 자료구조를 활용해야한다. 크루스칼 알고리즘은 모든 간선의 가중치를 오름차순으로 정렬하여 순서대로 간선을 선택하며 트리를 추가하는 방식으로 작동한다. 이 알고리즘의 효율성은 간선을 정렬하는 과정과, 사이클을 형성하는지 검사하는 과정에 크게 의존된다. 간선정렬 O(E log E) 유니온-파인드 사이클형성 검사는 거의 상수시간..

해당 알고리즘 설명은 자료구조탭의 'DisjointSet 서로소집합' 글 참조 https://kark.tistory.com/15 서로소집합 DisjointSet 각 원소가 집합을 이루게 하거나, 집합을 관리하기 위해 사용되는 자료구조 각 원소가 어떤 집합에 속하는지 빠르게 찾아내고 두개의 집합을 하나로 합치는 연산을 지원한다. 최소 신장트리 알 kark.tistory.com 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www...

다익스트라 알고리즘은 그래프에서 한정점에서 다른 정점으로의 최단경로를 찾는 알고리즘 edge 의 가중치가 양수여야지만 사용할수 있다. 시작 정점에서 가장 가까운(비용이 적은) 정점을 찾고, 다음으로 가까운 정점을 찾아가는 과정을 반복 ① 초기 시작으로 주어진 정점의 비용을 0으로 설정하고, 나머지 정점은 아직 확인하지 못했으므로 무한대의 값으로 지정해둔다. ② 현재 정점에서 인접정점으로 가는 비용과 현재까지의 비용의 합이 인접정점이 갖고있던 비용보다 적다면 해당 비용을 수정하고 다음 탐색목록에 추가시켜준다. 이때 이미 방문했던 정점이라면 비용 수정 과정만 거치고 해당정점의 탐색은 하지 않게한다. ③ ②의 과정을 반복하며 우선순위 큐의 탐색목록이 없을때까지 또는 모든 정점의 방문이 끝났다면 탐색 완료 1을..

깊이우선탐색은 그래프의 모든 정점을 탐색하는 알고리즘중 하나 주변의 모든 인접점을 확인하며 탐색을 진행하는 BFS 알고리즘과는 반대로 현재 갈수있는 경로가 있다면 해당경로의 가장 깊은곳까지 탐색하는 방식이다. 해당알고리즘은 Stack 자료구조나 재귀함수로 구현하는게 일반적이다. 비선형자료구조를 탐색, 사이클 감지에 유용하며 모든 레벨의 노드를 기억해야하는 BFS 알고리즘과는 다르게 DFS 현재의 경로만 기억하면 되므로 BFS 보다는 메모리 효율을 높일수 있다는 점이 있다. 또한 DFS 탐색방법과 백트레킹방식으로 최적의 해를 구하는데 유용할수 있다. 0 정점을 시작으로 탐색을 진행해보자 0 정점의 인접점은 1 , 2 의 정점이 있다. 재귀함수 형태로 진행되는 과정을 표현해보자면 위의 그림과 같다. 함수를 ..

BFS는 탐색 방법중 하나로 시작 정점을 방문한뒤 인접한 정점들을 모두 탐색하는 방법을 뜻한다. 순차적으로 접근하는 방식을 사용하기위해 Queue 의 자료구조가 적합하며 가장 일반적이다. 사용시 주의할부분은 방문한곳을 다시 방문하지않게 처리해줘야한다. 위의 그림과 같은 노드가 있다고 가정해보자. 목적은 노드중에 8값을 찾아야한다. BFS 알고리즘으로 다음과 같은 탐색을 할경우 시작점을 가장먼저 Queue에 넣음으로 시작해 인접한 모든 정점을 다시 Queue에 넣어준다. Queue에 들어있던 0의 정점을 빼준뒤 인접한 정점들을 전부 확인한 다음 확인된 정점들을 다시 넣어준다. 이후 더이상 인접한 정점이 없으며 하나씩 Queue에서 빼면서 대상을 확인하면 된다. 문제 https://www.acmicpc.ne..