C# 코딩테스트 강좌, 최소 공통 조상 구하기 1

작성자: 조광형

작성일: [오늘의 날짜]

들어가며

알고리즘 문제풀이에서는 다양한 문제를 해결하는 능력이 중요합니다. 그 중에서도 최소 공통 조상(Lowest Common Ancestor, LCA) 문제는 트리 구조에서의 노드 간의 관계를 이해하는 데 필수적인 개념입니다. 이번 글에서는 C#을 사용하여 최소 공통 조상을 구하는 문제를 풀어보겠습니다.

문제 설명

주어진 이진 트리가 주어졌을 때, 두 노드 A와 B의 최소 공통 조상(LCA)을 찾는 문제입니다. 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 자료구조입니다. LCA는 두 노드 A와 B의 가장 가까운 공통 조상을 의미합니다.

예를 들어 아래와 같은 이진 트리가 있다고 가정해 봅시다.

이 트리에서 노드 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#으로 구현을 통해 문제 해결 능력을 배양할 수 있었기를 바랍니다. 알고리즘 문제풀이에서의 기본 개념을 충분히 이해하고 다양한 상황에 적용해 보는 것이 중요합니다.

앞으로도 다양한 문제를 통해 알고리즘 능력을 향상시키고 코딩 테스트에서 좋은 성과를 내기를 바랍니다.