Sort 사용하기 / DFS 와 BFS의 차이

 

 

 

 

C# 문법 복습

 

정렬 알고리즘 - C# Sort

 

정렬 알고리즘에는 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 등 여러가지 방법이 있지만

C#에서는 많은 양의 데이터를 배열이나 리스트로 정리하기 때문에

Sort 라는 메서드를 사용해 배열과 리스트의 데이터를 정렬할 수 있다.

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers));

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names));

 

Sort 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없다.

 

 

 

 

탐색 알고리즘 - DFS 와 BFS

 

노드와 간선으로 이루어진 자료 구조를 [그래프]라고 한다.

 

DFS 는 깊이 우선 탐색으로, 가능한 깊은 곳까지 노드를 탐색하고, 막히면 이전 노드로 돌아가는 방식이다.

BFS는 너비 우선 탐색으로, 가장 가까운 노드부터 차례대로 노드를 방문하는 방식이다.

 

using System.Text;

namespace ConsoleApp1
{

    public class Graph
    {
        private int V;
        private List<int>[] adj;

        public Graph(int v)
        {
            V = v;
            adj = new List<int>[V];
            for (int i = 0; i < V; i++)
            {
                adj[i] = new List<int>();
            }
        }
        public void AddEdge(int v, int w)
        {
            adj[v].Add(w);
        }

        public void DFS(int v)

        {
            bool[] visited = new bool[V];
            DFSUtil(v, visited);
        }

        private void DFSUtil(int v, bool[] visited)
        {
            visited[v] = true;
            Console.Write($"{v} ");

            foreach (int n in adj[v])
            {
                if (!visited[n])
                {
                    DFSUtil(n, visited);
                }
            }
        }

        public void BFS(int v)
        {
            bool[] visited = new bool[V];
            Queue<int> queue = new Queue<int>();

            visited[v] = true;
            queue.Enqueue(v);

            while(queue.Count > 0) 
            {
              int n = queue.Dequeue();
                Console.Write($"{n} ");

                foreach(int m in adj[n])
                {
                    if (!visited[m])
                    {
                        visited[m] = true;
                        queue.Enqueue(m);
                    }
                }
            }
        }

        class Program
        {
            static void Main(string[] args)
            {
                Graph graph = new Graph(6);

                graph.AddEdge(0, 1);
                graph.AddEdge(0, 2);
                graph.AddEdge(1, 3);
                graph.AddEdge(2, 3);
                graph.AddEdge(2, 4);
                graph.AddEdge(3, 4);
                graph.AddEdge(3, 5);
                graph.AddEdge(4, 5);

                Console.WriteLine("DFS travelsal:");
                graph.DFS(0);
                Console.WriteLine();

                Console.WriteLine("BFS travelsal:");
                graph.BFS(0);
                Console.WriteLine();
            }
        }
    }
}

 

코드의 차이점이 있다면,

DFS는 DFSUtil 이라는 새로운 변수를 통해 노드 방문 bool값을 판단하지만

BFS는 새로운 변수 없이 queue를 사용해 bool값을 판단한다.

따라서 두 방식의 결과에도 차이가 있다.

 

 

 

오늘의 회고

 

알고리즘에 대해 공부했다.

좋은 프로그래머는 문제 해결 능력과 더불어 문제를 발견하는 능력도 중요하다는 것!

기획자의 요구사항을 잘 파악하고 컴퓨터와 비즈니스를 연결하기 위해 최선의 알고리즘을 구현하는 것이 중요하다.

 

가장 중요한 것은 기본 코딩 능력!

프로그래밍 언어를 사용해 기능을 무리없이 사용하고, 머리로 생각한 알고리즘을 코드로 표현할 수 있어야 한다.

 

본격적인 팀 과제 [스파르타 던전] 제작에 앞서

팀원들끼리 프로젝트 구조에 대해 토의하고 클래스를 정리했다.

구현하고 싶은 게 많아서 시간이 부족해 보이지만.. 팀워크로 잘 해낼 수 있을거라고 믿는다.

맡은 역할을 잘 해내는 사람이 되고 싶다!

 

내일도 열심히 해야지!