LCA
-
[Algorithm] - LCA ( 최소 공통 조상 )Algorithm/Algorithm 2022. 9. 15. 00:46
LCA ( Lowest Common Ancestor ) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 아래 그림에서 노드 13번과 15번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 5번 노드가 공통 조상이다. 아래 그림에서 노드 13번과 11번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 1번 노드가 공통 조상이다. 알고리즘 1. a,b 노드의 깊이를 파악한다. 2. 깊이가 동일하다면 상위 노드를 찾아가면서 동일한 노드가 나올 때까지 추적 그렇다면 노드의 깊이를 어떻게 파악할 것인가? DFS로 root 노드로 부터 깊이를 미리 구해둔다. 또한, 깊이를 구하면서 자신의 부모 노드를 기억하여 두고 부모 노드로 추적할 수 있게끔 할 수 있어야한다. ..
-
[BOJ] - 11437번Algorithm/BOJ 2022. 9. 15. 00:46
문제 [BOJ] - 11437번 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 이해 더보기 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트..