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

문제 설명

주어진 이진 트리의 모든 경로 합을 구하는 함수를 작성하세요.
경로는 루트에서 잎(leaf) 노드까지의 경로이며, 이 경로에 포함되는 모든 노드의 값의 합이 이 경로의 합입니다.

입력 형식

• 입력: 이진 트리의 루트 노드(root)는 TreeNode 클래스의 인스턴스입니다.

출력 형식

• 출력: 모든 경로의 합을 담은 리스트(List)를 반환합니다.

예시

            입력: [1, 2, 3]
            출력: [3, 4]
        

이 예시에서, 경로는 1 -> 2와 1 -> 3입니다. 첫 번째 경로의 합은 3이며, 두 번째 경로의 합은 4입니다.

문제 분석

이 문제를 해결하기 위해서는 이진 트리를 탐색할 수 있는 방법이 필요합니다.
대표적인 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
이 문제에서는 DFS가 더 적합합니다. DFS를 통해 각 경로의 노드를 탐색하며 경로의 총합을 계산합니다.

해결 전략

1. 재귀 함수를 통해 각 노드를 방문합니다.
2. 현재 노드의 값을 경로의 합에 추가합니다.
3. 현재 노드가 잎 노드인지 확인합니다.
4. 잎 노드라면 현재까지의 합을 리스트에 추가합니다.
5. 자식 노드가 있다면 자식 노드를 재귀적으로 탐색합니다.
6. 탐색이 끝난 후에는 부모 노드로 돌아가기 위해 경로의 합에서 현재 노드의 값을 제거합니다.

C# 코드 구현

아래는 이진 트리의 모든 경로 합을 구하는 C# 코드입니다.

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public IList PathSum(TreeNode root) {
        List result = new List();
        FindPaths(root, 0, result);
        return result;
    }

    private void FindPaths(TreeNode node, int currentSum, List result) {
        if (node == null) {
            return;
        }

        currentSum += node.val;

        // Check if we are at a leaf node
        if (node.left == null && node.right == null) {
            result.Add(currentSum);
        } else {
            // Traverse the left and right subtree
            FindPaths(node.left, currentSum, result);
            FindPaths(node.right, currentSum, result);
        }
    }
}
        

코드 설명

TreeNode 클래스: 이진 트리의 각 노드를 표현하는 클래스입니다.
각 노드는 정수 값(val), 왼쪽 자식(left), 오른쪽 자식(right)을 가질 수 있습니다.

Solution 클래스: 이진 트리의 경로 합을 계산하는 메소드를 포함하는 클래스입니다.
PathSum 메소드는 재귀적으로 노드를 탐색하는 FindPaths 메소드를 호출합니다.

• PathSum 메소드: 주어진 이진 트리를 입력으로 받아, 모든 경로의 합을 리스트로 반환합니다.
• FindPaths 메소드: 현재 노드와 현재까지의 경로 합을 인자로 받아서 재귀적으로 탐색합니다.
  잎 노드에 도달하면 현재 경로의 합을 리스트에 추가합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. N은 트리의 노드 수입니다.
모든 노드를 한 번씩 방문하기 때문입니다. 공간 복잡도 또한 O(H)입니다. H는 트리의 높이입니다.
재귀 호출에 사용되는 스택 공간을 고려한 것입니다.

결론

이 문제를 통해 이진 트리의 탐색 방법과 재귀적인 접근법을 이해할 수 있습니다.
다양한 이진 트리 문제를 풀기 위해 이러한 기법을 익혀 두는 것이 중요합니다.
충분한 연습을 통해 이진 트리와 그 활용 방법에 익숙해지길 바랍니다.

알고리즘 문제풀이 능력을 기르기 위한 중요한 과정 중 하나는 다양한 정렬 알고리즘을 이해하고 구현해보는 것입니다.
이번 회차에서는 ‘수 정렬하기’라는 문제를 통해 C# 언어로 정렬 알고리즘을 연습하는 방법을 알아보겠습니다.

문제 설명

주어진 정수를 오름차순으로 정렬하는 프로그램을 작성하세요.
입력은 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 100,000)이 주어지고,
둘째 줄에는 N개의 정수가 주어집니다.
이 정수는 절댓값이 1,000,000 이하인 수이며, 같은 수는 여러 번 주어질 수 있습니다.

입력 예시

    5
    5 3 2 1 4
    

출력 예시

    1
    2
    3
    4
    5
    

문제 풀이 과정

1. 문제 이해하기

문제를 해결하기 위해 가장 먼저 해야 할 일은 주어진 문제를 철저히 이해하는 것입니다.
정렬이 필요한 수의 개수와 이들 수의 범위를 확인한 후, 어떤 정렬 알고리즘이 가장 적합할지를 결정해야 합니다.

2. 정렬 알고리즘 선택하기

주어진 문제의 조건을 바탕으로 가장 적합한 정렬 알고리즘을 선택합니다. 예를 들어,
기본적으로 자주 사용되는 정렬 알고리즘으로는 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬(머지 정렬) 등이 있습니다.

주어진 N의 크기가 최대 100,000인 상황에서는 O(N log N) 시간 복잡도를 가지는 정렬 알고리즘,
예를 들어 퀵 정렬이나 병합 정렬을 사용하는 것이 좋습니다.
그러나 C#에서는 내장된 정렬 방법을 사용해도 충분히 효율적이라는 점도 고려해야 합니다.

3. C#에서의 구현

C#은 Array.Sort() 메서드를 통해 쉽게 배열을 정렬할 수 있습니다.
이를 사용하면 정렬 알고리즘을 직접 구현할 필요 없이 간단하게 문제를 해결할 수 있습니다.

구현 단계

1. 사용자로부터 입력값을 받습니다.
2. 받은 입력값을 배열에 저장합니다.
3. Array.Sort() 메서드를 사용하여 배열을 정렬합니다.
4. 정렬된 배열을 출력합니다.

4. 코드 작성

아래는 C#을 이용한 전체 코드입니다.

    using System;
    using System.Linq;

    class Program
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] numbers = new int[N];
            
            for (int i = 0; i < N; i++)
            {
                numbers[i] = int.Parse(Console.ReadLine());
            }
            
            Array.Sort(numbers);
            
            foreach (var number in numbers)
            {
                Console.WriteLine(number);
            }
        }
    }
    

5. 코드 설명

위 코드는 다음과 같은 과정을 통해 실행됩니다.

1. 먼저, 정수 N을 입력받아 배열의 크기를 정합니다.
2. 그 후, N개의 정수를 차례대로 입력받아 numbers 배열에 저장합니다.
3. Array.Sort() 메서드를 호출하여 numbers 배열을 정렬합니다.
4. 마지막으로, 정렬된 배열의 각 요소를 출력합니다.

6. 시간 복잡도 분석

주어진 문제의 시간 복잡도는 O(N log N)으로, 이는 선택한 정렬 알고리즘(퀵 정렬의 경우)에 의한 것입니다.
입력의 크기가 커질수록 정렬에 소요되는 시간도 비례하여 증가하지만,
이 알고리즘은 대부분의 경우 매우 효율적으로 동작합니다.
공간 복잡도는 O(N)으로, 입력받은 배열을 저장하기 위한 추가적인 메모리 공간이 필요합니다.

7. 결론

이번 장에서는 C#을 사용하여 수 정렬하기 문제를 해결했습니다.
정렬 알고리즘의 개념을 이해하고, 내장된 메서드를 활용하여 효율적으로 문제를 해결하는 방법을 배웠습니다.
다양한 정렬 알고리즘을 직접 구현해보는 것도 추천합니다.
다음 시간에는 좀 더 복잡한 문제를 다뤄보겠습니다.
끝까지 읽어주셔서 감사합니다!

코딩 테스트가 갈수록 인기를 끌고 있는 현 시점에서, 알고리즘 문제는 필수적으로 알아둬야 할 주제입니다. 이 글에서는 병합 정렬(Merge Sort) 알고리즘에 대해 심층적으로 다루어 보겠습니다. 병합 정렬은 일반적으로 좋은 성능을 발휘하는 정렬 알고리즘 중 하나로, ‘분할 정복(Divide and Conquer)’ 전략을 기반으로 합니다. 이 글에서는 병합 정렬의 원리, 구현 방법, 그리고 실제 문제를 통해 병합 정렬을 활용하는 방법을 설명하겠습니다.

1. 병합 정렬 개요

병합 정렬은 리스트를 분할하고 정렬한 다음에 병합하는 방식으로 작동합니다. 데이터 구조의 장점과 시간 복잡도를 고려해야 하는 여러 상황에서 유용하게 쓰일 수 있습니다. 병합 정렬은 평균, 최악, 그리고 최선의 경우 모두 O(n log n)의 시간 복잡도를 가지며, 안정적인 정렬 알고리즘입니다. 즉, 동일한 값을 가진 데이터의 상대적인 순서를 유지합니다.

1.1. 병합 정렬 작동 원리

병합 정렬은 다음과 같은 과정을 통해 진행됩니다:

1. 리스트를 반으로 나누고, 각 부분 리스트를 재귀적으로 정렬합니다.
2. 정렬된 부분 리스트를 병합하여 하나의 정렬된 리스트를 만듭니다.

이 과정을 통해 리스트의 길이가 1이 될 때까지 나누고, 이 후 조합으로 다시 정렬하게 됩니다. 아래의 그림은 병합 정렬의 기본적인 흐름을 보여줍니다:

2. 병합 정렬 구현

병합 정렬을 C#로 구현해 보겠습니다. 기본적인 구현은 다음과 같습니다:

using System;

class MergeSort
{
    // 메인 메서드
    static void Main(string[] args)
    {
        int[] array = {38, 27, 43, 3, 9, 82, 10};

        Console.WriteLine("정렬 전: " + string.Join(", ", array));
        MergeSortAlgorithm(array, 0, array.Length - 1);
        Console.WriteLine("정렬 후: " + string.Join(", ", array));
    }

    // 병합 정렬 알고리즘
    static void MergeSortAlgorithm(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            // 분할
            MergeSortAlgorithm(array, left, mid);
            MergeSortAlgorithm(array, mid + 1, right);

            // 병합
            Merge(array, left, mid, right);
        }
    }

    // 병합 메서드
    static void Merge(int[] array, int left, int mid, int right)
    {
        // 두 개의 서브 배열 만들기
        int[] leftArray = new int[mid - left + 1];
        int[] rightArray = new int[right - mid];

        for (int i = 0; i < leftArray.Length; i++)
            leftArray[i] = array[left + i];

        for (int j = 0; j < rightArray.Length; j++)
            rightArray[j] = array[mid + 1 + j];

        int k = left;
        int a = 0;
        int b = 0;

        // 배열 병합
        while (a < leftArray.Length && b < rightArray.Length)
        {
            if (leftArray[a] <= rightArray[b])
            {
                array[k] = leftArray[a];
                a++;
            }
            else
            {
                array[k] = rightArray[b];
                b++;
            }
            k++;
        }

        // 남은 요소들 병합
        while (a < leftArray.Length)
        {
            array[k] = leftArray[a];
            a++;
            k++;
        }

        while (b < rightArray.Length)
        {
            array[k] = rightArray[b];
            b++;
            k++;
        }
    }
}

2.1. 코드 설명

• MergeSortAlgorithm: 이 메서드는 배열을 반으로 나누고 재귀 호출을 통해 정렬합니다. 좌측과 우측의 서브 배열을 정렬한 후 Merge 메서드를 호출하여 병합합니다.
• Merge: 이 메서드는 두 개의 서브 배열을 받아 그 배열들을 병합하여 최종 정렬된 배열로 만듭니다. 각각의 포인터를 사용하여 두 서브 배열의 요소를 비교하고, 더 작은 값을 최종 배열에 추가합니다.

3. 문제 예제

이제 병합 정렬 알고리즘을 적용해 볼 수 있는 간단한 문제를 생각해 보겠습니다.

문제: 정수 리스트 정렬하기

주어진 정수 리스트를 오름차순으로 정렬하는 메서드를 작성하시오. 입력은 1에서 1,000,000 사이의 정수 값으로 구성된 배열이며, 최대 1,000개의 요소를 가질 수 있다. 병합 정렬을 사용하여 문제를 해결하세요.

입력 예시

{8, 3, 1, 7, 0, 10, 2}

출력 예시

{0, 1, 2, 3, 7, 8, 10}

3.1. 문제 해결 과정

위 문제를 병합 정렬 알고리즘을 통해 해결하기 위해서는 앞서 작성한 병합 정렬 알고리즘을 그대로 사용할 수 있습니다. 코드를 여기에 채워 넣고, 입력값을 여러 개 테스트해 보는 것도 도움이 될 것입니다.

using System;

class SortingExample
{
    static void Main(string[] args)
    {
        int[] array = {8, 3, 1, 7, 0, 10, 2};
        MergeSort(array);
        Console.WriteLine("정렬된 배열: " + string.Join(", ", array));
    }

    // 병합 정렬 호출 메서드
    static void MergeSort(int[] array)
    {
        MergeSortAlgorithm(array, 0, array.Length - 1);
    }

    // [이곳에 위의 MergeSortAlgorithm과 Merge 메서드를 추가하세요]
}

이렇게 작성된 메서드를 통해, 주어진 정수 리스트를 오름차순으로 정렬할 수 있습니다. 여러 입력값을 통해 다양한 테스트를 거쳐, 알고리즘의 유효성을 확인하는 것이 좋습니다.

4. 병합 정렬의 장점과 단점

4.1. 장점

• 안정적인 정렬: 같은 값의 데이터들이 원래 순서를 유지하면서 정렬됩니다.
• 예측 가능한 성능: 최악의 경우에도 O(n log n)의 복잡도를 보장합니다.
• 대량의 데이터 처리: 큰 데이터셋에서도 성능이 일관되며, 외부 정렬에 대한 구현이 용이합니다.

4.2. 단점

• 추가 공간 요구: 정렬을 위해 추가적인 메모리가 필요합니다.
• 소규모 데이터에서는 비효율적: 소규모 데이터에서는 단순한 정렬 방법이 더 빠를 수 있습니다.

5. 마치며

이번 포스트에서는 병합 정렬 알고리즘에 대해 상세히 알아봤습니다. 구체적인 구현을 통해 실제 문제 해결 과정에서도 어떻게 활용할 수 있는지를 살펴보았습니다. 효율적이고 안정적인 정렬을 위해 병합 정렬이 적합하게 작용할 수 있으며, 다양한 알고리즘 문제를 푸는 데 있어서 매우 유용한 도구가 될 것입니다. 다음 포스트에서도 다양한 알고리즘을 다뤄보겠습니다. 감사합니다!

작성자: 조광형 | 날짜: [날짜]

서론

코딩 테스트에서 알고리즘은 매우 중요한 역할을 합니다. 특히, 그래프 알고리즘은 문제 해결 능력을 평가하는 데 있어 자주 등장하는 주제 중 하나입니다. 이번 글에서는 C#을 활용하여 그래프를 표현하는 방법과 함께, 그래프를 이용한 알고리즘 문제를 해결하는 과정에 대해 자세히 알아보겠습니다.

그래프란 무엇인가?

그래프는 노드(또는 정점)와 이들 간의 관계를 나타내는 간선으로 구성된 자료구조입니다. 그래프는 두 가지 주요 요소로 나눌 수 있습니다:

• 정점(Vertices): 그래프의 노드입니다.
• 간선(Edges): 정점들 간의 연결을 나타냅니다.

그래프는 방향성이 있을 수도 있고(유향 그래프), 없을 수도 있습니다(무향 그래프). 또한 연결 그래프와 비연결 그래프로도 분류될 수 있습니다.

그래프의 표현 방법

그래프를 표현하는 방법은 여러 가지가 있지만, 일반적으로 사용되는 두 가지 방법은 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다.

1. 인접 행렬(Adjacency Matrix)

인접 행렬은 그래프의 정점 수에 따라 n x n 크기의 2차원 배열을 사용하여 그래프를 표현합니다. 만약 정점 i와 정점 j가 서로 연결되어 있다면, matrix[i][j] = 1 (유향 그래프의 경우) 또는 matrix[i][j] = matrix[j][i] = 1 (무향 그래프의 경우)로 설정합니다. 인접 행렬의 장점은 간선의 존재 여부를 O(1) 시간 복잡도로 확인할 수 있다는 점입니다. 하지만, 많은 정점에 비해 연결된 간선이 적은 희소 그래프의 경우 메모리 낭비가 발생할 수 있습니다.

2. 인접 리스트(Adjacency List)

인접 리스트는 각 정점에 연결된 정점들의 리스트를 사용하여 그래프를 표현합니다. 각 정점마다 연결된 정점들의 정보를 저장하는 리스트를 갖고 있어, 메모리 사용이 덜하지만 특정 정점과 연결된 정점을 찾는 데는 O(V) (V는 정점의 수) 시간이 걸립니다. 작은 정점 개수의 그래프는 인접 행렬보다 인접 리스트가 더 유리합니다.

알고리즘 문제: 최단 경로 찾기

문제 설명

주어진 그래프의 노드와 간선 정보가 있을 때, 특정 시작 노드에서 모든 다른 노드로 가는 최단 경로의 거리를 구하는 알고리즘을 구현하세요. 이 문제는 다익스트라(Dijkstra) 알고리즘을 사용하여 해결할 수 있습니다.

입력 형식

            - 첫 번째 줄: 정점의 수 V와 간선의 수 E
            - 두 번째 줄부터 E줄: 간선의 정보 u v w (정점 u에서 정점 v로 가는 가중치 w)
            - 마지막 줄: 시작 정점 S
        

예제 입력

            5 6
            1 2 2
            1 3 3
            2 3 1
            2 4 4
            3 5 1
            4 5 2
            1
        

예제 출력

            0
            2
            3
            6
            4
        

풀이 과정

다익스트라 알고리즘은 우선순위 큐를 통해 현재까지 발견된 노드 중 최단 거리인 노드를 선택하고, 해당 노드와 인접한 노드의 거리를 갱신하는 방식으로 진행됩니다.

1. 그래프를 인접 리스트 형태로 초기화합니다.
2. 우선순위 큐를 사용하여 시작 정점으로부터의 거리를 초기화합니다.
3. 우선순위 큐에서 거리가 가장 짧은 정점을 선택하고, 해당 정점과 연결된 모든 정점의 거리를 갱신합니다.
4. 모든 정점이 확인될 때까지 2~3단계를 반복합니다.

C# 코드 구현

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        int V = int.Parse(input[0]); // 정점 수
        int E = int.Parse(input[1]); // 간선 수

        List> edges = new List>();
        for (int i = 0; i < E; i++)
        {
            var edgeInput = Console.ReadLine().Split();
            int u = int.Parse(edgeInput[0]) - 1; // 0-indexed
            int v = int.Parse(edgeInput[1]) - 1; // 0-indexed
            int w = int.Parse(edgeInput[2]);
            edges.Add(Tuple.Create(u, v, w));
        }
        
        int startVertex = int.Parse(Console.ReadLine()) - 1; // 0-indexed
        Dijkstra(V, edges, startVertex);
    }

    static void Dijkstra(int V, List> edges, int startVertex)
    {
        // 그래프 초기화
        List>> graph = Enumerable.Range(0, V)
                                                        .Select(x => new List>())
                                                        .ToList();

        foreach (var edge in edges)
        {
            graph[edge.Item1].Add(Tuple.Create(edge.Item2, edge.Item3));
            graph[edge.Item2].Add(Tuple.Create(edge.Item1, edge.Item3)); // 무향 그래프
        }

        // 거리 배열 초기화
        int[] distances = new int[V];
        for (int i = 0; i < V; i++)
            distances[i] = int.MaxValue;
        distances[startVertex] = 0;

        // 우선순위 큐 초기화
        var priorityQueue = new SortedSet>();
        priorityQueue.Add(Tuple.Create(0, startVertex)); // (거리, 정점)

        while (priorityQueue.Any())
        {
            var current = priorityQueue.Min;
            priorityQueue.Remove(current);
            int currentDistance = current.Item1;
            int currentVertex = current.Item2;

            // 이미 더 짧은 경로가 발견된 경우 스킵
            if (currentDistance > distances[currentVertex])
                continue;

            foreach (var neighbor in graph[currentVertex])
            {
                int neighborVertex = neighbor.Item1;
                int edgeWeight = neighbor.Item2;

                // 거리 갱신
                if (distances[currentVertex] + edgeWeight < distances[neighborVertex])
                {
                    distances[neighborVertex] = distances[currentVertex] + edgeWeight;
                    priorityQueue.Add(Tuple.Create(distances[neighborVertex], neighborVertex));
                }
            }
        }

        // 결과 출력
        for (int i = 0; i < V; i++)
        {
            if (distances[i] == int.MaxValue)
                Console.WriteLine("INF");
            else
                Console.WriteLine(distances[i]);
        }
    }
}
        

결론

이번 강좌를 통해 그래프에 대한 기본적인 개념과 표현 방법, 그리고 C#으로 다익스트라 알고리즘을 구현하여 최단 경로 문제를 해결하는 방법을 배웠습니다. 알고리즘 문제는 지속적인 연습이 필요합니다. 다양한 문제를 풀어보며 자신만의 해결 방법을 찾아보시길 바랍니다.

문제 설명

주어진 그래프에서 K번째 최단 경로를 찾는 문제입니다. 일반적인 최단 경로 알고리즘(다익스트라 알고리즘, 벨만-포드 알고리즘 등)은 최단 경로를 한 가지만 찾지만, 이 문제에서는 주어진 두 정점 사이의 K번째로 짧은 경로를 찾아야 합니다.

입력 형식:

• 그래프는 정점과 간선으로 이루어져 있으며, 간선은 각각의 시작 정점, 끝 정점, 그리고 가중치를 가지고 있습니다.
• 그래프의 정점 수는 N, 간선 수는 M, K는 찾고자 하는 최단 경로의 순위입니다.

출력 형식:

• K번째 최단 경로의 길이를 출력합니다. 만약 K번째 최단 경로가 존재하지 않는 경우 -1을 출력합니다.

예제

        입력: 
        4 5 2
        1 2 1
        1 3 2
        2 3 1
        2 4 3
        3 4 1

        출력:
        3
    

문제 분석

이 문제를 해결하기 위해 사용되는 알고리즘은 우선순위 큐를 활용한 그래프 탐색입니다. 전통적인 최단 경로 알고리즘을 변형하여 K번째로 짧은 경로를 찾는 접근 방법을 사용합니다. 특히, 다익스트라 알고리즘과 우선순위 큐의 조합으로 필요한 경로를 탐색할 수 있습니다.

문제를 해결하기 위한 과정은 다음과 같습니다:

1. 그래프 데이터를 입력받고, 인접 리스트 형태로 구성합니다.
2. 우선순위 큐를 생성하여 출발 정점에서 시작합니다.
3. 우선순위 큐를 통해 경로를 탐색하고, K번째 최단 경로를 카운트합니다.
4. K번째 최단 경로가 발견되면 그 길이를 출력합니다.

C# 코드 구현

아래는 위의 과정을 C#으로 구현한 코드입니다.

        
        using System;
        using System.Collections.Generic;

        class Program
        {
            static void Main(string[] args)
            {
                // 입력 받기
                var line = Console.ReadLine().Split();
                int N = int.Parse(line[0]); // 정점 수
                int M = int.Parse(line[1]); // 간선 수
                int K = int.Parse(line[2]); // K번째 최단 경로

                // 그래프 초기화
                var graph = new List<(int to, int cost)>[N + 1];
                for (int i = 0; i <= N; i++)
                {
                    graph[i] = new List<(int, int)>();
                }

                // 간선 정보 입력
                for (int i = 0; i < M; i++)
                {
                    line = Console.ReadLine().Split();
                    int a = int.Parse(line[0]);
                    int b = int.Parse(line[1]);
                    int cost = int.Parse(line[2]);
                    graph[a].Add((b, cost));
                }

                // K번째 최단 경로 찾기
                var result = FindKthShortestPath(graph, N, K);
                Console.WriteLine(result);
            }

            static int FindKthShortestPath(List<(int to, int cost)>[] graph, int N, int K)
            {
                var pq = new SortedSet<(int cost, int node, int count)>();
                pq.Add((0, 1, 0)); // (cost, node, count)

                // K번째 최단 경로를 위한 리스트
                var paths = new List[N + 1];
                for (int i = 0; i <= N; i++)
                {
                    paths[i] = new List();
                }

                while (pq.Count > 0)
                {
                    var (cost, node, count) = pq.Min;
                    pq.Remove(pq.Min);

                    paths[node].Add(cost);

                    // K번째 최단 경로를 찾았으면 리턴
                    if (count == K - 1)
                    {
                        return cost;
                    }

                    // 간선 탐색
                    foreach (var edge in graph[node])
                    {
                        pq.Add((cost + edge.cost, edge.to, count + 1));
                    }
                }

                return -1; // K번째 최단 경로가 존재하지 않을 경우
            }
        }
        
        

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O((M + N) log N) 입니다. 이유는:

1. 우선순위 큐에 노드가 추가되고 삭제되는 과정에서 log N 시간이 소요됩니다.
2. 모든 간선과 노드를 탐색하므로 그래프의 전체 크기인 O(M + N)만큼의 회차를 수행합니다.

결론

이 강좌에서는 K번째 최단 경로를 찾는 문제를 해결하기 위해 그래프 탐색에 대한 기본 개념을 바탕으로 코드를 구현했습니다. 최단 경로 접근법을 변형해서 K번째 최단 경로를 찾는 방법을 학습하면서, 다양한 알고리즘 문제에서의 전략적 사고를 키울 수 있기를 바랍니다.

다음 강좌에서는 좀 더 복잡한 그래프 탐색 문제를 다루도록 하겠습니다. 추가적으로 궁금한 점이나 피드백이 있다면 댓글로 남겨 주세요!