[백준] 1922 네트워크 연결 | MST (Prim, Kruscal) | Gol4 Pythonhttps://www.acmicpc.net/problem/1922 접근유형 1 : MST - prim (396ms)유형 2 : MST - kruscal (240ms)간선 수가 노드수보다 100배 많은데 prim보다 kruscal 이 더 빠르네 [문제 해석]최소의 비용으로 모든 컴퓨터를 연결하는 경로 구하기= MST 최소 스패닝 트리 구하기1 1 1 간선이 주어질 때 두 노드번호가 같을 수도 있다 MST 프림으로 풀어보자~ 노드선택 구상 - Prim간선 입력받아서 연결된 첫번째 노드별로 (가중치, 노드2) 형태로 리스트에 저장최소힙 사용(정렬유지하며 잦은 삽입 필요)현재 그래프에 포함되어있는 노드 표시하는 배열..
Union Find
[백준] 4195 친구 네트워크 | Union Find, 경로압축 | Gol2 Pythonhttps://www.acmicpc.net/problem/4195 접근유형 : union find (합집합)union find 인데 노드 이름이 문자열인union find 짤 때 모든 연산은 루트노드 기준으로 할 것 기억하기..~! [문제 해석]sns 친구추가(합집합 연산) 시마다 그 새로운 친구 네트워크에 포함된 전체 친구 수 구하기친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말함친구 = 노드, 친구관계 = 간선시간제한 3초친구관계 수 앗.. 사이클이 생길수도 있겠네..? 같은 네트워크면 친구추가 무시해야겠다노드가 친구이름으로 주어지니까 딕셔너리를 쓰자 구상 : 노드이름 문자열에 해당하는 번호를 따로 ..
[백준] 1717 집합의 표현 | Union Find, 경로압축 | Gol5 Pythonhttps://www.acmicpc.net/problem/1717 구상유형 : union find +경로압축둘 다 새롭게 구현해본 개념이라 공부가 많이 됐다!union find만으로는 시간초과가 나서 경로압축 등 find함수를 최적화하여 해결했다.새로운 재미가 있던 문제~ [문제 해셕]0~n 각 하나씩만 원소로 갖는 집합 n+1개가 주어지고, 이들 간의 집합 연산 결과 출력하기0 a b : a와 b가 포함되어있는 집합의 합집합 연산1 a b : a와 b가 같은 집합의 원소인지 확인하는 연산a = b 일 수도 있음1 1 시간제한 : 2초 트러블 슈팅TS 1 : 합집합 연산 시 x,y가 포함된 집합 전체를 연결시켜야하므로..
