Coding Test/Tree

최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과)

최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 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번 노드의..

세그먼트 트리, 인덱스 트리, 구간합

1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 모든 값을 update 해야함 ➔ 느림 데이터의 업데이트가 빈번하게 일어나게 되면 합배열 성능 측면에서 안좋음 ➔ 속도유지를 위해 세그먼트 트리 사용 2. 원리 1) 트리 초기화 하기 ⓪ 샘플데이터 {5, 8, 4, 3, 7, 2, 1, 6} ① 리스트 길이 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듬 2ᵏ≥ N을 만족하는 𝑘의 최솟값을 구한 후 2ᵏ * 2 N=8이므로 2³ ≥ 8 ➔ 2³ * 2 = 16 ② 시작 노드 : 2ᵏ ➔ 2³ = 8 ③ 리프 노드에 원본 ..

트리 (구성 요소, 이진 트리, 세그먼트 트리, 인덱스 트리, 최소공통 조상 LCA)

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