LCA

#1. 문제https://www.acmicpc.net/problem/13511  #2. 풀이 1. 트리 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다.  Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리 자료구조의 각 노드 간 연결 관계는 간선으로 나타내며, 순환 구조를 갖지 않기 때문에 "계층 구조"를 형성합니다. 트리 자료구조의 노드 개수가 N개라면, 간선의 개수는 N-1개입니다.  2. LCA [알고리즘]#7_LCA(Least Common Ancest..

#1. 문제https://www.acmicpc.net/problem/3176  #2. 풀이 1. LCA [알고리즘]#7_LCA(Least Common Ancestor)#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가webddevys.tistory.comLCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. LCA 알고리즘은 Binary Lifting 기법을 활용해 최적화를 수행하며, 일반적으로 두 노드의 공통 조상을 찾거나, 두 노드 사이의 거리 혹은 최단/최대 거리를 찾는데 활용됩니다. 2...

#1. 문제https://www.acmicpc.net/problem/1761  #2. 풀이 1. LCA 알고리즘 [알고리즘]#7_LCA(Least Common Ancestor)#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가webddevys.tistory.comLCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘은 Binary Lifting 기법을 통해 최적화..

#1. 문제 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리는 노드와 간선으로 이루어져 있으며, 노드 간의 연결..

#1. 문제 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리는 노드와 간선으로 이루어져 있으며, 노드 간의 연결 관..

#1. 문제 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 트리는 그래프 자료구조의 한 종류로, 1:N 관계의 계층 구조를 갖는 비 선형 자료구..

#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘을 효율적으로 구현하는 방법으로 Binary Lifting 기법이 있습니다. 2. Binary Lifting 기법  Binary Lifting 기법은 주어진 트리 자료구조에서 두 노드의 LCA를 찾는 방법 중 하나입니다. 특히, Binary Lifting 기법은 깊이가 깊은 트리에서 두 노드의 LCA를 찾는데 효율적입니다. BL의 핵심 개념은 각 노드에 대해 미리 점프할 수 있는 조상 정보를 계산해 ..