프림 알고리즘 (Prim's Algorithm)
April 10, 2025이전 포스트에서 크루스칼 알고리즘으로 최소 신장 트리(MST)를 구하는 방법을 정리했습니다. 이번에는 같은 MST 문제를 다른 방식으로 접근하는 프림 알고리즘(Prim's Algorithm) 을 정리합니다. 최소 신장 트리(MST…
Graph
8개의 글
최소 스패닝 트리(MST)와 크루스칼 알고리즘
March 16, 2025스패닝 트리 (Spanning Tree…
트리에서의 동적 계획법 (Tree DP)
February 10, 2025트리 DP는 일반 DP와 다르게 계층 구조의 트리 위에서 상태를 전이합니다. 핵심은 DFS…
위상 정렬 (Topological Sort)
January 30, 2025수강신청을 할 때 선수과목을 먼저 들어야 하는 것처럼, 작업들 사이에 선후 관계가 있을 때 올바른 실행 순서를 결정하는 알고리즘이 위상 정렬(Topological Sort) 입니다. 1. 위상 정렬이란? 위상 정렬은 방향 비순환 그래프(DAG…
유니온 파인드(Union-Find) 알고리즘
November 08, 2024유니온 파인드(Union-Find)는 두 노드가 같은 집합에 속하는지 판별하는 그래프 알고리즘입니다. 합집합 찾기 알고리즘이라고도 부르며, 서로 연결되지 않은 노드들의 집합을 다루기 때문에 서로소 집합(Disjoint Set…
플로이드 워셜(Floyd-Warshall) 알고리즘
October 25, 2024플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 한 번에 구하는 알고리즘입니다. 다익스트라가 단일 출발점의 최단 경로를 구하는 것과 달리, 플로이드 워셜은 모든 쌍(Pair…
벨만-포드(Bellman-Ford) 알고리즘
July 06, 2024벨만-포드(Bellman-Ford) 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘입니다. 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있으며, 음수 순환(Negative Cycle…
다익스트라(Dijkstra) 알고리즘
May 05, 2024다익스트라(Dijkstra…