tree2 LCA (Lowest Common Ancestor) LCA는 이름에서 알 수 있듯이 두 정점 A와 B에서 가장 가까운 공통된 조상을 찾는 알고리즘입니다. 여기에는 2 가지 방법이 있는데요, 하나씩 조상 노드를 살펴보는 방법과 DP를 사용하는 방법이 있습니다. 트리의 depth를 H라고 할 때, 조상 노드를 하나씩 살펴보는 방법으로는 보통 시간복잡도가 O(H)가 나오지만, 최악의 경우 O(N)이 걸릴 수 있습니다. 하지만 DP를 사용하게 된다면? 보통 O(log H)가 걸리지만, 최악의 경우 O(log N)이 걸립니다. DP를 사용하는게 훨씬 빠르죠? 그래서 노드의 개수가 매우 많고, 검사해야할 노드가 매우 많은 경우에 DP를 사용한 방법을 활용하면 빠르게 답을 찾을 수 있습니다! 먼저, 조상 노드를 하나씩 살펴보는 방법은 사실 간단해요. 두 정점 A와 B.. 2021. 4. 1. 인덱스 트리 (Indexed Tree) 구간합을 구하는 트리 종류에는 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있습니다. 그 중에서도 오늘은 인덱스 트리(Indexed Tree) 에 대해 알아보려 합니다. 참고로, 인덱스 트리에 포함되어 있는 종류 중 하나가 세그먼트 트리이기 때문에 세그먼트 트리로 풀 수 있는 문제는 인덱스 트리로 모두 풀 수 있습니다. 인덱스 트리는 A라는 수열에서 구간 S ~ E 가 주어졌을 때, A의 구간 S ~ E 사이의 합을 구하기 위해 사용합니다. 중간 중간 A의 값이 하나씩 바뀔 때마다 그 구간의 합을 구할 때 인덱스 트리를 사용할 수 있습니다. 구현 과정을 보면 다소 복잡해 보일 수 있지만, 그래도 천천히 단계를 밟으면 쉽게 이해할 수 있습니다. 저는 Swift로 구현을 해볼건데요, 마지막에 Java 로 구현.. 2021. 3. 24. 이전 1 다음
