Leta Learns

문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 크루스칼 사랑해. 이제 크루스칼은 문제 이해만 잘 하면 나름 수월하게 풀 수 있다. 근데 그 문제 이해가 오래 걸린다.. 이걸 어떻게 크루스칼로 풀어야 하는지, 이게 왜 크루스칼인지.. 뭐 풀다보면 익숙해지겠지..? import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a..

문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 스터디할 때는 크루스칼 어려웠는데 지금은 할 만하다. 문제 해결에 필요한 로직대로만 조금 수정하고 find, union 함수 사용하면 돼서 금방 익숙해진 것 같다. MST 어려워서 겁먹었었는데 이제는 좀 더 마음 놓고 시도해도 될 것 같다. import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = ..

크루스칼 공부할 때 코드 외운다고 해놓고 안 외웠더니 오늘도 고생 좀 했다.. 그래도 크루스칼은 find, union함수만 외우면 나름 금방 풀리는 것 같다. 이번 문제는 테스트 케이스가 여러 개 주어지는 경우가 있다는 것을 캐치하는데 오래 걸렸다. 마지막 입력값에 0 0 을 왜 하나 싶었는데 다 그래서였구나....... import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = find(parent[a]) return parent[a] def union(a, b): a = find(a) b = find(b) if a > b: parent[a] = b else: parent[b] = a while Tr..

문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이번 주 MST 스터디에서 1197번은 프림으로, 1922번은 크루스칼로 풀 생각이었는데 보통 문제 풀 때는 거의 다 크루스칼로 푸니까 둘 다 크루스칼로 풀기로 스터디원이랑 협의했다. 그랬더니.. 1197번이랑 입력 부분 빼고 코드가 전부 똑같다. 이번 주는 크루스칼에 익숙해지는 주간.. import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = find(parent[a]) re..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 처음에 Prim으로 풀었는데 예제만 맞고 또 일반화에 실패했다. ㅋㅋ 찾아보니까 Prim은 우선순위큐를 쓰더라고.. 복잡하길래 그냥 Kruskal로 풀었다. 유니온 파인드 공부해놨더니 별로 안 어려워서 풀만 했다. import sys input = sys.stdin.readline def find(a): if a == parent[a]: retu..

Kruskal Algorithm : 그리디 방법을 사용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 간선 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리와 무관하게 무조건 최소 비용 간선 선택 Kruskal 알고리즘 과정 그래프의 간선들을 가중치를 기준으로 오름차순 정렬 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택 -> 최소 가중치 먼저 선택, 사이클 형성하는 간선은 제외 해당 간선을 현재의 MST 집합에 추가 Kruskal 알고리즘 예 주의할 점 ! 간선을 선택할 때 사이클을 생성하는지 확인 => 추가할 간선의 양 정점이 같은 집합에 속하면 안 된다. 사이클 생성 여부 확인 방법 :..

Spanning Tree (신장 트리) : 그래프의 최소 연결 부분 그래프. 최소 연결 -> 간선의 수가 최소 n개의 정점을 가지는 그래프의 최소 간선의 수: n-1 n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. => ST 즉, 그래프에서 일부 간선을 선택해서 만든 트리. Spanning Tree의 특징 하나의 그래프에는 여러 개의 신장 트리가 존재 가능. ST는 트리의 특수 형태 => 모든 정점들 연결 => 사이클 포함 x => N개의 정점을 정확히 n-1개의 간선으로 연결 Minimum Spanning Tree (최소 신장 트리) : Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 상이할 때 단순히 간선 수를 가장 적게 사용한다고 해서 ..