목록가장 가까운 공통조상 (1)

Toolofv 님의 블로그

[Python] 백준 - 3584 가장 가까운 공통 조상

백준 - 3584 가장 가까운 공통 조상첫 줄에 테스트 케이스의 개수 T가 주어집니다.각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다.www.acmicpc.net문제루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Ancestor)은 다음과 같이 정의됩니다.두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊..
Algorithm 2024. 9. 2. 00:08
이전 Prev 1 Next 다음