최단 거리 알고리즘 대표 3가지다익스트라 알고리즘(Dijkstra's Algorithm):한 노드로부터 다른 모든 노드까지의 최단 경로를 찾을 때 사용되며, 가중치가 양수인 경우 사용one(시작점) to many(도착점). 가중치 양수만 허용벨만-포드 알고리즘(Bellman-Ford Algorithm):다익스트라 알고리즘과 유사하지만, 가중치가 음수인 간선이 있을 경우에도 사용할 수 있음one(시작점) to many(도착점). 가중치 음수도 허용플로이드-워셜 알고리즘(Floyd-Warshall Algorithm):모든 노드 쌍 사이의 최단 경로를 찾는 데 사용many(시작점) to many(도착점). 가중치 음수도 허용 다익스트라 알고리즘(Dijkstra's Algorithm) 과정출발 노드 설정최단 거..
코딩테스트 준비 (알고리즘 & SQL)/알고리즘 이론
최소 신장 트리 (Minimum Spanning Tree, MST)주어진 가중치 그래프의 모든 정점을 최소한의 비용으로 연결하는 부분 그래프쉽게 말하면, 최소 비용으로 모든 지점이 서로 통행 가능하도록 연결한다.종류 : 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘 등 크루스칼(Kruskal) 알고리즘 과정가장 작은 가중치를 가진 간선부터 선택선택될 간선 개수 = 총 정점 개수 - 1간선 선택 시 사이클이 생기지 않도록 한다. 사이클 형성 여부는 union-find 자료구조를 사용한다. 예제 코드 (python)더보기# 특정 원소가 속한 집합 찾기def find_parent(parent: list, x: int): # 루트 노드 찾을 때까지 재귀 호출 if parent[x] !=..
