라이브스마트

문제 설명

당신은 친구들에게 크리스마스 서프라이즈 선물을 전달하는 이벤트를 기획하고 있습니다.
N명의 친구가 있고 각 친구는 선물을 받고 싶은 목록을 가지고 있습니다.
당신은 가능한 한 많은 친구들이 원하는 선물을 받을 수 있도록 해야 합니다.
각 친구는 원하는 선물 한 가지를 지정하며, 선물은 하나 밖에 없습니다.
단, 선물은 하나의 친구에게만 전달될 수 있습니다.

입력 형식

• 첫째 줄에 친구의 수 N이 주어집니다.
• 둘째 줄부터 N번째 줄까지 각 친구가 원하는 선물이 나열됩니다.

출력 형식

최대 몇 명의 친구들이 원하는 선물을 받을 수 있는지 출력합니다.

제한

• 1 ≤ N ≤ 100
• 선물은 알파벳 대문자로 표기되며, 최대 26종류가 존재합니다.

문제 접근 방법

이 문제는 기본적으로 그래프 이론에서 최대 매칭 문제와 유사합니다.
각 친구를 정점으로, 친구가 원하는 선물을 간선으로 연결할 수 있습니다.
이 문제를 해결하기 위해 우리는 친구들의 선물 요청을 입력 받아
각 선물에 대해 친구가 요청한 목록을 생성한 뒤,
최대 매칭을 구하는 알고리즘을 사용할 것입니다.

알고리즘 개요

– 입력된 친구의 수와 요청된 선물을 기반으로 그래프를 구성합니다.
– 그래프를 탐색하여 각 친구에게 할당 가능한 선물을 찾습니다.
– DFS(Depth First Search) 알고리즘을 사용하여 가능한 매칭을 시도합니다.

코드 구현

아래는 C#으로 작성된 선물 전달하기 문제의 풀이 코드입니다.

                
using System;
using System.Collections.Generic;

class Program
{
    static int N;                         // 친구의 수
    static List friends;          // 친구가 원하는 선물 목록
    static Dictionary gifts; // 각 선물의 매칭 상태
    static bool[] visited;                // DFS 방문 여부 기록

    static void Main(string[] args)
    {
        N = int.Parse(Console.ReadLine());
        friends = new List();

        for (int i = 0; i < N; i++)
        {
            friends.Add(Console.ReadLine());
        }

        gifts = new Dictionary();
        int totalMatched = 0;

        foreach (var friend in friends)
        {
            visited = new bool[26];
            if (DFS(friend[0], ref totalMatched))
            {
                totalMatched++;
            }
        }

        Console.WriteLine(totalMatched);
    }

    static bool DFS(char gift, ref int totalMatched)
    {
        int index = gift - 'A';

        if (visited[index]) return false; // 이미 방문한 선물
        visited[index] = true;

        if (!gifts.ContainsKey(gift.ToString()) || gifts[gift.ToString()] == -1)
        {
            gifts[gift.ToString()] = totalMatched; // 선물 매칭
            return true;
        }

        return false;
    }
}
                
            

코드 설명

위 코드는 다음과 같은 절차로 선물 전달 문제를 해결합니다.

• 입력 읽기: 친구의 수 N을 입력받고, 각 친구마다 원하는 선물을 입력받습니다.
• DFS 함수 구현: 요청한 선물이 가능한지 확인하며, 매칭을 시도합니다.
• 방문 여부 기록: 선물 당 한 번만 요청을 수용하기 위해 방문 기록을 관리합니다.
• 결과 출력: 최대 매칭 결과를 출력합니다.

시간 복잡도

이 알고리즘은 O(N^2) 복잡도를 가집니다.
각 친구에 대해 DFS를 호출하고, 선물의 수는 최대 26개로 제한되어 있기 때문에
문제의 범위 안에서는 충분히 효율적입니다.

결론

“선물 전달하기” 문제는 친구들에게 선물을 배분하는 흥미로운 문제입니다.
DFS와 그래프의 최대 매칭 원리를 통해 구현할 수 있음을 보여주었습니다.
향후 비슷한 문제에서도 이 원리를 적용하여 풀이할 수 있을 것입니다.

이 글이 C# 코딩 테스트 대비에 도움이 되었으면 합니다.
다양한 문제를 통해 알고리즘을 연습해 보시기 바랍니다.

코딩 테스트를 준비하는 많은 분들께서는 알고리즘 문제 풀이에 대한 체계적인 학습이 필요합니다. 오늘은 구간 합을 구하는 문제에 대해 다뤄보겠습니다. 특히, ‘구간 합 구하기 3’ 문제는 다양한 전략을 활용할 수 있는 흥미로운 문제입니다. 이 글에서는 문제의 정의, 풀이 방법, C# 코드를 통한 구현 및 시간 복잡성 분석까지 자세히 설명하겠습니다.

문제 정의

주어진 정수 배열 arr와 여러 쿼리 query가 있을 때, 각 쿼리는 구간의 시작과 끝을 나타냅니다. 우리의 목표는 각 쿼리의 구간 합을 효율적으로 계산하여 반환하는 것입니다.

예시

배열: arr = [1, 2, 3, 4, 5]
쿼리: query = [[1, 3], [0, 2], [2, 4]]
출력: [9, 6, 12]

위의 예시에서 첫 번째 쿼리는 인덱스 1부터 3까지의 구간을 의미하므로, 2 + 3 + 4 = 9가 됩니다. 나머지 쿼리들도 동일한 방식으로 처리할 수 있습니다.

문제 접근법

문제를 해결하는 여러 방법이 있지만, 배열의 원소 개수가 많을 경우 성능이 중요한 요소로 작용할 수 있습니다. 따라서 효율적인 알고리즘은 필수적입니다.

1. 전통적인 방법

가장 기본적인 접근법은 각 쿼리에 대해 배열의 값을 직접 합산하는 것입니다. 그러나 이러한 방법은 다음과 같은 문제점을 가집니다:

• 시간 복잡도가 O(n)으로, 쿼리 수가 많아지면 효율적이지 못합니다.
• 배열의 원소 개수가 많을 경우 매우 비효율적입니다.

2. 누적 합을 이용한 방법

보다 효율적으로 문제를 해결하기 위해 노출된 방법은 누적 합을 사용하는 것입니다. 누적 합 배열은 다음과 같이 정의됩니다:

sum[i] = arr[0] + arr[1] + ... + arr[i]

이렇게 구해진 누적 합 배열을 통해 주어진 구간 합을 빠르게 계산할 수 있습니다. 구간 [left, right]의 합은 sum[right] - sum[left - 1]로 구해집니다. 이러한 방식으로 시간 복잡도를 O(1)로 줄일 수 있습니다.

3. C# 코드 구현

이제 주어진 문제를 바탕으로 C# 언어를 사용하여 누적 합을 계산하는 코드를 구현해 보겠습니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 배열 및 쿼리 정의
        int[] arr = { 1, 2, 3, 4, 5 };
        int[][] queries = { new int[] { 1, 3 }, new int[] { 0, 2 }, new int[] { 2, 4 } };

        // 구간합을 저장할 리스트
        List results = new List();

        // 누적 합 배열 생성
        int[] prefixSum = new int[arr.Length];
        prefixSum[0] = arr[0];

        for (int i = 1; i < arr.Length; i++)
        {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        // 각 쿼리에 대해 구간 합 계산
        foreach (var query in queries)
        {
            int left = query[0];
            int right = query[1];

            if (left == 0)
            {
                results.Add(prefixSum[right]);
            }
            else
            {
                results.Add(prefixSum[right] - prefixSum[left - 1]);
            }
        }

        // 결과 출력
        Console.WriteLine(string.Join(", ", results));
    }
}

코드 분석 및 설명

위 코드에서는 배열을 미리 누적 합으로 변환하여 각 쿼리의 구간 합을 O(1) 시간 내에 계산할 수 있도록 설계했습니다. 다음과 같은 단계로 진행됩니다:

1. 누적 합 배열 생성: 배열의 첫 번째 원소를 초기화한 후, 반복문을 통해 각 원소의 누적 합을 계산합니다.
2. 쿼리 수행: 각 쿼리를 순회하며 구간 합을 계산합니다. 만약 왼쪽 경계가 0이면, 바로 누적 합을 가져오고, 그렇지 않으면 두 원소의 차를 통해 구간 합을 구합니다.
3. 결과 출력: 각각의 결과를 출력합니다.

시간 복잡성 분석

이 알고리즘의 시간 복잡성은 다음과 같습니다:

• 누적 합 배열을 만들기 위한 시간: O(n)
• 각 쿼리에 대한 구간 합 계산 시간: O(1) (쿼리 수에 비례)

따라서 전체 시간 복잡성은 O(n + m)으로 나타낼 수 있으며, 여기서 m은 쿼리의 수입니다. 이는 많은 쿼리를 처리해야 할 때 효율적인 방법입니다.

마무리

오늘은 “구간 합 구하기 3” 문제를 통해 효율적인 알고리즘을 설계하고 구현하는 방법에 대해 살펴보았습니다. 알고리즘 문제는 단순한 개념일 수 있지만, 다양한 접근 방식을 통해 해결책을 찾는 것은 코딩 테스트에 있어 매우 중요한 기술입니다. 이 강좌를 통해 여러분이 직접 코드를 작성하고, 문제를 해결하는 과정에서 많은 도움을 얻기를 바랍니다.

코드의 활용, 알고리즘의 개선을 통해 여러분의 코딩 테스트 실력을 한 단계 끌어올리길 바랍니다. 다음 강좌에서 또 만나요!

1. 서론

코딩 테스트는 많은 기업에서 지원자의 알고리즘적 사고와 문제해결 능력을 평가하기 위해
실시합니다. 다양한 주제와 난이도가 존재하는 문제들 중에서, “이친수 구하기”는
DP(Dynamic Programming) 기법을 활용할 수 있는 좋은 예시입니다. 이번 글에서는 이친수 구하는 문제를
상세히 설명하고, C#을 사용하여 문제를 해결하는 과정을 단계별로 진행해보겠습니다.

2. 문제 설명

이친수(Binary Number)는 0과 1로 이루어진 숫자 중에서,
두 개의 1이 연속으로 나타나지 않는 수를 의미합니다.
예를 들어, 0과 1로 이루어진 이친수의 예시는 다음과 같습니다:
0, 1, 010, 001, 100, 0101, 1010, 1001, 0001 등입니다.
반면 11, 00000이나 1111은 이친수가 아닙니다.
예를 들어 N이 주어질 때, N 길이의 이친수의 개수를 구하라는 문제가 주어집니다.

2.1. 입력 형식

– 첫 번째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 1,000)

2.2. 출력 형식

– N 길이의 이친수의 개수를 출력한다.

2.3. 예제

    Input:
    3
    
    Output:
    3
    

이 경우 이친수는 {001, 010, 100} 총 3가지가 있습니다.

3. 문제 해결 방안

이 문제를 해결하기 위해서는 다음과 같은 접근 방식이 필요합니다.

3.1. DP 배열 정의

우리는 Dynamic Programming을 활용하여 이 문제를 해결할 수 있습니다.
먼저, DP 배열을 정의하여 N 길이의 이친수의 개수를 저장합니다.
– DP[i]는 길이 i의 이친수의 개수를 저장합니다.

3.2. 상태 전이 식

현재 상태에서 다음과 같은 상태 전이 식을 도출할 수 있습니다.
– 길이 i의 이친수는 길이 (i-1)에서 마지막 자리가 0이라면 이어붙이기 가능하고,
– 길이 (i-2)에서 마지막 자리가 1이라면 10으로 이어붙일 수 있습니다.

따라서 다음과 같이 표현할 수 있습니다:
– DP[i] = DP[i-1] + DP[i-2]

3.3. 초기 조건 설정

– DP[1] = 2 (이친수: 0, 1)
– DP[2] = 3 (이친수: 00, 01, 10)

4. C# 코드 구현

위의 논리를 바탕으로 C# 코드를 구현해보겠습니다.

    using System;

    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long[] dp = new long[N + 1];
            
            // 초기 조건 설정
            dp[1] = 2; // 이친수: 0, 1
            if (N > 1)
            {
                dp[2] = 3; // 이친수: 00, 01, 10
            }

            // DP 배열 계산
            for (int i = 3; i <= N; i++)
            {
                dp[i] = dp[i - 1] + dp[i - 2];
            }

            // 결과 출력
            Console.WriteLine(dp[N]);
        }
    }
    

5. 코드 설명

위 코드에서는 사용자로부터 N을 입력받고, DP 배열을 초기화한 후
반복문을 통해 DP 배열을 채워나갑니다.
그리고 마지막에 DP[N]을 출력하면 N 길이의 이친수 개수를 확인할 수 있습니다.

5.1. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(N)입니다. N이 최대 1,000일 경우에도
빠르게 동작하여 많은 양의 데이터를 처리할 수 있습니다.

5.2. 공간 복잡도

공간 복잡도 또한 O(N)으로 DP 배열을 사용하는 만큼
메모리 요구량이 증가합니다. 그러나 N이 작기 때문에
메모리 사용량은 크게 문제가 되지 않습니다.

6. 마무리

이번 강좌에서는 “이친수 구하기” 문제를 다루어보았습니다.
Dynamic Programming의 기법을 통해 문제를 단계적으로 해결하는
과정과 C# 코드 구현을 설명했습니다.
이러한 유형의 문제는 실제 코딩 테스트에서 자주 출제되기 때문에,
연습을 통해 충분히 익혀두시면 좋습니다.

코딩 테스트를 준비하면서 더 많은 문제를 풀어보시고,
각 문제에 대해 다양한 접근 방식과 최적화를 고민해보시길 바랍니다.
감사합니다!

안녕하세요, 여러분! 이번 블로그 포스트에서는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 문제에 대해 알아보겠습니다. MST는 그래프의 모든 정점을 포함하면서, 간선의 합이 최소인 트리를 의미합니다. 이 문제는 네트워크 설계, 데이터 클러스터링, 그리고 그룹화를 포함한 다양한 분야에서 중요한 역할을 합니다.

문제 설명

다음과 같은 그래프가 주어졌을 때, 최소 신장 트리를 구하는 문제를 해결해 보겠습니다.

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

여기서 첫 줄의 ‘5 6’은 각각 정점의 개수와 간선의 개수를 의미합니다. 이어지는 줄에서는 각 간선과 그 가중치가 주어집니다. 예를 들어 ‘1 2 1’은 정점 1과 정점 2를 연결하는 간선의 가중치가 1이라는 의미입니다.

출력 형식

최소 신장 트리에 포함된 간선의 목록과 해당 간선의 가중치의 합을 출력해야 합니다.

문제 풀이 접근법

최소 신장 트리를 구하는 방법에는 여러 가지가 있지만, 여기서는 대표적으로 프림(Prim’s) 알고리즘과 크루스칼(Kruskal’s) 알고리즘을 사용해 보겠습니다. 두 가지 방법 모두 효율적이며, 상황에 따라 다르게 적용할 수 있습니다.

프림 알고리즘

프림 알고리즘은 특정 정점에서 시작하여 가장 작은 가중치를 가진 간선을 선택함으로써 점차적으로 트리를 확장해 나가는 방식입니다. 전체 과정은 다음과 같습니다:

1. 시작 정점을 선택하고, 해당 정점을 방문한 것으로 표시합니다.
2. 현재 트리와 연결된 간선 중 가중치가 가장 낮은 간선을 선택합니다.
3. 새로운 정점을 방문하고 트리에 추가합니다.
4. 1~3단계를 모든 정점을 방문할 때까지 반복합니다.

C# 코드 구현

아래는 프림 알고리즘을 C#으로 구현한 예제입니다:

using System;
using System.Collections.Generic;

class Graph
{
    public int Vertices { get; set; }
    public List> Edges { get; set; }

    public Graph(int vertices)
    {
        Vertices = vertices;
        Edges = new List>();
    }

    public void AddEdge(int u, int v, int weight)
    {
        Edges.Add(Tuple.Create(u, v, weight));
    }

    public void PrimsMST()
    {
        int[] parent = new int[Vertices];
        int[] key = new int[Vertices];
        bool[] mstSet = new bool[Vertices];

        for (int i = 0; i < Vertices; i++)
        {
            key[i] = Int32.MaxValue;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < Vertices - 1; count++)
        {
            int u = MinKey(key, mstSet);
            mstSet[u] = true;

            foreach (var edge in Edges)
            {
                int v = edge.Item2;
                int weight = edge.Item3;
                if (edge.Item1 == u && !mstSet[v] && weight < key[v])
                {
                    parent[v] = u;
                    key[v] = weight;
                }
            }
        }

        PrintResult(parent);
    }

    private int MinKey(int[] key, bool[] mstSet)
    {
        int min = Int32.MaxValue, minIndex = -1;

        for (int v = 0; v < Vertices; v++)
        {
            if (mstSet[v] == false && key[v] < min)
            {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    private void PrintResult(int[] parent)
    {
        Console.WriteLine("간선 \t 가중치");
        int totalWeight = 0;
        for (int i = 1; i < Vertices; i++)
        {
            Console.WriteLine(parent[i] + " - " + i + "\t " + Edges[i].Item3);
            totalWeight += Edges[i].Item3;
        }
        Console.WriteLine("최소 신장 트리의 총 가중치: " + totalWeight);
    }
}

class Program
{
    static void Main(string[] args)
    {
        int vertices = 5;
        Graph g = new Graph(vertices);

        g.AddEdge(1, 2, 1);
        g.AddEdge(1, 3, 3);
        g.AddEdge(2, 3, 2);
        g.AddEdge(2, 4, 4);
        g.AddEdge(3, 4, 5);
        g.AddEdge(4, 5, 6);

        g.PrimsMST();
    }
}

위 코드에서 Graph 클래스는 그래프의 정점과 간선을 저장하며, AddEdge 메서드를 사용해 간선을 추가합니다. PrimsMST 메서드는 프림 알고리즘의 로직을 구현하고 있습니다. 가중치가 가장 작은 간선을 반복적으로 선택하여 최소 신장 트리를 완성합니다.

크루스칼 알고리즘

크루스칼 알고리즘은 간선을 기준으로 가중치를 오름차순으로 정렬한 후, 사이클이 생기지 않도록 간선을 선택하는 방식입니다. 이 알고리즘의 과정은 다음과 같습니다:

1. 그래프의 모든 간선을 가중치에 따라 정렬합니다.
2. 각 간선을 하나씩 선택하며, 선택한 간선이 현재의 트리에 포함되어도 사이클이 생기지 않는 경우 추가합니다.
3. 위 과정을 최소 신장 트리가 완성될 때까지 반복합니다.

C# 코드 구현

아래는 크루스칼 알고리즘을 C#으로 구현한 예제입니다:

using System;
using System.Collections.Generic;

class Edge : IComparable
{
    public int Source { get; set; }
    public int Destination { get; set; }
    public int Weight { get; set; }

    public int CompareTo(Edge other)
    {
        return this.Weight.CompareTo(other.Weight);
    }
}

class Graph
{
    public int Vertices { get; set; }
    public List Edges { get; set; }

    public Graph(int vertices)
    {
        Vertices = vertices;
        Edges = new List();
    }

    public void AddEdge(int source, int destination, int weight)
    {
        Edges.Add(new Edge { Source = source, Destination = destination, Weight = weight });
    }

    public void KruskalsMST()
    {
        Edges.Sort();
        int[] parent = new int[Vertices];

        for (int i = 0; i < Vertices; i++)
            parent[i] = -1;

        int totalWeight = 0;

        foreach (var edge in Edges)
        {
            int x = FindParent(parent, edge.Source);
            int y = FindParent(parent, edge.Destination);

            if (x != y)
            {
                totalWeight += edge.Weight;
                Console.WriteLine("간선: " + edge.Source + " - " + edge.Destination + " 가중치: " + edge.Weight);
                Union(parent, x, y);
            }
        }
        Console.WriteLine("최소 신장 트리의 총 가중치: " + totalWeight);
    }

    private int FindParent(int[] parent, int i)
    {
        if (parent[i] == -1)
            return i;
        return FindParent(parent, parent[i]);
    }

    private void Union(int[] parent, int x, int y)
    {
        parent[x] = y;
    }
}

class Program
{
    static void Main(string[] args)
    {
        int vertices = 5;
        Graph g = new Graph(vertices);

        g.AddEdge(1, 2, 1);
        g.AddEdge(1, 3, 3);
        g.AddEdge(2, 3, 2);
        g.AddEdge(2, 4, 4);
        g.AddEdge(3, 4, 5);
        g.AddEdge(4, 5, 6);

        g.KruskalsMST();
    }
}

위 코드에서 Graph 클래스는 크루스칼 알고리즘을 위한 구조로, 간선을 관리하며 MST를 계산하는 KruskalsMST 메서드를 포함합니다. 간선을 가중치에 따라 정렬하고, 트리에 추가할 수 있는지 확인한 후 추가합니다.

결론

이번 포스트에서 최소 신장 트리를 구하는 두 가지 알고리즘, 즉 프림 알고리즘과 크루스칼 알고리즘을 살펴보았습니다. 두 알고리즘 모두 효율적이며 특정 경우에 따라 상대적인 이점을 가집니다. 실제 코딩 테스트에서는 문제의 조건과 그래프의 형태에 따라 적절한 알고리즘을 선택하는 것이 중요합니다. 이러한 알고리즘은 실무에서도 많이 사용되며, 알고리즘 문제 풀이 능력을 향상하는 데 좋은 연습이 됩니다.

이 과정을 통해 여러분이 최소 신장 트리에 대한 이해를 높이고, C# 코딩 테스트에 대비하는 데 도움이 되었길 바랍니다. 다음 시간에는 다른 알고리즘 주제로 찾아뵙겠습니다. 감사합니다!

1. 위상 정렬이란?

위상 정렬은 방향 그래프에서 노드들을 선형으로 정렬하는 방법입니다. 이 정렬의 가장 큰 특징은 그래프 내의 모든 간선들이
정렬된 노드의 순서를 따르는 것입니다. 즉, 만약 노드 A에서 노드 B로 향하는 간선이 있다면, 노드 A는 노드 B보다 선행해야
합니다. 이러한 성질을 갖는 위상 정렬은 주로 작업의 순서를 정하거나, 스케줄링 문제에서 많이 사용됩니다.

위상 정렬은 Directed Acyclic Graph(Directed Acyclic Graph, DAG)에서만 적용할 수 있습니다.
사이클이 존재하는 경우, 위상 정렬을 할 수 없으며, 이는 그래프의 특성상 불가능한 상태를 의미합니다.
위상 정렬을 구현하는 방법에는 크게 2가지가 있습니다.
1) DFS(Depth First Search) 기반 방법
2) Kahn의 알고리즘

2. 문제 설명

다음은 위상 정렬을 이용해야 하는 문제입니다.

문제: 과목 이수 순서

당신은 대학생입니다. 여러 과목을 이수해야 졸업할 수 있습니다. 각 과목의 이수 조건은 다른 과목을 먼저
이수해야 한다는 것입니다. 이 정보를 바탕으로 각 과목의 이수 순서를 출력하세요. 만약 이수 순서가
불가능한 경우 “IMPOSSIBLE”이라고 출력해야 합니다.

입력 형식:
– 첫 번째 줄에는 과목의 수 N(1 ≤ N ≤ 1000)과 선행 과목의 수 M(0 ≤ M ≤ 100,000)이 주어진다.
– 그 다음 M줄에는 선행 과목 관계를 나타내는 두 개의 정수가 u, v가 주어진다. 이 경우 과목 u를 먼저 이수한 후
과목 v를 이수해야 한다.

출력 형식:
– 각 과목의 이수 순서를 한 줄에 하나씩 출력한다.
– 만약 이수 순서가 불가능한 경우 “IMPOSSIBLE”이라고 출력한다.

3. 문제 해결 과정

먼저, 입력을 통해 각 과목의 수와 선행 과목의 관계를 파악해야 합니다. 이를 위해 인접 리스트를 사용하여
그래프를 표현합니다. 그리고 각 노드의 차수를 저장하기 위한 배열을 하나 만들어야 합니다.
차수는 해당 노드의 선행 과목의 개수를 나타냅니다.

1) 그래프 구축:
– 입력으로 주어진 선행 과목 관계를 바탕으로 인접 리스트와 차수 배열을 구축합니다.

2) 차수를 활용한 위상 정렬:
– 차수가 0인 노드를 큐에 추가합니다. 이 경우 해당 과목은 선행 과목이 없으므로 먼저 이수할 수 있습니다.
– 큐에서 노드를 꺼내고, 이와 연결된 노드들의 차수를 1 감소시킵니다. 만약 차수가 0이 된다면, 해당 노드를 큐에 추가합니다.
– 이 과정을 반복하여 모든 노드를 처리합니다. 만약 처리된 노드의 수가 총 과목 수와 같지 않다면, 사이클이 존재하는 것이므로 “IMPOSSIBLE”을 출력해야 합니다.

4. C# 코드 구현

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 입력 받기
        int N = int.Parse(Console.ReadLine());
        int M = int.Parse(Console.ReadLine());

        // 인접 리스트와 차수 배열 초기화
        List[] graph = new List[N + 1];
        int[] inDegree = new int[N + 1];

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

        // 선행 과목 관계 입력받기
        for (int i = 0; i < M; i++)
        {
            string[] input = Console.ReadLine().Split();
            int u = int.Parse(input[0]);
            int v = int.Parse(input[1]);

            graph[u].Add(v);
            inDegree[v]++;
        }

        // 큐와 결과 리스트 초기화
        Queue queue = new Queue();
        List result = new List();

        // 차수가 0인 노드 큐에 추가
        for (int i = 1; i <= N; i++)
        {
            if (inDegree[i] == 0)
            {
                queue.Enqueue(i);
            }
        }

        // 위상 정렬
        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            result.Add(node);

            foreach (int neighbor in graph[node])
            {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                {
                    queue.Enqueue(neighbor);
                }
            }
        }

        // 결과 출력
        if (result.Count != N)
        {
            Console.WriteLine("IMPOSSIBLE");
        }
        else
        {
            foreach (int course in result)
            {
                Console.WriteLine(course);
            }
        }
    }
}

        

이 코드는 주어진 과목 수와 선행 과목 관계를 바탕으로 위상 정렬을 수행하는 방법을 보여줍니다.
그래프의 간 선행 관계에 따라 각 과목을 선형으로 정렬할 수 있습니다.

5. 결론

위상 정렬은 그래프 이론에서 매우 중요한 알고리즘 중 하나입니다.
실질적으로 많은 문제에서 적용이 가능하여, 프로그래밍 테스트에서도 자주 출제되는 주제입니다.
위 문제를 통해 위상 정렬을 어떻게 활용할 수 있는지를 이해하는 데 도움이 되었길 바랍니다.

이제 여러분은 C#을 사용하여 위상 정렬을 구현하고, 다양한 문제에 적응할 수 있는 기술을 갖추게 되었습니다.
앞으로도 위상 정렬을 필요로 하는 다양한 문제에 도전해 보시길 바랍니다.