안녕하세요, 여러분! 이번 포스트에서는 자바스크립트 코딩 테스트에서 자주 출제되는 ‘최소 공통 조상(Least Common Ancestor, LCA)’ 문제에 대해 알아보겠습니다. 이 문제는 트리 구조를 다룰 때 매우 중요한 개념입니다. 우리는 최소 공통 조상을 찾는 알고리즘을 구현하고, 그 과정을 자세히 살펴보겠습니다.
문제 설명
주어진 이진 트리에서 두 개의 노드의 최소 공통 조상을 찾는 문제입니다. 트리는 다음과 같은 규칙을 따릅니다:
- 각 노드는 최대 두 개의 자식을 가질 수 있습니다.
- 주어진 두 노드는 항상 트리에 존재합니다.
입력
- 트리의 루트 노드의 주소 (root)
- 첫 번째 노드의 주소 (node1)
- 두 번째 노드의 주소 (node2)
출력
두 노드의 최소 공통 조상의 노드 값을 출력합니다.
예제
입력:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
node1 = 5, node2 = 1
출력:
3
문제 풀이
문제를 해결하기 위해 여러 접근 방식이 있을 수 있습니다. 그러나 가장 일반적인 접근 방식은 DFS(깊이 우선 탐색)를 사용하는 것입니다. 이 방법은 각 노드를 방문하며 최소 공통 조상을 찾아낼 수 있습니다. 이 과정을 단계별로 자세히 살펴보겠습니다.
1단계: 트리 구조 정의
제일 먼저, 트리를 정의하는 클래스를 만들어야 합니다. 자바스크립트에서 트리 노드는 일반적으로 아래와 같이 정의할 수 있습니다:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null; // 왼쪽 자식
this.right = null; // 오른쪽 자식
}
}
2단계: 트리 생성
트리를 생성하기 위한 예시 코드를 작성해봅니다. 위의 예제와 같은 트리를 생성하는 방법은 다음과 같습니다:
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
3단계: DFS 알고리즘 구현
이제 DFS 알고리즘을 구현해 볼 차례입니다. 최소 공통 조상 찾기 알고리즘은 다음과 같은 과정을 따릅니다:
- 현재 노드가 null이면 null을 반환합니다.
- 현재 노드가 node1 또는 node2와 같으면 현재 노드를 반환합니다.
- 왼쪽과 오른쪽 자식을 재귀적으로 호출하여 각각의 결과를 가져옵니다.
- 왼쪽 및 오른쪽 자식 노드 결과가 모두 null이 아닐 경우 현재 노드가 최소 공통 조상입니다.
- 왼쪽 또는 오른쪽 자식 중 하나만 null인 경우 null이 아닌 자식을 반환합니다.
function lowestCommonAncestor(root, node1, node2) {
if (root === null) return null;
if (root.value === node1.value || root.value === node2.value) return root;
const left = lowestCommonAncestor(root.left, node1, node2);
const right = lowestCommonAncestor(root.right, node1, node2);
if (left && right) return root;
return left ? left : right;
}
4단계: 결과 출력
최소 공통 조상 알고리즘이 완성되었으므로, 이를 테스트해봅시다:
const lca = lowestCommonAncestor(root, root.left, root.right); // node1: 5, node2: 1
console.log(lca.value); // 3
종합 및 정리
이번 포스트에서는 최소 공통 조상(LCA) 문제를 다루어 보았습니다. 트리 구조를 정의하고, DFS를 활용한 알고리즘을 구현한 후, 예제를 통해 결과를 확인하였습니다. 중요한 점은 이 알고리즘이 재귀 호출을 통해 각 노드를 방문하며, 최소 공통 조상을 찾는 과정에서 조건을 구조적으로 구성하는 것입니다.
이와 같은 문제는 다양한 변형 유형이 존재하기 때문에, 여러 유형의 문제를 풀어보며 연습하는 것이 중요합니다. 이후에도 자바스크립트 코딩 테스트에 도움이 되는 다양한 알고리즘을 소개할 예정이니 많은 관심 부탁드립니다!
참고 자료
- GeeksforGeeks – Lowest Common Ancestor in a Binary Tree
- ProgramCreek – LeetCode: Lowest Common Ancestor of a Binary Tree
여러분의 코딩 테스트 준비에 도움이 되길 바랍니다. 감사합니다!