파이썬3 크루스칼 알고리즘(Kruskal's algorithm) 1. 신장 트리(Spanning Tree)의 조건 - 주어진 그래프의 모든 노드를 연결해야 한다 - 단, 노드를 연결할 때 사이클이 생겨선 안 된다 2. 최소 신장 트리 MST(Minimum Spanning Tree) - 최소 비용(간선 가중치의 합이 최소)의 Spanning Tree 3. 크루스칼 알고리즘(Kruskal's algorithm) - 간선의 비용을 기준으로 오름차순 정렬하여 비교할 노드를 선정 - 두 노드씩 최상위 노드를 탐색한 후, 서로 다를 경우 노드를 연결하는 알고리즘 - 부모 노드가 서로 다르다는 것은 연결해도 사이클이 발생하지 않는다는 것을 의미함 * 유니온-파인드(Union-Find) 알고리즘 활용 4. 시간 복잡도: O(E log E) def find(node): # path .. 2020. 10. 11. 11650-좌표 정렬하기 (python) - python의 기본 정렬 라이브러리(sorted 등)는 key 설정을 하지 않으면 튜플의 인덱스 순서대로 오름차순 정렬한다 n = int(input()) positions = [] for _ in range(n): data = input().split() positions.append((int(data[0]), int(data[1]))) positions_sorted = sorted(positions) for p in positions_sorted: print(p[0], p[1]) 2020. 10. 11. 10814-나이순 정렬 (python) 1. 내가 작성한 코드 (dictionary 이용) n = int(input()) members = dict() for x in range(1, 201): members[x] = [] for x in range(n): age, name = input().split() members[int(age)].append(name) for k, names in members.items(): for name in names: print(k, name) 2. 1번 통과 후 참고한 코드 (튜플, 기본 정렬 library(sorted) 이용) n = int(input()) array = [] for _ in range(n): input_data = input().split(' ') array.append((int(inpu.. 2020. 10. 11. 이전 1 다음