# MST

156개의 포스트
post-thumbnail

최소 신장 트리(MST, Minimum Spanning Tree)

최소 신장 트리(MST, Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm) > 가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘 예) 도시가 여러 개 있을 때 각 도시를 도로로 연결하고자 할 때 비용을 최소화하는 방법

7일 전
·
0개의 댓글
·

[백준 17472 파이썬] 다리 만들기 2 (골드 1, MST)

크루스칼 MST 문제인데 고려해야 할 사항이 많아 복잡함

2022년 8월 3일
·
0개의 댓글
·

[백준 2887 파이썬] 행성 터널 (플래티넘 5, MST)

모든 간선을 활용할 수 없을 때, MST를 만들어낼 수 있는 간선 집합을 어떤 식으로 추려내야할지 잘 생각해보자.

2022년 8월 2일
·
0개의 댓글
·
post-thumbnail

[BOJ] 14621. 나만 안되는 연애

깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.이 앱은 사용자들을 위해 사심 경로를 제공한다. 이

2022년 7월 27일
·
0개의 댓글
·

[백준 4386 파이썬] 별자리 만들기 (골드 4, MST)

크루스칼 MST (딕셔너리를 사용한 weighted union find 활용)

2022년 7월 20일
·
0개의 댓글
·

[백준 1197 파이썬] 최소 스패닝 트리 (골드 4, MST)

연결 그래프에서 MST를 찾는 두 가지 알고리즘, 크루스칼과 프림

2022년 7월 19일
·
0개의 댓글
·

1197_최소 스패닝 트리

1197_최소 스패닝 트리

2022년 7월 14일
·
0개의 댓글
·

최소 비용 신장 트리 (MST)

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

2022년 7월 14일
·
0개의 댓글
·
post-thumbnail

백준 #1197 최소 스패닝 트리 (파이썬) : 크루스칼 알고리즘

드디어 최소 스패닝 트리를 배웠다. 이번 글에서는 가장 대중적인 방식인 Kruskal Algorithm을 활용한다.

2022년 6월 25일
·
0개의 댓글
·

백준 - 다리 만들기2(feat.python)

https://www.acmicpc.net/problem/17472 문제 요구사항 모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다. 문제 풀이 이 문제를 푸는 로직은 크게 4가지로 나눌 수 있습니다. 1.

2022년 5월 13일
·
4개의 댓글
·
post-thumbnail

<Baekjoon> #17472_MST, Kruskal, brute force, graph 다리 만들기2 c++

\[최소 비용으로 모든 다리를 연결한다는 점에서 kruskal algorithm 을 떠올린다 각 섬에 번호를 매기고 vec 이라는 이름의 vector를 만들어 {dist, 섬1, 섬2} 를 저장한다. 이는 섬1과 섬2간 거리는 dist라는 뜻이다vec에 저장된 값을 참

2022년 5월 12일
·
0개의 댓글
·

[백준] 14621 나만 안되는 연애 JAVA

깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.이 앱은 사용자들을 위해 사심 경로를 제공한다. 이

2022년 5월 12일
·
0개의 댓글
·
post-thumbnail

[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

2022년 4월 26일
·
0개의 댓글
·
post-thumbnail

[알고리즘] Java / 백준 / 도시 분할 계획 / 1647

문제문제 링크접근 방식최소 스패닝 트리를 구하면서 트리를 구성하는 간선 비용의 합을 구한 후 여기에 간선의 최댓값을 빼면 두 마을을 분리하는 길의 유지비 최솟값을 구할 수 있다.최소 스패닝 트리를 구하는 방법은 kruskal과 prim이 있는데 kruskal은 익숙해서

2022년 4월 16일
·
0개의 댓글
·
post-thumbnail

[백준] 1922번 - 네트워크 연결

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서

2022년 4월 12일
·
0개의 댓글
·
post-thumbnail

크루스칼(Kruskal) 최소 신장 트리 알고리즘

최소 신장 트리 주어진 가중치 그래프에서 사이클 없이 모든 점을 연결 시킨 트리 중 간선들의 가중치 합이 최소인 트리 크루스칼 알고리즘 가중치가 가장 작은 간선이 사이클을 만들지 않을 때만 'Greedy' 하게 그 간선을 추가시키는 방법 Pseudo Code Kru

2022년 4월 10일
·
0개의 댓글
·
post-thumbnail

[알고리즘] 최소 신장 트리(MST)

신장트리, 최소 신장 트리, kruskal, prim

2022년 4월 5일
·
0개의 댓글
·