-
가장 가까운 공통 조상백준알고리즘 2020. 1. 23. 20:09
https://www.acmicpc.net/problem/3584
3584번: 가장 가까운 공통 조상
문제 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운
www.acmicpc.net
조상노드를 찾아가는걸로 풀수있던문제 어렵지 않다.
'백준알고리즘' 카테고리의 다른 글
[BOJ 17244] 아 맞다 우산 (0) 2020.02.03 [BOJ 17825]주사위 윷놀이 (0) 2020.01.26 움직이는 미로 탈출 (0) 2020.01.23 결! 합! (0) 2020.01.17 회의준비 (0) 2019.12.30