# MST
최소 신장 트리(MST, Minimum Spanning Tree)
최소 신장 트리(MST, Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm) > 가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘 예) 도시가 여러 개 있을 때 각 도시를 도로로 연결하고자 할 때 비용을 최소화하는 방법
[백준 2887 파이썬] 행성 터널 (플래티넘 5, MST)
모든 간선을 활용할 수 없을 때, MST를 만들어낼 수 있는 간선 집합을 어떤 식으로 추려내야할지 잘 생각해보자.
[BOJ] 14621. 나만 안되는 연애
깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.이 앱은 사용자들을 위해 사심 경로를 제공한다. 이
최소 비용 신장 트리 (MST)
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
백준 #1197 최소 스패닝 트리 (파이썬) : 크루스칼 알고리즘
드디어 최소 스패닝 트리를 배웠다. 이번 글에서는 가장 대중적인 방식인 Kruskal Algorithm을 활용한다.
백준 - 다리 만들기2(feat.python)
https://www.acmicpc.net/problem/17472 문제 요구사항 모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다. 문제 풀이 이 문제를 푸는 로직은 크게 4가지로 나눌 수 있습니다. 1.
.png)
<Baekjoon> #17472_MST, Kruskal, brute force, graph 다리 만들기2 c++
\[최소 비용으로 모든 다리를 연결한다는 점에서 kruskal algorithm 을 떠올린다 각 섬에 번호를 매기고 vec 이라는 이름의 vector를 만들어 {dist, 섬1, 섬2} 를 저장한다. 이는 섬1과 섬2간 거리는 dist라는 뜻이다vec에 저장된 값을 참
[백준] 14621 나만 안되는 연애 JAVA
깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.이 앱은 사용자들을 위해 사심 경로를 제공한다. 이
[1584] Min Cost to Connect All Points | LeetCode Medium
You are given an array points representing integer coordinates of some points on a 2D-plane, where pointsi = xi, yi.The cost of connecting two points
[Data Structure & Algorithm] 최소 신장 트리 & 크루스칼 알고리즘 (shortest path)
최소신장트리(MST)와 크루스칼 알고리즘
[알고리즘] Java / 백준 / 도시 분할 계획 / 1647
문제문제 링크접근 방식최소 스패닝 트리를 구하면서 트리를 구성하는 간선 비용의 합을 구한 후 여기에 간선의 최댓값을 빼면 두 마을을 분리하는 길의 유지비 최솟값을 구할 수 있다.최소 스패닝 트리를 구하는 방법은 kruskal과 prim이 있는데 kruskal은 익숙해서
[백준] 1922번 - 네트워크 연결
도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서
크루스칼(Kruskal) 최소 신장 트리 알고리즘
최소 신장 트리 주어진 가중치 그래프에서 사이클 없이 모든 점을 연결 시킨 트리 중 간선들의 가중치 합이 최소인 트리 크루스칼 알고리즘 가중치가 가장 작은 간선이 사이클을 만들지 않을 때만 'Greedy' 하게 그 간선을 추가시키는 방법 Pseudo Code Kru
