작성자: 조광형
작성일: [오늘의 날짜]
들어가며
알고리즘 문제풀이에서는 다양한 문제를 해결하는 능력이 중요합니다. 그 중에서도 최소 공통 조상(Lowest Common Ancestor, LCA) 문제는 트리 구조에서의 노드 간의 관계를 이해하는 데 필수적인 개념입니다. 이번 글에서는 C#을 사용하여 최소 공통 조상을 구하는 문제를 풀어보겠습니다.
문제 설명
주어진 이진 트리가 주어졌을 때, 두 노드 A와 B의 최소 공통 조상(LCA)을 찾는 문제입니다. 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 자료구조입니다. LCA는 두 노드 A와 B의 가장 가까운 공통 조상을 의미합니다.
예를 들어 아래와 같은 이진 트리가 있다고 가정해 봅시다.
1
/ \
2 3
/ \
4 5
이 트리에서 노드 4와 5의 최소 공통 조상은 2입니다. 노드 2는 4와 5로 가는 경로에서 가장 가까운 조상입니다.
문제 요구 사항
- 이진 트리가 주어질 때, 두 개의 노드의 값을 입력받아 최소 공통 조상을 반환합니다.
- 노드의 값이 주어진 경우, 그 값에 해당하는 노드를 찾아야 합니다.
- 입력으로 주어지는 노드는 이진 트리 내에 항상 존재합니다.
- 시간 복잡도는 O(N)으로 제한됩니다.
접근 방식
이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용할 수 있습니다.
- 트리를 순회하여 각 노드의 부모 노드를 찾아 저장합니다.
- 첫 번째 노드의 조상 경로를 저장한 후, 두 번째 노드의 조상을 위에서부터 체크하며 공통 조상을 찾습니다.
- 이 방법을 통해 O(N)의 시간 복잡도로 두 노드의 최소 공통 조상을 찾을 수 있습니다.
코드 구현
지금부터 C#으로 이진 트리와 최소 공통 조상을 찾는 함수를 구현해 보겠습니다. 먼저 트리를 나타내는 클래스(TreeNode)를 정의하고, 그 위에 LCA를 찾는 메소드를 작성합니다.
using System;
using System.Collections.Generic;
public class TreeNode {
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value) {
Value = value;
Left = Right = null;
}
}
public class BinaryTree {
private TreeNode root;
public BinaryTree(TreeNode root) {
this.root = root;
}
public TreeNode FindLCA(int val1, int val2) {
return FindLCA(root, val1, val2);
}
private TreeNode FindLCA(TreeNode node, int val1, int val2) {
if (node == null) {
return null;
}
if (node.Value == val1 || node.Value == val2) {
return node;
}
TreeNode leftLCA = FindLCA(node.Left, val1, val2);
TreeNode rightLCA = FindLCA(node.Right, val1, val2);
if (leftLCA != null && rightLCA != null) {
return node;
}
return (leftLCA != null) ? leftLCA : rightLCA;
}
}
위 코드는 기본적인 이진 트리 노드를 정의하고, 최소 공통 조상을 찾는 메소드를 구현한 예입니다.
테스트 케이스
이제 코드를 테스트해 보겠습니다. 아래와 같이 이진 트리를 생성하고, LCA를 찾는 로직을 실행해 볼 수 있습니다.
class Program {
static void Main() {
TreeNode root = new TreeNode(1);
root.Left = new TreeNode(2);
root.Right = new TreeNode(3);
root.Left.Left = new TreeNode(4);
root.Left.Right = new TreeNode(5);
BinaryTree tree = new BinaryTree(root);
TreeNode lca = tree.FindLCA(4, 5);
Console.WriteLine($"LCA of 4 and 5 is: {lca.Value}");
lca = tree.FindLCA(4, 3);
Console.WriteLine($"LCA of 4 and 3 is: {lca.Value}");
}
}
이 코드를 실행하면 노드 4와 5의 LCA는 2, 노드 4와 3의 LCA는 1이 출력됩니다. 이는 우리가 예측한 결과와 일치합니다.
결론
이번 글에서는 이진 트리에서 최소 공통 조상을 찾는 방법에 대해 알아보았습니다. C#으로 구현을 통해 문제 해결 능력을 배양할 수 있었기를 바랍니다. 알고리즘 문제풀이에서의 기본 개념을 충분히 이해하고 다양한 상황에 적용해 보는 것이 중요합니다.
앞으로도 다양한 문제를 통해 알고리즘 능력을 향상시키고 코딩 테스트에서 좋은 성과를 내기를 바랍니다.