Leta Learns

LCA (Lowest Common Ancestor) 알고리즘 : 최소 공통 조상을 찾는 알고리즘 즉, 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘 Segment Tree를 사용한 방법, DP를 사용한 방법이 존재하는데 DP 사용법에 대해서 공부하였다. 9와 6의 최소 공통 조상 : 2 4와 10의 최소 공통 조상 : 8 2와 15의 최소 공통 조상 : 1 LCA 접근법 최소 공통 조상 찾는 방법 : 각 노드에서 부모를 타고 올라가서 같은 부모를 찾는다. 이때, 양 노드의 레벨이 같아야 함. => 각 노드의 부모와 레벨을 알아야 하고, 트리가 있어야 함 각 노드의 부모 노드, 레벨 저장하는 법 => DFS 사용 재귀를 한 번씩 돌 때 마다 레벨 += 1, 부모 노드 또한 저장 가능. ex) 6과 1..