728x90 LCA 문제 풀이1 BOJ - 3584번, 가장 가까운 공통 조상 [LCA] 이번에 풀이한 문제는 3584번 LCA(Lowest Common Ancestor), 최소 공통 조상 문제입니다. 문제 제목에서 알 수 있듯이, 트리 정보를 입력받은 후에 두 개의 노드의 최소 공통 조상을 찾으면 되는 문제입니다. 최소 공통 조상은 위 그림과 같이 부모 노드로 타고 올라갈 때, 가장 높이가 낮으면서, 두 개의 노드의 공통 조상인 노드입니다. 이러한 유형을 풀어봤던 것 같은데, 각 노드의 부모 노드 정보를 저장한 뒤에 이를 활용해야 한다는 부분까지는 생각이 났는데, 정확한 알고리즘이 생각나지 않아 다른 분들의 풀이를 참고했습니다. 더 효율적인 방법이 있겠지만, 일단 이 문제에 적용할 수 있는 가장 쉬운 풀이는 하나의 노드가 먼저 부모를 거슬러 올라가며, 방문 처리하며 탐색한 뒤에 두 번째 노.. 2023. 1. 17. 이전 1 다음 728x90
