유니온 파인드 알고리즘

유니온-파인드(Union-Find) 알고리즘은 집합(disjoint-set)을 효율적으로 표현하고 관리하는 알고리즘입니다. 주로 여러 개의 원소들이 속한 집합을 표현하고, 두 집합을 합치거나 어떤 원소가 어느 집합에 속해 있는지 판별하는 데 사용됩니다.유니온-파인드 알고리즘은 트리 구조를 사용하여 각 집합을 표현하며, 두 가지 기본 연산인 "합집합(Union)"과 "찾기(Find)"를 지원합니다. 트리 형태로 표현하는 이유는 만약 재귀로 뿌리를 계속 찾다보면 시간이 오래걸린다. 따라서 자신의 뿌리의 가장 상위 뿌리를 자기의 뿌리로 표현하면 시간 복잡도가 줄어들기 때문이다. 우선 코드는 class UnionFind: def __init__(self, n): self.parent = [i ..

• format_list_bulleted 알고리즘
• · 2024. 2. 27.
• textsms

백준 1753번: 최단경로

이 문제도 다익스트라 알고리즘의 정석인 문제이다.각 노드별 최단 거리를 구한 리스트를 리턴하여 print해주면 되기 때문이다.import heapqv, e = map(int, input().split())k = int(input())graph = [[] for _ in range(v + 1)]INF = 1e8distance = [INF] * (v + 1)for i in range(e): start, end, w = map(int, input().split()) graph[start].append((w,end))def dijkstra(k): distance[k] = 0 q = [] heapq.heappush(q, (0,k)) while q: dist,now = ..

• format_list_bulleted 알고리즘/백준
• · 2024. 2. 10.
• textsms

백준 18352번: 특정 거리의 도시 찾기

import heapqN, M, K, X = map(int, input().split())graph = [[] for _ in range(N + 1)]INF = 1e8distance = [INF] * (N + 1)for i in range(M): A, B = map(int, input().split()) graph[A].append((B, 1))def dijkstra(graph, start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now]  🔍 문제 설명N개의 도시와 M개의 도로가 존재하는 방향..

• format_list_bulleted 알고리즘/백준
• · 2024. 2. 10.
• textsms