안녕하세요, 코딩테스트 준비생 여러분! 오늘은 최소 공통 조상(LCA, Lowest Common Ancestor) 문제에 대해 깊이 있게 알아보겠습니다. 이 문제는 트리 구조와 관련이 있으며, 알고리즘 및 데이터 구조에 대한 깊은 이해를 요구합니다. 우리는 이 문제를 다루면서 C#으로 해결하는 방법도 함께 살펴보겠습니다.
문제 정의
주어진 이진 트리에서 두 노드의 최소 공통 조상을 찾는 문제입니다. 두 노드 A와 B가 주어졌을 때, 이 두 노드의 조상이 되는 노드 중 가장 깊이 있는 노드를 찾는 것이 우리의 목표입니다.
예제
예를 들어, 다음과 같은 이진 트리가 존재한다고 가정해 보겠습니다.
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
노드 5와 노드 1의 최소 공통 조상은 3입니다.
노드 5와 노드 2의 최소 공통 조상은 5입니다.
노드 6와 노드 4의 최소 공통 조상은 5입니다.
문제 접근 방법
-
트리 구조 이해
우선, 이진 트리의 구조를 이해해야 합니다. 각 노드는 최대 두 개의 자식을 가지며, 왼쪽 서브트리와 오른쪽 서브트리로 나누어질 수 있습니다. 노드를 찾기 위해 트리를 탐색하는 방법을 알고 있어야 합니다.
-
재귀적 접근
주요 접근 방식 중 하나는 재귀적으로 탐색하는 것입니다. 만약 현재 노드가 A 또는 B 중 하나라면, 현재 노드를 반환하고, 왼쪽과 오른쪽 서브트리를 탐색하여 나머지 노드를 찾습니다. 둘 다 발견하면 현재 노드가 최소 공통 조상입니다.
-
트리 탐색 알고리즘 작성
이제 알고리즘을 구현하기 위해 C#으로 코드를 작성해야 합니다. 이 과정에서 재귀를 사용하여 노드를 탐색하고 확인하는 방법을 코드에 녹아내릴 것입니다.
C# 코드 구현
// 이진 트리 노드 클래스 정의
public class TreeNode {
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value) {
Value = value;
Left = null;
Right = null;
}
}
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 기저 사례: root가 null이거나 p 또는 q일 경우, root를 반환
if (root == null || root == p || root == q) {
return root;
}
// 왼쪽과 오른쪽 서브트리에서 각 노드를 탐색
TreeNode left = LowestCommonAncestor(root.Left, p, q);
TreeNode right = LowestCommonAncestor(root.Right, p, q);
// p와 q가 각각 다른 서브트리에 있을 경우 현재 노드가 LCA
if (left != null && right != null) {
return root;
}
// 둘 중 하나만 발견된 경우 해당 노드를 반환
return left ?? right;
}
}
코드 설명
이 코드는 주어진 이진 트리에서 두 노드의 최소 공통 조상을 찾기 위해 작성되었습니다. 다음은 코드의 주요 부분 설명입니다:
-
TreeNode 클래스
이 클래스는 트리의 각 노드를 나타냅니다. 각 노드의 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 저장합니다.
-
LowestCommonAncestor 메서드
이 메서드는 재귀적으로 호출되며, 현재 노드가 null인 경우와 p 또는 q인 경우를 확인합니다. 왼쪽과 오른쪽 서브트리에서 각각 p와 q를 찾고, 두 서브트리에서 둘 다 발견되면 현재 노드를 반환합니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 O(N)입니다. N은 트리의 노드 수이며, 모든 노드를 탐색해야 하므로 비례합니다. 공간 복잡도는 O(H)로, H는 트리의 높이를 나타냅니다. 이는 재귀 호출 스택의 깊이에 해당합니다.
예제 실행
// 트리 예시 생성 및 LCA 찾기
TreeNode 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);
Solution solution = new Solution();
TreeNode p = root.Left; // 노드 5
TreeNode q = root.Left.Right; // 노드 2
TreeNode lca = solution.LowestCommonAncestor(root, p, q);
Console.WriteLine($"최소 공통 조상: {lca.Value}"); // 5 출력
마무리
오늘은 C#을 사용하여 최소 공통 조상 문제를 해결하는 방법에 대해 알아보았습니다. 이 문제는 다양한 알고리즘 문제들을 풀기 위한 기초가 되며, 트리 구조와 재귀적 사고를 요구합니다. 연습을 통해 여러분의 코딩 실력을 향상시키고, 이번 기회에 C#에 대한 이해도를 높일 수 있기를 바랍니다.