꿈돌이랜드

프림 알고리즘프림 알고리즘은 크루스칼 알고리즘과 마찬가지로 MST를 구하는 알고리즘동작임의의 정점을 선택해서 비어있는 T 트리에 포함시킨다.T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.찾은 간선이 연결하는 두 노드 중, T에 없던 노드를 T에 포함시킨다.이 때, 1에서 찾은 간선도 같이 T에 포함된다.모든 노드가 T에 포함될 때 까지, 1, 2를 반복한다. 아래는 그림으로 설명된 것입니다.임의의 정점을 선택해서 빈 T에 포함시킨다.예를 들어 1을 선택합니다.T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.빨간색과 파란색을 연결하는 간선 중 가중치가 최소인 것을 찾는다. 1-3과 1-2 중, 가중치가 더 작은 간선은 가중치가 4인 1-3을..

신장 트리그래프의 모든 정점을 포함하는 트리를 말한다.그래프의 최소 연결 부분 그래프로 사이클이 없다.정점의 개수가 n개면 간선의 개수가 n-1개 이다.최소 신장 트리신장 트리는 신장 트리 중 가중치 합이 최소인 신장 트리를 말한다.예제)도시마다 도로를 짓는데 최소 거리가 되도록 구축집마다 전화망 설치하는데 최소 비용이 되도록 설계 최소 신장 트리 알고리즘대표적으로 크루스칼, 프림 알고리즘이 있다.크루스칼 알고리즘그리디 알고리즘을 이용한다.간선 선택을 기반으로 하는 알고리즘최소 신장 트리가 최소 비용의 간선으로 구성되고, 사이클을 포함하지 않는다는 두 조건에 따라서 매 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.이전 단계에서 만든 신장 트리와는 관계 없이 무조건 최소 간선만을 선택하는 방법..

크루스칼 알고리즘그리디를 사용하여 그래프의 최소 신장 트리를 구하는 알고리즘최소 신장 트리가 1) 최소 가중치의 간선으로 구성, 2) 사이클을 포함하지 않다는 조건으로 각 단계에서 사이클을 이루지 않는 최소 가중치 간선을 선택한다.동작그래프의 간선들을 가중치의 오름차순으로 정렬한다.정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.가장 낮은 가중치를 먼저 선택사이클을 형성하는 간선을 제외해당 간선을 현재의 최소 신장 트리의 집합에 추가한다.주의할 점은 간선을 선택할 때, 해당 간선이 사이클을 생성하는지 그 여부를 확인해야 하는데, 그 여부를 검사하기 위해 유니온 파인드 알고리즘을 이용해야 한다. Disjoint-Set유니온 파인드 알고리즘에 대해 공부하기 전 Disjoint-Set의..

벨만 포드 알고리즘벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘다익스트라 알고리즘과 다르게 음수 가중치가 있는 그래프에서도 최단 거리를 구할 수 있다단, 다익스트라 알고리즘은 시간복잡도가 O(ElogV)인데 비해, O(VE)로 느리다. 다익스트라 알고리즘 vs 벨만-포드 알고리즘다익스트라벨만포드매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 방문하여 한 단계씩 최단 거리를 구해나간다 (그리디)매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다.음수 간선이 있는 경우를 제외하면 최적의 해를 찾을 수 있다음수 간선이 있는 경우에도 최적의 해를 찾을 수 있다.시간복잡도가 O(ELogV)시간복잡도가 O(VE..

LowerBound동작방식구현UpperBound동작방식구현참조LowerBound와 UpperBound는 모두 이진탐색(BinarySearch)을 응용한 알고리즘이다.일반적으로 이진탐색은 찾고자 하는 값이 정확히 없다면 탐색을 실패한다.하지만 LowerBound와 UpperBound는 범위에 초점이 맞춰져 있어, 같은 원소가 여러개 있더라도 사용할 수 있다.개념은 알지만 구현 시 자주 헷갈리므로 정리해보자.LowerBound동작방식LowerBound는 찾고자 하는 값 이상의 값이 처음으로 나타나는 인덱스이다.LowerBound의 동작 방식은 다음과 같다. 초기에 left는 배열의 시작 위치, right는 배열의 길이로 세팅한다right가 배열의 끝 위치가 아니라, 길이로 처음에 셋팅한다는 점에 유의하자중간..

그래프 최단 경로 찾기 문제 유형PS에서 최단 경로 문제는 다음과 같은 종류로 나눌 수 있다.단일 출발 - 단일 도착 최단 경로그래프 내 특정 노드 A에서 출발해서, 다른 특정 노드 B에 도착하는 가장 짧은 경로를 찾는 문제위와 같은 가중치 그래프가 주어졌을 때, A-F 간 최단 경로를 찾는 경우가 이에 해당한다.단일 출발 최단 경로그래프 내 특정 노드 A에서 출발해서, 그래프에 존재하는 모든 노드들에 대한 가장 짧은 경로를 찾는 문제그래프 내 가중치들이 음수가 아닌 경우에 다익스트라 알고리즘을 사용한다전체 쌍(all pair) 최단 경로그래프 내 모든 노드 쌍들에 대한 최단 경로를 찾는 문제플로이드 와샬 등의 알고리즘을 사용 다익스트라 알고리즘시작 노드를 기준으로 하여 연결되어 있는 노드들을 추가하며 ..

Swift로 우선순위 큐를 구현하려면 직접 힙을 구현해야한다. 여기 Swift로 구현한 힙이 있습니다. 찾은 자료중 가장 깔끔한것 같아요.final class Heap { private var nodes: [T] = [] private let sort: (T, T) -> Bool init(sort: @escaping ((T, T) -> Bool)) { self.sort = sort } var isEmpty: Bool { nodes.isEmpty } func insert(_ data: T) { var index = nodes.count nodes.append(data) while index >= 0, sort(nodes[index], nodes[(index-1) / 2]) { nodes.swapAt(ind..

플로이드 와샬 그래프 문제에서 자주 출제되는 문제 유형. 그래프 유형에서 크루스칼과 플로이드 와샬이 대표적인 그리디 알고리즘 크루스칼 → 최소 간선을 싸이클 없이 더해가면서 최소 비용을 찾는과정 (한 정점에서 다른 정점으로 가는 최단거리) 플로이드 와샬 → 현재 노드의 최솟값을 지정할 때 현재 값과 다른 경로로 왔을 때의 최솟값을 비교해서 대입하는 방식 (모든 정점에서 다른 정점으로 가는 최단거리) 이런 그래프에서 1에서 5까지 가는 경우를 생각해보면 1-2-3-5 : 5코스트 1-2-5: 3코스트 플로이드 와샬은 이런 경우에 유용함! 코드 형태 func floydWarshall() { for i in 0..