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

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# 코딩 테스트에 대비하는 데 도움이 되었길 바랍니다. 다음 시간에는 다른 알고리즘 주제로 찾아뵙겠습니다. 감사합니다!

안녕하세요! 이번 강좌에서는 C# 알고리즘 코딩테스트의 한 예제로 미로 탐색 문제를 다루어 보겠습니다. 미로 탐색 문제는 그래프 이론과 DFS(Depth-First Search), BFS(Breadth-First Search) 알고리즘을 이해하는 데 매우 유용합니다. 이 강좌에서는 문제를 정의하고, 입력 형식, 출력 형식, 해결 알고리즘을 단계적으로 설명하겠습니다.

1. 문제 정의

주어진 2차원 배열로 구성된 미로에서 시작점에서 도착점까지 도달할 수 있는 방법의 수를 세는 문제입니다. 미로는 다음과 같은 규칙을 따릅니다:

• 0은 이동 가능한 경로를 나타냅니다.
• 1은 이동 불가능한 벽을 나타냅니다.

예를 들어, 다음과 같은 미로가 주어진다면:

0 1 0 0
0 1 0 1
0 0 0 0
1 1 0 1

이 미로에서 (0,0)에서 (3,2)까지 가는 모든 경로의 수를 세는 것이 우리의 목표입니다.

2. 입력 형식

첫 번째 줄에는 미로의 세로 크기 n과 가로 크기 m이 공백으로 구분되어 주어집니다. 두 번째 줄부터 n개의 줄에 걸쳐 미로가 0과 1로 주어집니다.

3. 출력 형식

시작점에서 도착점까지 도달할 수 있는 경로의 수를 출력합니다.

4. 접근 방식

이 문제를 해결하기 위해 BFS를 사용할 것입니다. BFS는 너비 우선 탐색으로, 주어진 그래프에서 최단 경로를 찾거나 특정 조건의 경로를 찾는 데 적합합니다. 문제를 해결하기 위한 단계는 다음과 같습니다:

1. 미로의 시작점을 큐에 넣고 방문 여부를 배열에 기록합니다.
2. 큐에서 현재 위치를 꺼내고, 상하좌우로 이동할 수 있는 위치를 확인합니다.
3. 이동할 수 있는 위치가 방문하지 않은 곳이라면 큐에 추가하고 방문 여부를 기록합니다.
4. 목적지에 도착하면 경로 수를 증가시킵니다.
5. 모든 경로가 탐색될 때까지 반복합니다.

5. C# 코드 구현

이제 C#으로 이 알고리즘을 구현해 보겠습니다. 아래는 미로 탐색을 위한 C# 코드입니다.

using System;
using System.Collections.Generic;

class Program
{
    static int n, m;
    static int[,] maze;
    static bool[,] visited;
    static int[] deltaRow = { -1, 1, 0, 0 };
    static int[] deltaCol = { 0, 0, -1, 1 };
    static int pathCount = 0;

    static void Main()
    {
        // 입력 받기
        string[] inputs = Console.ReadLine().Split(' ');
        n = int.Parse(inputs[0]);
        m = int.Parse(inputs[1]);
        maze = new int[n, m];
        visited = new bool[n, m];

        for (int i = 0; i < n; i++)
        {
            string row = Console.ReadLine();
            for (int j = 0; j < m; j++)
            {
                maze[i, j] = row[j] - '0'; // '0'과 '1'을 정수로 변환
            }
        }

        // BFS 탐색 시작
        BFS(0, 0);
        Console.WriteLine("도달 가능한 경로의 수: " + pathCount);
    }

    static void BFS(int startRow, int startCol)
    {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((startRow, startCol));
        visited[startRow, startCol] = true;

        while (queue.Count > 0)
        {
            var (currentRow, currentCol) = queue.Dequeue();

            // 도착점 확인
            if (currentRow == n - 1 && currentCol == m - 1)
            {
                pathCount++;
                continue; // 다른 경로를 계속 탐색
            }

            // 상하좌우 탐색
            for (int i = 0; i < 4; i++)
            {
                int newRow = currentRow + deltaRow[i];
                int newCol = currentCol + deltaCol[i];

                // 범위 체크 및 이동 가능 여부 체크
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && 
                    maze[newRow, newCol] == 0 && !visited[newRow, newCol])
                {
                    visited[newRow, newCol] = true;
                    queue.Enqueue((newRow, newCol));
                }
            }
        }
    }
}

위 코드는 BFS를 이용하여 미로를 탐색하고, 도착점에 도달할 때마다 경로의 수를 증가시키는 기능을 합니다. 이 코드는 시작점 (0, 0)에서 시작하여 도착점 (n-1, m-1)까지 가능한 모든 경로를 탐색합니다.

6. 코드 설명

코드의 주요 부분을 구체적으로 설명하겠습니다.

6.1. 입력 처리

입력 부분에서는 먼저 미로의 크기를 입력받고, 그에 따라 2차원 배열인 maze를 초기화합니다. 각 행을 읽어 들여 0과 1로 나누어 저장합니다.

6.2. BFS 함수

BFS 함수에서는 큐를 사용하여 현재 위치에서 4방향으로 이동할 수 있는지를 검사합니다. 여기에서는 deltaRow와 deltaCol 배열을 사용하여 상하좌우로 이동할 때의 인덱스를 계산합니다.

6.3. 경로 Counting

도착점에 도달했을 경우, pathCount를 증가시키며 다른 경로를 탐색할 수 있도록 관리합니다. BFS는 모든 가능한 경로를 탐색하는 데 유용한 방법입니다.

7. 성능 분석

이 알고리즘의 시간 복잡도는 O(N * M)입니다. 이는 각 셀을 한 번씩 체크하기 때문입니다. 그러나 최악의 경우 모든 경로를 탐색해야 하므로 추가적인 시간 소모가 있을 수 있습니다.

8. 문제 해결 후 한 단계 더 나아가기

이제 미로 탐색의 기본적인 개념을 이해했으니, 다음 단계로 미로의 최단 경로를 계산할 수 있는 Dijkstra 알고리즘이나 A* 알고리즘을 활용해 보세요. 각 알고리즘의 작동 방식을 학습하고, 이를 활용하여 최적 경로 문제를 해결하는 데 도전해 보세요.

9. 마무리

이번 강좌에서는 C#을 이용한 미로 탐색 문제를 해결하는 방법을 알아보았습니다. BFS 알고리즘이 어떻게 동작하는지, 그리고 문제를 해결하기 위해 어떤 과정을 거쳤는지를 살펴보았습니다. 이번 강좌가 여러분의 알고리즘 실력 향상에 도움이 되었기를 바라며, 더 많은 코딩테스트 준비를 진행하시기 바랍니다.