본문 바로가기

알고리즘 이론19

프림 알고리즘(Prim's algorithm) 1. 프림 알고리즘(Prim's algorithm): 크루스칼 알고리즘과 다르게(전체 간선을 정렬한 후 하나의 간선부터 시작), 하나의 특정 노드를 정하고, 연결된 간선 중 가중치가 가장 작은 간선을 선택하며 길을 확장하는 알고리즘 (예, 스타 크래프트 게임) - 크루스칼 알고리즘과 공통점: 둘다 탐욕 알고리즘을 구현함 2. 시간 복잡도: 최악의 경우(while문에서 모든 간선을 돌고, 최소 힙 구조를 이룬다면) O(E logE), - 개선된 시간 복잡도: O(E logV) 2020. 10. 12.
크루스칼 알고리즘(Kruskal's algorithm) 1. 신장 트리(Spanning Tree)의 조건 - 주어진 그래프의 모든 노드를 연결해야 한다 - 단, 노드를 연결할 때 사이클이 생겨선 안 된다 2. 최소 신장 트리 MST(Minimum Spanning Tree) - 최소 비용(간선 가중치의 합이 최소)의 Spanning Tree 3. 크루스칼 알고리즘(Kruskal's algorithm) - 간선의 비용을 기준으로 오름차순 정렬하여 비교할 노드를 선정 - 두 노드씩 최상위 노드를 탐색한 후, 서로 다를 경우 노드를 연결하는 알고리즘 - 부모 노드가 서로 다르다는 것은 연결해도 사이클이 발생하지 않는다는 것을 의미함 * 유니온-파인드(Union-Find) 알고리즘 활용 4. 시간 복잡도: O(E log E) def find(node): # path .. 2020. 10. 11.
유니온 파인드(Union-find) 알고리즘 유니온 파인드(Union-find) 알고리즘 Disjoint Set(서로소 집합)을 표현하기 위해 사용한다 (트리 구조를 활용함) 서로 중복되지 않은 부분집합끼리 연결했을 때 사이클이 생기는지 아닌지를 판단할 수 있는 알고리즘 더욱 간단하게, 노드들이 하나의 집합에 속해 있는지 찾거나, 노드들을 서로 연결하기(합치기) 위해 사용 2. 알고리즘의 구현 초기화: n개의 원소를 독립적인 집합으로 구분 초기화 find 함수: 두 개의 노드가 같은 집합(그래프)에 속하는지 확인하기 위해, 루트(최상위 부모) 노드를 찾는 로직 union 함수: 두 집합을 하나의 집합으로 합침(두 트리를 하나의 트리로 연결) 시간 복잡도 최악의 경우(아무 규칙 없이 구현할 경우) O(n) union-by-rank와 path-comp.. 2020. 10. 10.
다익스트라 알고리즘(dijkstra algorithm) * 최단 경로 구하기 알고리즘의 하나 - 다익스트라 알고리즘은, 특정한 노드에서 출발해 마지막 노드에 도착하는 것까지의 경로를 구하는 것과 관련 있다. - 관련 문제: 백준 10282번 - 해킹 (www.acmicpc.net/problem/10282) 백준 5719번 - 거의 최단 경로(www.acmicpc.net/problem/5719) import heapq mygraph = { 'A':{'B':8, 'C':1, 'D':2}, 'B':{}, 'C':{'B':5, 'D':2}, 'D':{'E':3, 'F':5}, 'E':{'F':1}, 'F':{'A':5} } def dijkstra(graph, start): # 초기화 distances = { node:float('inf') for node in gr.. 2020. 10. 10.

티스토리툴바