MST

[알고리즘] 3124. 최소 스패팅 트리

작성자:
Featured image for [알고리즘] 3124. 최소 스패팅 트리

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 MST를 구하는 문제다. 주어지는 가중치가 크기 때문에 overflow를 주의하면서 풀면 된다. 가. Kruskal 나. Prim – PQ

[알고리즘] 1251. 하나로

작성자:
Featured image for [알고리즘] 1251. 하나로

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

[Java] 최소 신장 트리

작성자:
Featured image for [Java] 최소 신장 트리

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