유니온 파인드와 크루스칼 알고리즘을 이용한 최소 신장 트리 구현
유니온 파인드 (Disjoint Set Union)
유니온 파인드는 서로소 집합을 효율적으로 관리하기 위한 자료구조입니다. 각 집합을 트리 형태로 표현하며, 트리의 루트 노드가 해당 집합의 대표 원소가 됩니다.
핵심 연산
초기화 (Initialize): 각 원소를 자신을 루트로 하는 독립적인 집합으로 설정합니다.
type DisjointSet struct {
root []int
rank []int
}
fun ...
9월 1일 21:39에 게시됨
최소 신장 트리와 비트 연산을 활용한 그래프 문제 해결
이 문서에서는 최소 신장 트리, 배열의 반복 비교, 그리고 비트 연산 기반 그래프 문제를 다룹니다. 각 문제는 별도의 접근 방식과 알고리즘 구현을 필요로 합니다.
문제 1: 최소 신장 트리
배열 p가 주어졌을 때, 이를 바탕으로 n개의 정점을 가진 완전 무방향 그래프를 생성합니다. 두 정점 i와 j 사이의 간선 가중치는 |pi - pj| × |i - j|로 계산됩니다. 이 그래프 ...
6월 4일 02:15에 게시됨