공부한 내용 기록하기 공부한 내용 기록하기

1. 프림 알고리즘이란?프림 알고리즘(Prim's Algorithm)은 최소 신장 트리(MST: Minimum Spanning Tree)를 구하는 알고리즘 중 하나로, 정점을 중심으로 트리를 확장하는 방식으로 동작한다. 시작 정점에서 출발하여 가장 가중치가 낮은 간선을 선택하며 트리를 확장해 나간다.1.1 프림 알고리즘의 특징탐욕적 접근법(Greedy Approach) 기반무방향 가중 그래프에서 사용정점을 중심으로 최소 비용 간선을 선택해 트리를 확장시간 복잡도: O((V + E) log V) (V는 정점 수, E는 간선 수)2. 프림 알고리즘의 동작 원리프림 알고리즘은 다음과 같은 단계로 수행된다:초기화:시작 정점을 선택하고 해당 정점에서 연결된 간선 중 가장 작은 가중치의 간선을 선택최소 비용 트리에..

1. 크루스칼 알고리즘이란?크루스칼 알고리즘(Kruskal's Algorithm)은 최소 신장 트리(MST: Minimum Spanning Tree)를 구하는 대표적인 알고리즘 중 하나이다. 그래프에서 모든 정점을 최소 비용으로 연결하는 트리를 생성하는 데 사용된다.이 알고리즘은 간선을 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 가장 작은 가중치를 가진 간선을 선택하는 방식으로 동작한다. 유니온-파인드(Union-Find) 자료구조를 활용해 사이클 발생 여부를 효율적으로 판별한다.1.1 크루스칼 알고리즘의 특징탐욕적 접근법(Greedy Approach) 기반무방향 가중 그래프에서 사용사이클 방지를 위해 유니온-파인드 사용시간 복잡도: O(E log E) (E는 간선 수)2. 크루스칼 알고리즘..