# MST
MST와 최단경로 정리
최소신장트리 : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치들의 합이 최소인 신장 트리정점의 개수가 N일때 N(N-1)/4 -> N^2/4를 기준으로 간선이 많다 적다를 판단한다간선이 적으면 Kruskal간선이 많으면 Prim간선중심으로 최소신장트리를
[백준] 1197번 : 최소 스패닝 트리
최소 스패닝 트리우선 기본 지식을 알아 보겠다.원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 함.(간선들이 사이클을 이루지 않아야 함.)주어진 그래프의 모든 정점들을 연결하는 부분 그
백준 14621 '나만 안되는 연애'
문제의 2번, 3번 특징에서 MST 문제임을 알 수 있다.문제의 1번에서, 남초-남초 간선과 여초-여초 간선은 제외해야함을 알 수 있다.MST를 구하기 위해 Kruskal 알고리즘을 사용했다.$N \\le 1\\ 000$이므로 Prim을 써도 상관 없을 것이다.간선 개
백준 1922 '네트워크 연결'
모든 컴퓨터를 연결하는 데 최소 비용이 들도록 한다. → 최소 스패닝 트리 문제Prim 알고리즘의 시간복잡도는 $O(V^2)$ 또는 $O((V+E)\\lg V)$로, 우선순위 큐를 사용하면 풀이가 가능하다.Kruskal 알고리즘의 시간복잡도는 $O(E \\lg E)$로
백준 2887 '행성 터널' (풀이중)
N개의 행성을 모두 연결하는 Full graph로 풀 수 있을까?N ≤ 100,000, E = N(N-1)/2 이므로 어림도 없다.간선의 수를 줄여야 함백트래킹으로 유망성을 검사해서 미리 간선을 쳐낸다.메모리:시간:리뷰
백준 4386 '별자리 만들기'
n개 정점의 완전 그래프에 대한 MST간선의 가중치는 두 행성 간의 거리n이 작고 간선 수는 많으므로 PriorityQueue를 쓰지 않는 Prim 알고리즘을 사용해봄메모리: 14120 KB시간: 128 msn이 작을 때는 PQ를 안 쓰는게 더 빠를 수 있다.
백준 1197 '최소 스패닝 트리'
ㅈㄱㄴE가 V에 비해 크지 않으므로 Kruskal로 ㄱmake랑 union은 굳이 메소드 안 만들었습니다.나름 최적화한답시고 경로압축이랑 큰 번호쪽이 루트가 되도록?메모리: 49608 KB시간: 628 ms기본기는 확실히
[알고리즘] Greedy & DP & MST
그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘임동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법그렇게 각 단계에서 최선의 선택을
[알고리즘 이론] 최소 신장 트리 _ MST
그래프에서 최소 비용 문제를 해결하기 위한 트리 1\. 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리 2\. 두 정점 사이의 최소 비용 경로 찾기❓ 여기서 신장 트리란? : V개의 정점으로 이루어진 무향그래프에서 V개의 정점과 V-1개의 간선으로
[백준] 23034번: 조별과제 멈춰!
문제 바로가기교수님이 시험기간에 조별과제를 내셔서 조교가 조를 나눈다는 내용이다... 문제 내용은 다음과 같다.N명의 학생을 각각 1명 이상이 포함된 두개의 조로 나눈다.각 조의 팀장에게 공지를 할 때, 팀장에서부터 회선으로 퍼져나가 모든 학생이 공지를 들을 때 까지
문제 풀이(8)
https://www.acmicpc.net/problem/4386먼저 점의 개수 n을 입력 받고, n개의 좌표를 입력 받아서 nodes 배열에 저장한다.입력 받은 좌표들 간의 거리를 계산하여 모든 가능한 간선을 우선순위 큐(pq)에 저장한다. 이때 거리가 짧은
[Python] 백준 1197번 최소 스패닝 트리 (최소 스패닝 트리)
BOJ 1197번 \[최소 스패닝 트리]그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.첫째 줄에 정점의 개수 V
