# MST

146개의 포스트
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개의 댓글
post-thumbnail

[알고리즘 개념] 최소신장트리(MST)-Kruskal

개념탐욕적인 방법으로 최소신장트리를 구한다순서간선들의 가중치를 오름차순으로 정렬한다정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아 현재의 최소비용 신장트리의 집합에 추가한다실제로 사이클을 알기 위해서는 연결하려는 간선의 양 끝점이 동일한 집합에 없는지를

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

mst 최소스패닝트리

최소신장트리는 '그래프에서 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리'를 뜻한다. MST(minimum spanning tree)의 줄임말이다. 한마디로 모든 정점을 연결하는데 간선의 cost가 최소가 될 때를 찾는 알고리즘이다. 그렇기 때문에 방향

2022년 3월 31일
·
0개의 댓글
post-thumbnail

[알고리즘] Java / 백준 / 전기가 부족해 / 10423

문제문제 링크접근 방식크루스칼 알고리즘으로 사이클이 생기지 않으면서 최소 가중치의 간선을 선택하되 유니온 파인드의 루트를 발전소의 위치로 하여 한 정점이 2개 이상의 발전소와 이어지지 않도록 한다.간선을 연결할 때마다 모든 정점이 발전소와 이어져 있는지 확인하고, 모두

2022년 3월 28일
·
0개의 댓글
post-thumbnail

[알고리즘] Java / 백준 / 최소 스패닝 트리 / 1197

문제문제 링크접근 방식 Kruskal 알고리즘으로 최소 스패닝 트리의 비용을 구한다Kruskal 개념코드

2022년 3월 27일
·
0개의 댓글
post-thumbnail

[알고리즘 개념] 최소신장트리(MST)-Prim

[알고리즘 개념] 최소신장트리(MST)-Prim > 개념 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나간다 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장해나간다 > 인접행렬 그래프의 MST를 구하기 위한 Prim 알...

2022년 3월 27일
·
0개의 댓글
post-thumbnail

스패닝 트리 알고리즘

스패닝 트리(Spanning Tree)란? 그래프 내의 모든 정점을 포함하지만 사이클이 없는 트리로, 신장 트리라고도 한다. 스패닝 트리는 그래프의 최소 연결 부분 그래프이다. 최소 연결은 간선의 수가 가장 적은 것을 의미한다. n개의 정점을 가지는 그

2022년 3월 20일
·
0개의 댓글
post-thumbnail

<Programmers> Greedy_섬 연결하기 + MST, Kruskal Algorithm c++

참고 Kruskal Minimum Spanning Tree Algorithm 모든 간선을 가중치의 오름차순으로 정렬 스패닝 트리에 하나씩 추가 가중치가 작다고 무조건 간선을 트리에 더하는 것이 아니라, 사이클이 생기지 않는 경우에만 트리에 더해준다 상호 배타적 집합

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

백준[2887] 행성 터널 C++ 풀이

MST 알고리즘을 사용할 줄 안다각 x,y,z 별로 sort를 해서 바로 양옆 행성과의 거리를 거리가 작은 순으로 priority queue에 저장한다\-> 왜? : 결국 행성간 거리는 x,y,z간의 거리중 가장 작은 값이다. 각 좌표별로 sort한다면, 바로 옆 행성

2022년 3월 11일
·
0개의 댓글
post-thumbnail

[BOJ] 16202 - MST 게임

https&#x3A;//www.acmicpc.net/problem/16202N개의 정점과 M개의 양방향간선으로 이루어진 단순 그래프 G가 있다. 단순 그래프란, self-loop 간선(한 정점에서 자기 자신을 이어주는 간선)이 없고, 임의의 두 정점 사이 최대 한 개의

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

Graph Algorithm - MST

신장의 의미

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