# prim

38개의 포스트

[Algorithm] MST

MST 최소신장트리 Kruskal, Prim

2023년 4월 24일
·
0개의 댓글
·

[Python/Programmers] 42861. 섬 연결하기

n개의 섬 사이에 다리를 건설하는 비용이 주어진다.모든 섬을 연결할 때 필요한 최소 비용을 바노한하라.다리를 여러 번 건너서라도 도달할 수만 있다면 통행 가능한 경우이다. 가령 A섬과 C섬을 잇는 다리가 없더라도 B섬을 거쳐 갈 수 있다면 A섬과 C섬은 서로 통행 가능

2023년 4월 3일
·
1개의 댓글
·
post-thumbnail

ㄴㄴ 내가 더 빠름(feat. MST)

Disjoint sets(서로소 집합) : MST를 위한 기본 지식서로 중복 포함된 원소가 없는 집합들즉, 교집합이 없다.집합에 속한 하나의 특정 멤버(대표자 / representative)를 통해 각 집합들을 구분표현하는 방법연결 리스트트리연산 + Pseudo Cod

2023년 3월 30일
·
0개의 댓글
·
post-thumbnail

프림(prim) 알고리즘

프림 알고리즘을 알아보자

2023년 3월 26일
·
0개의 댓글
·
post-thumbnail

우선순위 큐 (Priority Queue)

우선순위 큐 모든 데이터에 우선 순위가 있음 우선순위가 높은 데이터가 먼저 나옴 (선입선출 FIFO가 아님) Dequeue시, 우선순위가 높은 순으로 나감 우선순위가 에는 선입선출 PriorityQueue클래스를 이용하여 우선순위 큐를 구현 우선순위 큐(Priorit

2023년 3월 25일
·
0개의 댓글
·
post-thumbnail

[백준] 1922: 네트워크 연결 - MST, Prim, BST, TreeSet

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

2023년 2월 22일
·
0개의 댓글
·
post-thumbnail

BOJ 16398 : 행성 연결

BOJ 16398 : 행성 연결

2023년 2월 10일
·
0개의 댓글
·
post-thumbnail

[ BOJ / Python ] 4386번 별자리 만들기

이번 문제는 최소스패닝트리 문제였다. 처음 접해보는 알고리즘이었기 때문에 구현 방법을 찾아보고 구현하였다. 처음 접근 할 때에는 찾아보지 않고, permutations를 구하여 그 순서대로 방문하는 가중치 중 최솟값을 구하도록 구현하였다. 답은 잘 도출되었지만, 메모리

2022년 7월 6일
·
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

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

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

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

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

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

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

스패닝 트리 알고리즘

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

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

[백준] 4386번 : 별자리 만들기(Java)

https://www.acmicpc.net/problem/4386 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으

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

최소 스패닝 트리 (1) (Minimum Spanning Tree,MST)

1. 개념 > * Spanning Tree(스패닝 트리) 란? * 그래프의 정점 모두와 간선의 부분 집합으로 구성된 부분 그래프이다. 스패닝 트리에 포함된 간선들은 정점들을 트리형태로 모두 연결 해야하며, 트리의 특성 상 사이클이 발생 해서는 안된다. >Minimum

2022년 1월 15일
·
0개의 댓글
·
post-thumbnail

Prim's Algorithm과 증명

Prim's Algorithm은 그래프에서 MST(최소신장트리)를 찾는 알고리즘이다.

2022년 1월 10일
·
0개의 댓글
·

[BOJ 1647] 도시 분할 계획 (Java)

가장 작은 유지비를 갖는 도로들을 구하고, 이를 분할해 봅시다!

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

최소 신장(스패닝) 트리(minimum spanning tree)

최소 스패닝 트리를 해결하는 방법, Kruskal 과 Prim 알고리즘

2021년 10월 19일
·
0개의 댓글
·
post-thumbnail

최소 신장 트리(MST)

모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리

2021년 10월 5일
·
0개의 댓글
·