[카테고리:] C# 코딩테스트 강좌

소개

본 강좌에서는 C# 프로그래밍 언어를 사용하여 ‘최소 공통 조상(LCA; Lowest Common Ancestor)’ 문제를 해결하는 방법에 대해 다룰 것입니다.
최소 공통 조상은 이진 트리에서 두 노드의 공통 조상 중 가장 깊은 노드를 의미합니다.
특정 알고리즘 및 자료 구조를 활용하여 이 문제를 해결하는 과정을 자세히 설명하겠습니다.

문제 설명

주어진 이진 트리와 두 개의 노드 A, B에 대해, A와 B의 최소 공통 조상을 찾는 문제입니다.
이진 트리는 비어있지 않으며, 모든 노드는 고유한 값을 갖습니다.
추가적으로 노드 A와 B는 반드시 트리에 존재한다고 가정합니다.

입력 형식

                - 첫 번째 줄: 트리의 노드 수 N (1 ≤ N ≤ 10^5)
                - 두 번째 줄: N개의 공백으로 구분된 정수로 트리의 노드 값
                - 세 번째 줄: 두 개의 정수 A, B (A, B는 트리의 노드에 존재)
            

출력 형식

                - A와 B의 최소 공통 조상의 값
            

문제 예시

                입력:
                7
                3 5 1 6 2 0 8
                5 1

                출력:
                3
            

해결 방법

최소 공통 조상을 찾기 위한 여러 방법이 있지만, 일반적으로 트리의 깊이를 고려하면서
DFS(Depth First Search) 방식으로 탐색하는 방법이 효과적입니다.
이진 탐색 트리(BST)의 경우에는 A와 B가 각각 어느 서브트리에 속하는지를 판단하여
조상을 효율적으로 찾는 방법이 가능합니다. 하지만 일반적인 이진 트리에서는 부모 노드의 정보를 활용하는
방식이 필요합니다.

알고리즘 설계

알고리즘의 주요 단계는 다음과 같습니다.

1. 입력으로 주어진 트리를 생성합니다.
2. 각 노드에 대한 부모 노드를 맵 또는 배열로 저장합니다.
3. 노드 A에서 루트까지의 경로를 기록합니다.
4. 노드 B에서 루트까지의 경로를 기록합니다.
5. 두 경로에서 첫 번째 공통 노드를 찾습니다.

C# 코드 구현

아래는 위의 알고리즘을 C#으로 구현한 코드입니다.

                
using System;
using System.Collections.Generic;

class TreeNode {
    public int Value;
    public TreeNode Left, Right;
    
    public TreeNode(int value) {
        this.Value = value;
        this.Left = null;
        this.Right = null;
    }
}

class Program {
    static Dictionary nodeMap = new Dictionary();
    static TreeNode root;

    public static void Main(string[] args) {
        int N = Convert.ToInt32(Console.ReadLine());
        int[] values = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int A = Convert.ToInt32(Console.ReadLine());
        int B = Convert.ToInt32(Console.ReadLine());

        BuildTree(values, 0, N);
        TreeNode ancestor = FindLCA(root, A, B);
        Console.WriteLine(ancestor.Value);
    }

    static TreeNode BuildTree(int[] values, int index, int N) {
        if (index < N) {
            TreeNode node = new TreeNode(values[index]);
            nodeMap[values[index]] = node;
            node.Left = BuildTree(values, 2 * index + 1, N);
            node.Right = BuildTree(values, 2 * index + 2, N);
            return node;
        }
        return null;
    }

    static TreeNode FindLCA(TreeNode node, int A, int B) {
        if (node == null) return null;
        if (node.Value == A || node.Value == B) return node;

        TreeNode leftLCA = FindLCA(node.Left, A, B);
        TreeNode rightLCA = FindLCA(node.Right, A, B);

        if (leftLCA != null && rightLCA != null) return node;
        return (leftLCA != null) ? leftLCA : rightLCA;
    }
}
                
            

코드 설명

1. TreeNode 클래스: 이진 트리의 노드를 표현합니다. 각각의 노드는 값과 왼쪽, 오른쪽 자식을 갖습니다.

2. Main 메서드: 프로그램의 시작점입니다. 사용자로부터 입력을 받고 트리를 생성한 후 LCA를 찾습니다.

3. BuildTree 메서드: 배열을 사용하여 이진 트리를 구축합니다. 재귀적으로 호출되어 트리를 구성합니다.

4. FindLCA 메서드: 재귀적으로 트리를 탐색하며 두 노드 A와 B의 최소 공통 조상을 찾습니다.

시간 복잡도

본 알고리즘의 시간 복잡도는 O(N)입니다.
트리를 한 번 순회하면서 각 노드를 방문하므로 노드 수에 비례하여 증가합니다.
공간 복잡도 또한 O(N)인데, 이는 재귀 호출 스택과 노드 정보를 저장하는 데 사용되는 공간 때문입니다.

맺음말

이번 강좌에서는 C#을 이용하여 최소 공통 조상 문제를 해결하는 방법에 대해 배웠습니다.
알고리즘의 원리를 이해하고 코드를 구현하면서, 코딩 테스트에서 이와 같은 트리 문제를 효과적으로 해결하는
방법에 대한 감을 잡을 수 있었을 것입니다.
다음 시간에는 다른 데이터 구조나 알고리즘 문제를 깊이 있게 다뤄보도록 하겠습니다.
감사합니다.

서론

알고리즘 문제는 코딩테스트에서 중요한 요소 중 하나로, 특히 그래프 알고리즘은 많은 상황에서 유용하게 활용됩니다.
이 글에서는 플로이드-워셜 알고리즘을 활용한 문제를 풀이해보겠습니다.
플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾기 위한 알고리즘으로, 주로 동적 프로그래밍 기법을 사용합니다.

문제 설명

문제: 최단 경로 찾기

자신이 다니는 대학교의 모든 캠퍼스는 정점으로 표현되고, 캠퍼스를 연결하는 도로는 간선으로 표현됩니다.
캠퍼스 A에서 캠퍼스 B까지 가는 최단 경로의 거리를 구해보세요. 아래의 입력 형식을 따릅니다.

            입력:
            - 첫 번째 줄: 총 캠퍼스의 개수 N (1 ≤ N ≤ 100)
            - 두 번째 줄: 도로의 개수 M (1 ≤ M ≤ 10000)
            - 다음 M 줄: 각 도로의 정보 (A, B, C) 형식으로 주어지며, A에서 B로 가는 도로의 길이가 C임을 의미합니다.
            
            출력:
            - 캠퍼스들 간의 최단 경로의 거리 행렬을 출력하시오.
        

알고리즘 개요

플로이드-워셜 알고리즘은 다음과 같은 기본 원리에 기반합니다.
모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로가 k를 경유할 경우의 거리와 직접 경로의 거리를 비교하여 최단 경로를 갱신하는 방식입니다.

            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
        

이 알고리즘은 O(N^3)의 시간 복잡도를 가지며, 모든 정점 쌍 간의 최단 경로를 효율적으로 구할 수 있습니다.

문제 풀이 과정

1단계: 입력 처리

입력을 처리하기 위해, 배열을 초기화하고 도로 정보를 입력받습니다.
거리를 무한대로 초기화한 후, 직접 연결된 캠퍼스 간의 거리를 입력받아 설정합니다.
이를 통해 초기 거리 행렬 D를 만듭니다.

2단계: 플로이드-워셜 알고리즘 구현

세 개의 중첩 루프를 통해 각 캠퍼스 쌍 간의 최소 거리를 갱신합니다.
각 반복에서 k를 경유할 경우 더 짧은 경로가 있는지를 체크하고, 그 경우 거리 행렬을 업데이트 합니다.

3단계: 결과 출력

업데이트된 거리 행렬을 출력합니다. 무한대로 남아있는 경우는 도달할 수 없는 캠퍼스를 의미합니다.

C# 코드 구현

            
            using System;
            using System.Linq;

            class Program
            {
                const int INF = 987654321; // 무한대 값 정의

                static void Main(string[] args)
                {
                    // 입력 처리
                    int N = int.Parse(Console.ReadLine());
                    int M = int.Parse(Console.ReadLine());

                    int[,] D = new int[N + 1, N + 1];

                    // 거리 배열 초기화
                    for (int i = 1; i <= N; i++)
                    {
                        for (int j = 1; j <= N; j++)
                        {
                            if (i == j) D[i, j] = 0;
                            else D[i, j] = INF; // 무한대로 초기화
                        }
                    }

                    // 도로 정보를 거리 배열에 입력
                    for (int i = 0; i < M; i++)
                    {
                        var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                        int A = input[0], B = input[1], C = input[2];
                        D[A, B] = Math.Min(D[A, B], C); // 여러 개의 도로가 있을 수 있으니 최소값으로 설정
                    }

                    // 플로이드-워셜 알고리즘
                    for (int k = 1; k <= N; k++)
                    {
                        for (int i = 1; i <= N; i++)
                        {
                            for (int j = 1; j <= N; j++)
                            {
                                D[i, j] = Math.Min(D[i, j], D[i, k] + D[k, j]);
                            }
                        }
                    }

                    // 결과 출력
                    for (int i = 1; i <= N; i++)
                    {
                        for (int j = 1; j <= N; j++)
                        {
                            if (D[i, j] == INF) Console.Write("INF ");
                            else Console.Write(D[i, j] + " ");
                        }
                        Console.WriteLine();
                    }
                }
            }
            
        

결론

이번 글에서는 플로이드-워셜 알고리즘을 이용한 최단 경로 찾기 문제를 다루었습니다.
이 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 데 효과적이며, 실제 상황에서도 널리 사용됩니다.
다양한 그래프 문제를 풀기 위해 플로이드-워셜 알고리즘을 잘 이해하고 활용하시길 바랍니다.