Lca 알고리즘 - LCA(Lowest Common Ancestor) 알고리즘
(알고리즘) LCA 알고리즘 + C++ 예제코드
![알고리즘 lca [알고리즘] 최소](http://www.secmem.org/assets/images/fast-LCA/EulerTour1.png "알고리즘 lca [ 개념")
[알고리즘] 최소 공통 조상 LCA 트리
![알고리즘 lca [Algorithm] 최소](https://blog.kakaocdn.net/dn/cpGntv/btqEcmY5rLa/OtQ6NZr56oZbOVuYWRsYuk/img.jpg "알고리즘 lca Crocus")
LCA
![알고리즘 lca [C/C++] 백준](http://www.secmem.org/assets/images/fast-LCA/LCA2.png "알고리즘 lca Tarjan's off")
[알고리즘] 최소 공통 조상
[Algorithm] 최소 공통 조상 LCA (Lowest Common Ancestor)
LCA(Least Common Ancestor)
최소 공통 조상 LCA 란 두 노드가 트리에서 두 노드를 포함하여 조상을 따라 거슬러 올라갈때 처음 공통으로 만나게 되는 정점이다.
나는 Node라는 클래스를 하나 만들어서 거리 d 와 길이 len 을 프로퍼티로 두었고, 시작 노드를 Key로 하고 그 시작 노드에 연결된 노드들의 ArrayList를 Value로 하는 HashMap 자료구조를 아래와 같이 만들어 보았다.
해당 방식 또한 DP와 마찬가지로 O MlogN 의 시간복잡도를 가진다.
- Related articles
2.png?type=w800)
2022 media.readernaut.com