최소 신장 트리(MST)2 [Programmers] 섬 연결하기 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문제에서 요구하는 결과값이 최소 신장 트리(minimum spanning tree)의 간선의 가중치의 총합이므로, 최소 신장 트리 알고리즘을 활용하여 문제를 해결하고자 하였다. 구현 간선 데이터가 주어지므로, 유니온-파인드(union-find) 연산을 구현한 다음 크루스칼 알고리즘(Kruskal's algorithm)을 통해 최소 신장 트리를 만들어 가중치의 총합을 구하였다... 2023. 12. 11. [Baekjoon] 1197번: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해결 과정 착안 최소 (비용) 신장 트리(minimum spanning tree, MST)를 구하는 문제이므로, 이를 구하는 대표적인 알고리즘을 이용하여 문제를 해결하고자 하였다. 문제에서 한 줄씩 간선 데이터를 입력으로 제공하기 때문에, 간선 데이터를 하나씩 저장하면서 정렬하는 것이 문제 해결에 편리할 것 같아서 크루스칼 알고리즘(Kruskal.. 2023. 5. 31. 이전 1 다음
