S E P H ' S

최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor)는 주어진 두 노드 a, b의 최소 공통 조상을 찾는 알고리즘이다. 예를 들어 아래의 트리에서 5번과 6번의 최소 공통 조상 LCA는 2번 노드이다. 일반적인 LCA 풀이방법 1번 루트노드를 기준으로 DFS 탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장한다. LCA 를 구하기 위한 a, b 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다. (a의 높이 == b의 높이) 높이가 맞춰졌으면 각 부모 노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1) LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게 되면 엄청 많은 반복을 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 키포인트는 이진 트리를 이해하고 응용할 수 있는지와 트리의 성질을 이용해 답을 도출해나갈 수 있는지 두 가지로 보았다. 트리의 성질을 더욱 잘 이해하고 있어야 하는 이유가 있는 문제였다. 트리를 활용한 기본 문제들은 입력에서 자식 노드의 인덱스들을 parentIdx * 2 (왼쪽 자식 인덱스), parentIdx * 2 + 1 (오른쪽 자식 인덱스) 그대로를 주는 문제들이 대부분이었다. 다시 말하자면 부모 인덱스가 무조건 자식 인덱스보다 작았었다. 하지만 이 문제의 입력값을 보자면 부모 인덱스가 자식 인덱스보다 값이 큰 경우도 확인해볼 수 있다. 그래서 ..