# prim
[Python/Programmers] 42861. 섬 연결하기
n개의 섬 사이에 다리를 건설하는 비용이 주어진다.모든 섬을 연결할 때 필요한 최소 비용을 바노한하라.다리를 여러 번 건너서라도 도달할 수만 있다면 통행 가능한 경우이다. 가령 A섬과 C섬을 잇는 다리가 없더라도 B섬을 거쳐 갈 수 있다면 A섬과 C섬은 서로 통행 가능
ㄴㄴ 내가 더 빠름(feat. MST)
Disjoint sets(서로소 집합) : MST를 위한 기본 지식서로 중복 포함된 원소가 없는 집합들즉, 교집합이 없다.집합에 속한 하나의 특정 멤버(대표자 / representative)를 통해 각 집합들을 구분표현하는 방법연결 리스트트리연산 + Pseudo Cod
우선순위 큐 (Priority Queue)
우선순위 큐 모든 데이터에 우선 순위가 있음 우선순위가 높은 데이터가 먼저 나옴 (선입선출 FIFO가 아님) Dequeue시, 우선순위가 높은 순으로 나감 우선순위가 에는 선입선출 PriorityQueue클래스를 이용하여 우선순위 큐를 구현 우선순위 큐(Priorit
[백준] 1922: 네트워크 연결 - MST, Prim, BST, TreeSet
도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서
[ BOJ / Python ] 4386번 별자리 만들기
이번 문제는 최소스패닝트리 문제였다. 처음 접해보는 알고리즘이었기 때문에 구현 방법을 찾아보고 구현하였다. 처음 접근 할 때에는 찾아보지 않고, permutations를 구하여 그 순서대로 방문하는 가중치 중 최솟값을 구하도록 구현하였다. 답은 잘 도출되었지만, 메모리
[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
[알고리즘] Java / 백준 / 도시 분할 계획 / 1647
문제문제 링크접근 방식최소 스패닝 트리를 구하면서 트리를 구성하는 간선 비용의 합을 구한 후 여기에 간선의 최댓값을 빼면 두 마을을 분리하는 길의 유지비 최솟값을 구할 수 있다.최소 스패닝 트리를 구하는 방법은 kruskal과 prim이 있는데 kruskal은 익숙해서
[알고리즘 개념] 최소신장트리(MST)-Prim
[알고리즘 개념] 최소신장트리(MST)-Prim > 개념 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나간다 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장해나간다 > 인접행렬 그래프의 MST를 구하기 위한 Prim 알...
스패닝 트리 알고리즘
스패닝 트리(Spanning Tree)란? 그래프 내의 모든 정점을 포함하지만 사이클이 없는 트리로, 신장 트리라고도 한다. 스패닝 트리는 그래프의 최소 연결 부분 그래프이다. 최소 연결은 간선의 수가 가장 적은 것을 의미한다. n개의 정점을 가지는 그
[백준] 4386번 : 별자리 만들기(Java)
https://www.acmicpc.net/problem/4386 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으
최소 스패닝 트리 (1) (Minimum Spanning Tree,MST)
1. 개념 > * Spanning Tree(스패닝 트리) 란? * 그래프의 정점 모두와 간선의 부분 집합으로 구성된 부분 그래프이다. 스패닝 트리에 포함된 간선들은 정점들을 트리형태로 모두 연결 해야하며, 트리의 특성 상 사이클이 발생 해서는 안된다. >Minimum
