라이브스마트

안녕하세요! 오늘은 C#을 활용한 코딩 테스트에서 발생할 수 있는 문제를 다루고, 이를 해결하기 위한 디버깅의 중요성에 대해 이야기해보겠습니다. 이번 강좌를 통해 코딩 테스트에서 만날 수 있는 기본적인 알고리즘 문제를 해결할 것이며, 그 과정에서 디버깅 기법과 중요성을 살펴보겠습니다.

문제 정의: 배열의 두 수 합

가장 먼저 소개할 문제는 “주어진 배열에서 두 수의 합이 특정 값을 만드는 두 수의 인덱스를 반환하라”는 문제입니다. 이 문제는 많은 코딩 인터뷰에서 자주 다뤄지는 문제 중 하나입니다.

문제 설명

정수 배열 nums와 정수 target이 주어질 때, nums에서의 두 개의 수의 합이 target이 되는 인덱스를 반환하는 함수를 구현하시오. 같은 요소를 두 번 사용할 수는 없으며, 오직 하나의 정답만 존재한다고 가정하겠습니다.

예시:
    입력: nums = [2, 7, 11, 15], target = 9
    출력: [0, 1]
    설명: nums[0] + nums[1] = 2 + 7 = 9이므로 [0, 1]을 반환합니다.

문제 접근법

이 문제를 해결하기 위해 여러 접근 방법이 존재하지만, 가장 일반적인 방법은 두 개의 중첩 루프를 사용하는 것입니다. 그러나 이는 시간복잡도가 O(n^2)로 비효율적이므로 해시맵을 활용한 접근 방식이 더 효율적입니다. 해시맵을 사용하면 시간복잡도를 O(n)으로 줄일 수 있습니다.

풀이 과정

1. 빈 해시맵을 생성합니다.
2. 배열의 각 요소를 순회합니다.
3. 현재 요소의 ‘필요한 상대 값’이 해시맵에 존재하는지 확인합니다. (target - nums[i])
4. 존재한다면 해당 인덱스와 현재 인덱스를 반환합니다.
5. 존재하지 않는다면 현재 요소와 해당 인덱스를 해시맵에 추가합니다.

코드 구현

위에서 설명한 접근법을 바탕으로 아래와 같이 C# 코드를 작성할 수 있습니다.

using System;
    using System.Collections.Generic;

    public class Solution {
        public int[] TwoSum(int[] nums, int target) {
            Dictionary map = new Dictionary();
            for (int i = 0; i < nums.Length; i++) {
                int complement = target - nums[i];
                if (map.ContainsKey(complement)) {
                    return new int[] { map[complement], i };
                }
                map[nums[i]] = i;
            }
            throw new ArgumentException("No two sum solution");
        }
    }

디버깅의 필요성

이제 문제를 해결하는 과정을 설명했으니, 디버깅 과정에 대해 이야기해보겠습니다. 프로그래밍에서 디버깅은 매우 중요한 단계로, 우리가 만든 코드의 오류를 수정하고 최적화하는 과정입니다. 디버깅을 잘 하면 문제를 빠르게 분석하고 해결할 수 있습니다.

디버깅 기법

디버깅 과정에서는 여러 가지 기법을 사용할 수 있습니다. 이 중 몇 가지를 소개합니다.

• Print 디버깅: 코드의 특정 부분에 결과값을 출력하여 변수의 값과 흐름을 확인할 수 있습니다.
• 디버거 활용: IDE에 내장된 디버거를 사용하여 중단점을 설정하고, 코드 실행을 단계별로 분석하는 방법입니다.
• 단위 테스트: 구문 오류가 아닌 논리적 오류를 사전에 잡기 위해, 각 함수를 미리 테스트하는 체계적인 절차입니다.

디버깅 단계

디버깅은 다음과 같은 단계로 진행됩니다.

1. 문제를 이해하고 입력값 및 예상 결과를 명확히 합니다.
2. 코드를 실행하고 결과를 비교하여 오류를 찾아냅니다.
3. 문제를 해결할 수 있는 적절한 부분을 찾고 수정합니다.
4. 수정 후 해당 코드를 다시 테스트하여 문제 해결 여부를 확인합니다.

결론

이번 강좌를 통해 C#의 기본적인 코딩 문제를 해결하는 과정을 살펴보았고, 디버깅의 중요성을 강조하였습니다. 알고리즘 문제를 해결하는 것은 매우 중요하지만, 그 과정에서 발생하는 문제를 효과적으로 해결하는 것도 마찬가지로 중요합니다. 디버깅을 통해 더 나은 프로그래머가 되고, 코딩 테스트에서의 성공 확률을 높일 수 있습니다. 다음 강좌에서는 더욱 복잡한 문제를 다루고, 다양한 방법을 통해 효율적인 해결책을 모색해보겠습니다. 감사합니다!

안녕하세요, 여러분! 오늘은 C#을 사용하여 다익스트라 알고리즘을 구현하고, 이를 통해 알고리즘 문제를 해결하는 방법에 대해 깊이 있게 알아보도록 하겠습니다. 이 강좌에서는 알고리즘의 기본 개념, 문제 정의, C# 코드 구현, 그리고 최적화 방법을 단계별로 설명할 것입니다.

1. 다익스트라 알고리즘이란?

다익스트라 알고리즘은 그래프에서 최단 경로를 찾기 위한 알고리즘입니다. 특히, 모든 간선의 가중치가 0보다 크거나 같을 때 유용하게 사용됩니다. 이 알고리즘은 특정 노드에서 시작하여 다른 모든 노드까지의 최단 경로를 효율적으로 계산합니다.

다익스트라 알고리즘의 기본 원리는 다음과 같습니다:

1. 시작 노드에서 거리 값을 초기화합니다. 시작 노드의 거리는 0, 다른 노드는 무한대로 설정합니다.
2. 현재 노드에서 인접한 노드로 이동할 때, 현재 노드를 통해 인접 노드에 도달하는 거리가 더 짧은 경우 거리 값을 업데이트합니다.
3. 모든 노드가 방문될 때까지 이 과정을 반복합니다.
4. 최종적으로 각 노드까지의 최단 거리를 출력합니다.

2. 문제 정의

이번에 함께 풀어볼 문제는 “최단 경로 찾기”입니다. 주어진 그래프의 노드와 간선이 있고, 특정 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 것입니다.

문제의 입력은 다음과 같습니다:

• 첫 번째 줄: 노드의 수 N (1 <= N <= 100,000)과 간선의 수 M (1 <= M <= 200,000)
• 두 번째 줄부터 M개의 줄: 각 간선의 정보 (A, B, C)로, 여기서 A와 B는 노드 번호, C는 두 노드 사이의 거리입니다.
• 마지막 줄: 출발 노드 K

출력은 각 노드까지의 최단 거리입니다. 도달할 수 없는 노드는 “INF”로 표시합니다.

3. 알고리즘 설계

다익스트라 알고리즘을 C#으로 구현하기 위해 필요한 라이브러리와 데이터 구조로는 다음을 사용할 수 있습니다:

• 우선순위 큐: 거리 정보를 관리하기 위해 사용합니다.
• 그래프 표현: 인접 리스트 또는 인접 행렬을 통해 그래프를 표현합니다.
• 거리 배열: 각 노드에 대한 최단 거리 값을 저장합니다.

4. C# 코드 구현

먼저 C#에서 다익스트라 알고리즘을 구현하기 위한 전체 코드를 살펴보겠습니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int N = input[0];
        int M = input[1];

        List>[] graph = new List>[N + 1];
        for (int i = 0; i <= N; i++)
            graph[i] = new List>();

        for (int i = 0; i < M; i++)
        {
            input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            graph[input[0]].Add(new Tuple(input[1], input[2]));
            graph[input[1]].Add(new Tuple(input[0], input[2])); // 무향 그래프인 경우
        }

        int K = int.Parse(Console.ReadLine());
        int[] distances = Dijkstra(graph, N, K);

        for (int i = 1; i <= N; i++)
        {
            Console.WriteLine(distances[i] == int.MaxValue ? "INF" : distances[i].ToString());
        }
    }

    static int[] Dijkstra(List>[] graph, int N, int start)
    {
        int[] distances = new int[N + 1];
        for (int i = 1; i <= N; i++)
            distances[i] = int.MaxValue;
        distances[start] = 0;

        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.Enqueue(start, 0);

        while (priorityQueue.Count > 0)
        {
            var current = priorityQueue.Dequeue();
            int currentNode = current.Item1;
            int currentDistance = current.Item2;

            if (currentDistance > distances[currentNode]) continue;

            foreach (var edge in graph[currentNode])
            {
                int nextNode = edge.Item1;
                int weight = edge.Item2;

                if (distances[currentNode] + weight < distances[nextNode])
                {
                    distances[nextNode] = distances[currentNode] + weight;
                    priorityQueue.Enqueue(nextNode, distances[nextNode]);
                }
            }
        }

        return distances;
    }
}

5. 코드 설명

위의 코드에서는 다익스트라 알고리즘을 구현하였습니다. 각 부분의 기능을 자세히 설명하겠습니다.

5.1. 메인 함수

메인 함수에서는 입력을 받고, 그래프를 구성한 후 다익스트라 함수를 호출합니다.

• 입력을 받아 N과 M을 구분합니다.
• 각 노드에서 리스트로 표현된 그래프를 초기화합니다.
• 주어진 간선 정보를 기반으로 그래프를 구성합니다.
• 출발 노드 K를 입력받고, 다익스트라 함수를 호출하여 최단 거리 배열을 반환받습니다.
• 각 노드의 최단 거리를 출력합니다. 도달할 수 없는 경우 “INF”를 표시합니다.

5.2. Dijkstra 함수

Dijkstra 함수는 다익스트라 알고리즘의 핵심 로직을 포함하고 있습니다.

• 거리 배열을 초기화합니다.
• 우선순위 큐를 사용하여 현재 노드 정보를 저장하고, 가장 작은 거리를 가진 노드를 선택합니다.
• 현재 노드와 인접한 노드들에 대해 최단 거리 업데이트를 수행합니다.

6. 테스트 케이스

이제 다익스트라 알고리즘이 잘 작동하는지 테스트하기 위해 몇 가지 테스트 케이스를 만들어 보겠습니다.

6.1. 테스트 케이스 1

입력:

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

출력:

0
2
3
5
4

6.2. 테스트 케이스 2

입력:

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

출력:

0
3
1
4

7. 정리 및 최적화

이번 강좌에서는 C#을 사용하여 다익스트라 알고리즘을 구현하고, 최단 경로 찾기 문제를 해결했습니다. 다익스트라 알고리즘의 효율성을 높이기 위해 다음과 같은 최적화 방법을 고려할 수 있습니다:

• 우선순위 큐 대신 Fibonacci 힙을 사용하면, 최악의 경우 O(V log V) 시간 복잡도로 계산할 수 있습니다.
• 그래프가 희소한 경우 인접 리스트를 사용하여 메모리를 절약할 수 있습니다.

다음 강좌에서 다루게 될 주제는 “벨만-포드 알고리즘”으로, 이 알고리즘은 음수 가중치 간선이 존재할 때 최단 경로를 찾는 데 유용합니다. 여러분의 알고리즘 실력 향상에 도움이 되었으면 좋겠습니다! 감사합니다.

작성자: 조광형

작성일: [오늘의 날짜]

들어가며

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

문제 설명

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

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

              1
             / \
            2   3
           / \
          4   5
            

이 트리에서 노드 4와 5의 최소 공통 조상은 2입니다. 노드 2는 4와 5로 가는 경로에서 가장 가까운 조상입니다.

문제 요구 사항

• 이진 트리가 주어질 때, 두 개의 노드의 값을 입력받아 최소 공통 조상을 반환합니다.
• 노드의 값이 주어진 경우, 그 값에 해당하는 노드를 찾아야 합니다.
• 입력으로 주어지는 노드는 이진 트리 내에 항상 존재합니다.
• 시간 복잡도는 O(N)으로 제한됩니다.

접근 방식

이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용할 수 있습니다.

1. 트리를 순회하여 각 노드의 부모 노드를 찾아 저장합니다.
2. 첫 번째 노드의 조상 경로를 저장한 후, 두 번째 노드의 조상을 위에서부터 체크하며 공통 조상을 찾습니다.
3. 이 방법을 통해 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#으로 구현을 통해 문제 해결 능력을 배양할 수 있었기를 바랍니다. 알고리즘 문제풀이에서의 기본 개념을 충분히 이해하고 다양한 상황에 적용해 보는 것이 중요합니다.

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

코딩테스트에서 알고리즘 문제를 효과적으로 해결하는 방법 중 하나는 동적 계획법(Dynamic Programming, DP)입니다. 동적 계획법은 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 접근 방식으로, 최적화 문제를 해결하고 계산을 줄이는 데 매우 유용합니다. 이번 강좌에서는 동적 계획법의 기초부터 시작하여 실제 문제를 통해 이론을 살펴보고, C# 프로그래밍 언어를 사용하여 문제를 해결하는 방법을 단계별로 설명하겠습니다.

동적 계획법의 이해

동적 계획법은 기본적으로 두 가지 중요한 성질인 최적 부분 구조와 중복 쌍 문제를 활용합니다. 최적 부분 구조는 문제의 최적 해결 방법이 그 하위 문제의 최적 해결 방법으로 구성된다는 것을 의미합니다. 중복 쌍 문제는 동일한 하위 문제를 여러 번 해결하는 대신, 그 결과를 저장하여 필요할 때 재사용하는 것입니다. 이를 통해 효율성을 획기적으로 높일 수 있습니다.

동적 계획법의 적용 예시

동적 계획법은 다음과 같은 문제에 사용됩니다:

• 피보나치 수열 계산
• 최장 공통 부분 수열(longest common subsequence)
• 최소 경로 문제
• 0-1 배낭 문제
• 동적 행렬 곱셈

문제 소개: 0-1 배낭 문제

이번 강좌에서는 0-1 배낭 문제를 통해 동적 계획법을 적용해 보겠습니다. 문제는 다음과 같이 설명됩니다:

무게의 제한이 있는 배낭이 있습니다. 각 아이템은 고유한 무게와 가치를 가집니다. 각 아이템은 0개 또는 1개만 사용할 수 있으며, 배낭에 담을 수 있는 최대 가치는 무엇인지 계산하세요.

예시로 다음과 같은 아이템 목록이 있다고 가정해 봅시다:

아이템	무게	가치
아이템 1	1	1
아이템 2	2	6
아이템 3	3	10
아이템 4	5	16

배낭의 최대 무게는 7입니다. 이 경우 최대 가치는 얼마일까요?

문제 풀이 과정

1단계: 문제 정의

우리는 재귀적인 사고 방식으로 문제를 해결하려고 할 수 있지만, 이는 중복된 계산을 야기할 수 있습니다. 따라서, 동적 계획법을 사용하여 하위 문제의 해결책을 저장하고 재사용하는 방식으로 접근합니다.

2단계: 상태 정의

먼저 우리가 해결해야 할 문제를 정의합니다. dp[i][w]를 사용하여 첫 i개의 아이템을 고려했을 때, 무게 w를 초과하지 않으면서 최대 가치를 저장합니다. i는 아이템의 인덱스, w는 배낭의 무게입니다.

3단계: 상태 전이 방정식

이제 상태 전이 방정식을 정의해야 합니다. i 번째 아이템을 포함하는 경우와 포함하지 않는 경우를 나누어 생각합니다.

• 아이템 i를 포함하지 않을 경우: dp[i][w] = dp[i-1][w]
• 아이템 i를 포함할 경우(이때 아이템의 무게가 w를 넘어서는 안 됨): dp[i][w] = dp[i-1][w – weight[i]] + value[i]

최종적으로, 두 경우 중 최대값을 선택합니다:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

4단계: 초기 조건 정의

기본적으로 아이템이 없거나 무게가 0인 경우에는 최대 가치는 0입니다. 따라서 다음과 같이 초기화합니다:

for w in range(max_weight + 1):
    dp[0][w] = 0
for i in range(n + 1):
    dp[i][0] = 0

5단계: 최종 솔루션

모든 하위 문제를 해결한 후, dp 배열의 마지막 요소는 최적의 해를 나타냅니다. 이를 출력하여 결과를 확인합니다.

6단계: C# 코드 구현

using System;

class Program
{
    static void Main(string[] args)
    {
        int[] weights = new int[] { 1, 2, 3, 5 };
        int[] values = new int[] { 1, 6, 10, 16 };
        int maxWeight = 7;
        int n = weights.Length;

        int[,] dp = new int[n + 1, maxWeight + 1];

        // 초기화
        for (int w = 0; w <= maxWeight; w++)
            dp[0, w] = 0;
        
        for (int i = 0; i <= n; i++)
            dp[i, 0] = 0;

        // 동적 계획법 적용
        for (int i = 1; i <= n; i++)
        {
            for (int w = 1; w <= maxWeight; w++)
            {
                if (weights[i - 1] <= w)
                    dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
                else
                    dp[i, w] = dp[i - 1, w];
            }
        }

        Console.WriteLine("최대 가치: " + dp[n, maxWeight]);
    }
}

결과 확인

위 코드를 실행하면 주어진 배낭 문제에 대한 최대 가치를 출력하게 됩니다. 이 경우 결과는 17이 됩니다. 이는 아이템 2와 아이템 3을 선택하여 최대 무게를 초과하지 않으면서 최대 가치를 얻을 수 있음을 의미합니다.

결론

이번 강좌를 통해 동적 계획법의 기초와 0-1 배낭 문제를 해결하는 과정을 살펴보았습니다. 동적 계획법은 많은 알고리즘 문제에서 활용될 수 있으며, 문제 해결 능력을 키우는 데 큰 도움을 줄 것입니다. 연습을 통해 다양한 문제를 해결해 보시고, 더 깊이 있는 이해를 쌓으시길 바랍니다.

다음 강좌에서는 더 다양한 동적 계획법 응용문제를 다루어 보겠습니다. 감사합니다!

문제 설명

주어진 방향 그래프에서 임계 경로를 구하는 문제입니다. 임계 경로는 그래프 내의 노드와 엣지로 표현되며, 가장 긴 경로를 해결하는 문제입니다. 주어진 그래프는 노드의 개수 n과 엣지의 개수 m으로 구성되어 있습니다.

입력 형식

• 첫 번째 줄에 정수 n과 m이 주어진다.
• 다음 m줄에 각각 한 쌍의 정수 u와 v가 주어진다. 이는 노드 u에서 노드 v로 가는 엣지를 나타낸다.

출력 형식

가장 긴 경로의 길이를 출력한다.

예제 입력

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

예제 출력

4

문제 풀이 과정

이 문제를 해결하기 위해 다음과 같은 방법을 사용할 수 있습니다.

단계 1: 그래프 표현

주어진 방향 그래프를 Adjacency List 형태로 표현합니다. 이를 통해 각 노드에서 이동할 수 있는 노드들을 쉽게 확인할 수 있습니다.

단계 2: 위상 정렬

가장 긴 경로를 구하기 위해서는 그래프의 모든 노드를 한 번씩 방문해야 합니다. 이를 위해 위상 정렬을 활용합니다. 위상 정렬을 통해 모든 노드는 순서대로 방문할 수 있게 됩니다.

단계 3: 최장 경로 계산

위상 정렬이 완료된 후에는 각 노드에 대해 시작 노드부터 해당 노드까지의 최장 경로를 계산합니다. 이때, 최장 경로의 값을 저장할 배열을 사용합니다.

단계 4: 코드 구현

다음은 C#을 사용한 임계 경로 구하기 코드 구현 예시입니다:

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int n = 6; // 노드의 수
        int m = 7; // 엣지의 수
        List[] graph = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List();
        }

        // 엣지 정보 입력
        graph[1].Add(2);
        graph[1].Add(3);
        graph[2].Add(4);
        graph[3].Add(4);
        graph[4].Add(5);
        graph[5].Add(6);
        graph[3].Add(6);
        
        // 위상 정렬을 위한 인접 행렬
        int[] inDegree = new int[n + 1];
        foreach (var edges in graph) {
            foreach (var v in edges) {
                inDegree[v]++;
            }
        }

        // 위상 정렬을 위한 큐
        Queue queue = new Queue();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        // 최장 경로 계산
        int[] longest = new int[n + 1];
        while (queue.Count > 0) {
            int u = queue.Dequeue();
            foreach (var v in graph[u]) {
                longest[v] = Math.Max(longest[v], longest[u] + 1);
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.Enqueue(v);
                }
            }
        }

        // 결과 출력
        int maxPath = 0;
        for (int i = 1; i <= n; i++) {
            maxPath = Math.Max(maxPath, longest[i]);
        }
        Console.WriteLine(maxPath);
    }
}
    

코드 설명

위의 코드는 다음과 같이 작동합니다:

1. 그래프를 List 자료구조로 표현합니다.
2. 모든 엣지에 대해 노드의 진입 차수를 계산합니다.
3. 진입 차수가 0인 노드를 큐에 추가하여 위상 정렬을 수행합니다.
4. 위상 정렬된 순서대로 각 노드에 대해 최장 경로를 업데이트합니다.
5. 최종적으로, 가장 긴 경로의 길이를 출력합니다.

결론

임계 경로 구하기 문제는 위상 정렬과 최장 경로 계산을 통해 효율적으로 해결할 수 있습니다. 이 방법은 다양한 경로 최적화 문제에 적용될 수 있으므로, 기초적인 이해와 실습이 중요합니다.

이 글이 C# 코딩 테스트 준비에 도움이 되기를 바랍니다! 추가적인 질문이나 설명이 필요하시면 댓글로 남겨주세요.