0. 스위프트에는 왜 우선순위 큐가 없을까? 스위프트는 우선순위 큐가 기본적으로 없다. 정확히 말하자면 개념이 없다기 보다 구현이 안되어 있다. iOS 단독 언어인 주제에 구현되어있지 않다니... 이 이자식! 파이썬은 멀티 쓰레드 버전 / Unsafe 멀티 쓰레드 버전 구분되어 있어서 때에 따라서 다르게 쓰는데 스위프트는 없다. 그럼 직접 구현해야지 뭐... 힙을 이용해서 구현해보자. 1. 코드 import Foundation struct Heap { var nodes = [T]() var isEmpty: Bool { nodes.isEmpty } var sort: (T, T) -> Bool mutating func insert(_ ele: T) { nodes.append(ele) swapUp(nodes...

0. 개요 모든 정점에서 모든 정점으로의 최단 경로를 구할 수 있다. 단, 모든 정점은 양의 간선이여야 한다. 1. 구현 방법 우선 정점의 개수가 V개 라면 V X V 의 배열을 만들어야 한다. 배열의 [3][5] 이라면 3번 정점 -> 5번 정점의 최단 거리를 나타내는 것이다. 구현 방법은 다음과 같다. 이차원 배열은 다음과 같이 저장한다. 주어진 간선은 이차원배열에 저장 이차원 배열에서 X축과 Y축이 같으면 0으로 저장 간선에 나와 있지 않은 숫자들은 INF(무지막지하게 큰 수)로 저장 for 경유정점 in range(V): for 시작 정점 in range(V): for 도착정점 in range(V): dist[시작정점][도착종점] = min(dist[시작정점][도착종점], dist[시작종점][경유..

0. 개요 벨만포드 알고리즘은, 그래프 중 음수간선이 있을 때 시작 정점에서부터 임의 정점까지 거리를 알 수 있다. 음의 사이클의 존재여부도 위 알고리즘을 통해 감지 할 수 있다. 최단거리 알고리즘 중에서 음수 간선이 있어도 유효하다. 1. 구현 벨만포드 알고리즘은 [ 1번 정점부터 N번 정점까지 최단거리를 BFS로 최신화하는 루프 ]를 N-1번 순회하는 알고리즘이다. 2. 설명 위의 그래프를 예시를 들어보자. 1번 노드를 출발점이라 가정하자. 정점이 4개이므로 1번~4번정점까지 총 3(4-1)번 반복하면 된다. 정점 번호 1 2 3 4 dist 0 INF INF INF 1번째 반복 정점 번호 1 2 3 4 dist 0 INF -8 -12 1번 정점부터 4번 정점까지 순차적으로 BFS로 최단거리를 갱신하..

0. 개요 다익스트라 알고리즘은, 특정 시작 점에서 다른 한점까지의 최단거리를 측정할 수 있다. 단, 모든 간선은 양의 간선 이여야 한다. 하는데 사용하는 알고리즘이다. 먼저 개념은 아래의 EBS 영상이 가장 잘 나타내고 있음으로 아래의 영상을 참고하길 바란다. 1. 구현 방법 사용되는 자료구조는 힙큐 혹은 우선순위 큐 이다. 1. 우선 그래프에 있는 모든 정점들에 대해서 거리를 메모할 리스트를 생성한다. dist = [INF for _ in range(V)] # INF는 엄청 큰 수 / V는 꼭지점의 개수 2. 시작점을 우선순위 큐에 넣는다. 이 때, 거리가 가까운 정점을 먼저 방문해야 하므로 (거리, 정점 번호) 로 우선순위에 넣는다. 3. 우선순위 큐에서 정점 하나를 꺼내서 인접한 꼭지점의 dist..