최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식에서 2ᵏ번째 위치의 부모 노드까지 저장해 둬야함 원리 1. 부모 노드 저장 리스트 만들기 부모 노드 리스트 정의 : P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드 번호 내 바로 위에 있는 부모 노드뿐만 아니라, 내 자리에서 2ᵏ 칸 위에 있는 부모가 누군지 저장해놔야함 부모 노드 리스트의 점화식 : P[K][N] = P[K-1][P[k-1][N]] 예시) K = 2 N=12 가정 P[2][12] = P[1][P[1][12]] P[2][12] : 12번 노드의 2²번째 부모 = 1 P[1][12] = 12번 노드의..

➊ 특징 노드와 에지로 연결된 그래프의 특수한 형태 그래프의 표현으로도 트리를 표현할 수 있음 순환구조 X, 1개의 루트노드 루트노드를 제외한 노드는 1개의 부모노드를 가짐 트리의 부분 트리 역시 토리의 모든 특징을 따름 그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트) 간선 리스트 인접 행렬 인접 리스트 중심 간선 노드 노드 시간복잡도 - 느림 빠름 구조 [] d[시작노드][종료노드] d[시작노드] 입력 (시작노드 ,도착노드, 가중치) 가중치 (도착노드, 가중치) 알고리 karla.tistory.com ➋ 트리의 구성요소 구성요소 설명 노드 데이터의 index와 value를 표현하는 요소 에지 노드와 노드의 연결 관계를 나타내는 선 루트 노드 트리에서 가장 상위에 존재하는 노드 부모 노..