LCA 알고리즘 2

[ BOJ ][JAVA][11437] LCA

www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 3 초 256 MB 10473 4652 2717 43.493% 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에..

[ 개념 ] 54. LCA(Lowest Common Ancestor)

이 포스트는 https://m.blog.naver.com/PostList.nhn?blogId=kks227 의 블로그를 참조하여 따로 공부한 내용을 정리한 글입니다. > 최소 공통 조상(LCA) Lowest Common Ancestor LCA 알고리즘이란 주어진 트리에서 최소 공통 조상을 찾는 알고리즘입니다. 최소 공통 조상 이란 두 정점 u, v에서 가장 가까운 공통 조상입니다. u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드(가까이 있는) 노드이죠. 이런 트리가 있을 때, 4번 정점과 3번 정점의 LCA는 1번 정점입니다. 이때 빨간색으로 칠해진 간선들을 이어보면 두 정점 사이의 최단 경로가 됩니다. 10번 정점과 14번 정점의 LCA는 2번 정점입니다. 3번 정점과 1..