*'Do it! 알고리즘 코딩 테스트 자바편'을 참고했습니다.직관적이면서 편리한 트리 자료구조는 "배열"인덱스01234567값ABCDEFNoneG트리의 노드와 배열의 인덱스 사이 상관관계이동 목표 노드인덱스 연산제약 조건(N = 노드)root nodeindex = 1 parent nodeindex = index / 2not root nodeleft child nodeindex = index * 2index * 2 right child nodeindex = index * 2 + 1index * 2 + 1 위 인덱스 연산 방식은 segment tree나 LCA(lowest common ancestor) 알고리즘에서도 기본이 되는 연산이므로 숙지해야 한다.

문제링크문제 파악최소 스패닝 트리: 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리사이클을 포함하면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 스패닝 트리를 구성하는 엣지의 개수는 항상 N-1개다.정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000), 가중치는 음수일 수도 있으며 절댓값이 1,000,000을 넘지 않는다.최소 스패닝 트리의 가중치는 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.접근 방법크루스칼 알고리즘: 엣지 리스트 pq(노드1, 노드2, 가중치), 사이클 확인용 UNION-FINDclass Pa..