Leta Learns

크루스칼 공부할 때 코드 외운다고 해놓고 안 외웠더니 오늘도 고생 좀 했다.. 그래도 크루스칼은 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 알고리즘 예 주의할 점 ! 간선을 선택할 때 사이클을 생성하는지 확인 => 추가할 간선의 양 정점이 같은 집합에 속하면 안 된다. 사이클 생성 여부 확인 방법 :..

Prim 알고리즘 대표적인 최소신장트리 알고리즘 ex) Prim, Kruskal 알고리즘 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장하는 방법 정점 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리를 확장하는 방법 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 가중치로 연결된 정점을 선택. 해당 정점에서 다시 최소 가중치로 연결된 정점을 선택. => 그리디 알고리즘 Prim 알고리즘 예 임의의 정점을 선택. 연결된 노드 집합에 삽입. 현재 정점에 연결된 간선들을 간선 리스트에 삽입 간선 리스트에서 최소가중치를 가지는 간선 추출 추출한 간선은 간선 리스트에서 삭제 간선 리스트에 더 이상 간선이 없을 때 까지 3,4번 반복 3번 과정에서, if 해당 간선에 연결된 정점이..

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