최소 신장 트리 – 피곤한아이의 개발 블로그

[알고리즘] 1251. 하나로

2026년 02월 04일2024년 02월 26일 작성자: 피곤한아이

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 이 문제는 모든 노드가 서로 연결될 수 있는 완전 그래프다. 따라서 많은 간선이 생길 수 있다. (E의 최대 개수 = (V(V-1))/2)) 밀집 그래프에서 유리한 반복문으로 구현한 Prim 알고리즘으로 문제를 풀어본다. But! PQ로 구현한 Prim 알고리즘으로 … 더 읽기

[Java] 최소 신장 트리

2026년 02월 04일2024년 02월 25일 작성자: 피곤한아이

1. 최소 신장 트리 (MST) 알고리즘 방식 시간 복잡도 유리한 상황 자료구조 Kruskal 일반적 O(ElogE + V) 간선이 많지 않은 그래프 간선 리스트 Prim (PQ 구현) 우선순위 큐(PQ) 사용 O(ElogV) 또는 O(ElogE) 간선이 많지 않은 그래프 인접 행렬, 인접 리스트 Prim (반복문 구현) 반복문 사용 O(V^2) 간선이 많은 밀집 그래프 인접 행렬, 인접 리스트 (E … 더 읽기