DevLog

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 1 - Union_Find 알고리즘 최소 신장 트리의 이해 1 - 크루스칼 알고리즘 코드 작성 - 1. Path 최소 신장 트리의 이해 1 - 크루스칼 알고리즘 코드 작성 - 2. Union_by_rank union-by-rank 기법 각 트리에 대해 높이(rank)를 기억해 두고, Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임 (즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함) 높이가 h - 1 인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 1 증가시켜주고, 다른 쪽의 트리를 해당 트리에 붙여줌 초기화시, 모든 원소는 높이(rank) 가 0 인 개별 집..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 1 - 신장 트리와 최소 신장 트리 이해 최소 신장 트리의 이해 1 - 크루스칼 알고리즘 (Kruskal's Algorithm) 최소 신장 트리의 이해 1 - Kruskal 알고리즘과 Union_find 알고리즘의 차이 신장 트리 란? Spanning Tree, 또는 신장 트리라고 불림 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 최소 신장 트리 Minimum Spanning Tree, MST 라고 불림 가능한 S..