최소신장트리2 [C++] 백준 1647번: 도시 분할 계획 (최소 신장 트리) https://www.acmicpc.net/problem/1647문제 이해하기 문제의 요구사항은 다음과 같습니다.한 마을을 두 마을로 분리할 때, 두 마을을 유지하는 길의 최소 비용을 구하여라.시간복잡도 어림하기 최소 신장 트리(Minimum Spanning Tree) 그래프의 모든 노드를 최소 비용으로 연결해야 하는 문제이므로 최소 신장 트리를 만드는 문제입니다. 최소 신장 트리는 크루스칼(Kruskal), 프림(Prim) 알고리즘으로 찾을 수 있습니다. 크루스칼 알고리즘은 간선 선택 기반 최소 신장 트리 구성 알고리즘으로 O(eloge)의 시간복잡도를 가지고, 프림 알고리즘은 정점 선택 기반 알고리즘으로 O(n^2)의 시간복잡도를 가집니다. 문제에서 e의 최댓값은 1,000,000이고 n의 최댓값은 .. 2024. 10. 16. [C++] 백준 4386번: 별자리 만들기 (최소 신장 트리) https://www.acmicpc.net/problem/4386문제 이해하기 문제의 요구사항은 다음과 같습니다.모든 별을 잇는 최소 비용을 구하여라.시간복잡도 어림하기최소 신장 트리(Minimum Spanning Tree) 모든 노드(별)을 연결하는 최소 비용을 구하는 문제이므로 최소 비용으로 신장 트리를 구성하는 것과 같습니다. 최소 신장 트리를 구하는 알고리즘으로 Kruskal 알고리즘과 Prim 알고리즘 두 종류가 있습니다. Kruskal 알고리즘의 시간 복잡도는 O(eloge)이고, Prim 알고리즘의 시간 복잡도는 O(n^2) 입니다. 이번 문제에서 n의 최댓값은 100이고, e의 최댓값은 100 x 100 = 10000 이므로 둘 중 어느 알고리즘을 사용해도 해결할 수 있는 문제입니다. 이번.. 2024. 8. 19. 이전 1 다음