목록LCA (1)
jade-devlab 님의 블로그
[JAVA] 최소 공통 조상 (Lowest Common Ancestor) 구현하기
1. 최소 공통 조상 : 트리에서 두 노드가 있을 때(u와 v), 둘 다의 노드 중에서 가장 가까운(깊은) 노드를 의미한다-> 공통 부모들 중에서 가장 아래에 있는 노드 구현 방법에는 "단순 구현(단순 상승)", "LCA + DP", "LCA + 세그먼트 트리" 이렇게 3방법이 있다.이 글에서는 단순 상승을 먼저 다뤄볼 예정이다..! 2. 구현 방법 ( 단순 상승 ) BFS(/DFS)탐색을 하면서 각 노드의 부모노드와 깊이를 계산두 노드의 깊이를 비교하여 더 깊은 노드를 올려 두 노드의 깊이를 동일하게 맞춘다두 노드를 동시에 한 칸씩 올리면서 두 노드가 동일해질 때까지 비교한다. 3. 구현 코드package org.bibisam06.tree.template;/* 단순 상승 LCA(Lowest ..
algorithm
2025. 10. 3. 16:05