[C#] 알고리즘 문제

App.cs

exam.zip

0.06MB

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace exam
{
    public class App
    {
        // 생성자
        public App()
        {
            //this.Solution1();
            //this.Solution2();
            //this.Solution3();
            //this.Solution4();
            //this.Solution5();
            //this.Solution6();
            //this.Solution7();
            //this.Solution8();
            //this.Solution9();
        }

        public void Solution1()
        {
            int[] arr = new int[] { 20, 10, 35, 30, 7 };
            int min = arr[0];
            int max = arr[0];


            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] > max)
                    max = arr[i];

                if (arr[i] < min)
                    min = arr[i];
            }

            Console.WriteLine("{0}, {1}", max, min);
            Console.WriteLine();
        }

        public void Solution2()
        {
            int h = 23;
            int m = 40;

            m -= 45;
            if (m < 0)
            {
                m += 60;
                h -= 1;
                if (h == 0) h = 24;
            }

            Console.WriteLine("{0}시 {1}분", h, m);
            Console.WriteLine();
        }

        public void Solution3()
        {
            Queue<int> queue = new Queue<int>();
            for (int i = 1; i <= 8; i++)
            {
                queue.Enqueue(i);
            }

            while(queue.Count > 1)
            {
                queue.Dequeue();
                int peek = queue.Peek();
                queue.Enqueue(peek);
                queue.Dequeue();
            }

            Console.WriteLine(queue.Peek());
            Console.WriteLine();
        }

        public void Solution4()
        {
            string s1 = "So when I die(the (first) I will see in (heaven) is a score list)";
            string s2 = "A rope may form )( a trail in a maze";
            string s3 = "Help( I(m being held prisoner) in a fortune cookie factory)";

            Stack<string> stack = new Stack<string>();
        }

        public void Solution5()
        {
            Console.Write("입력: ");
            int num = Convert.ToInt32(Console.ReadLine());
            if (num > 10)
            {
                Console.WriteLine("다시 입력하세요.");
            }
            else
            {
                Console.Write("출력: {0}", this.Factorial(num));
                Console.WriteLine();
            }

        }

        public void Solution6()
        {
            var graph = new Graph<int>();
            var one = graph.AddVertex(1);
            var two = graph.AddVertex(2);
            var three = graph.AddVertex(3);
            var four = graph.AddVertex(4);
            var five = graph.AddVertex(5);

            graph.AddEdge(one, two);
            graph.AddEdge(one, four);
            graph.AddEdge(two, three);
            graph.AddEdge(two, four);
            graph.AddEdge(four, five);

            graph.BFS();
            //graph.DebugPrintGraph();
        }

        public void Solution7()
        {
            var bt = new BinaryTree<string>("A");

            bt.Root.left = new BinaryTreeNode<string>("B");
            bt.Root.left.left = new BinaryTreeNode<string>("D");
            bt.Root.right = new BinaryTreeNode<string>("C");
            bt.Root.right.left = new BinaryTreeNode<string>("E");
            bt.Root.right.right = new BinaryTreeNode<string>("F");
            bt.Root.right.right.right = new BinaryTreeNode<string>("G");

            Console.Write("전위 순회한 결과: ");
            bt.PreorderTraversal();
            Console.WriteLine();
            Console.Write("중위 순회한 결과: ");
            bt.InorderTraversal();
            Console.WriteLine();
            Console.Write("후위 순회한 결과: ");
            bt.PostorderTraversal();
            Console.WriteLine();
        }

        public void Solution8()
        {
            string p = "I am happy today";
            string[] words = p.Split(' ');
            foreach(var word in words)
            {
                char[] reverse = word.ToCharArray();
                Array.Reverse(reverse);
                Console.Write(reverse);
                Console.Write(" ");
            }
            Console.WriteLine();
        }

        public void Solution9()
        {
            string p = "It over 2000 years old";
            string str = p.Replace(" ", String.Empty);
            char[] result = str.ToCharArray();
            int count = 0;
            foreach(var c in result)
            {
                count++;
            }
            Console.WriteLine(count);
        }

        private int Factorial(int n)
        {
            if (n == 0 || n == 1) return 1;
            return n * Factorial(n - 1);
        }
    }
}

BinaryTree.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace exam
{
    public class BinaryTree<T>
    {
        public BinaryTreeNode<T> Root { get; private set; }

        public BinaryTree(T data)
        {
            this.Root = new BinaryTreeNode<T>(data);
        }

        public void PreorderTraversal()
        {
            this.PreorderTraversal(this.Root);
        }

        private void PreorderTraversal(BinaryTreeNode<T> node)
        {
            if (node == null) return;
            Console.Write(node.data);
            this.PreorderTraversal(node.left);
            this.PreorderTraversal(node.right);
        }

        public void InorderTraversal()
        {
            this.InorderTraversal(this.Root);
        }

        private void InorderTraversal(BinaryTreeNode<T> node)
        {
            if (node == null) return;
            this.InorderTraversal(node.left);
            Console.Write(node.data);
            this.InorderTraversal(node.right);
        }

        public void PostorderTraversal()
        {
            this.PostorderTraversal(this.Root);
        }

        private void PostorderTraversal(BinaryTreeNode<T> node)
        {
            if (node == null) return;
            this.PostorderTraversal(node.left);
            this.PostorderTraversal(node.right);
            Console.Write(node.data);
        }

        public void PreorderIterative()
        {
            if (this.Root == null) return;
            var stack = new Stack<BinaryTreeNode<T>>();

            // 루트를 스택에 저장
            stack.Push(this.Root);

            while (stack.Count > 0)
            {
                // 스택에 저장된 노드 가져오기
                var node = stack.Pop();

                // 방문
                Console.WriteLine("{0} ", node.data);

                // 오른쪽 노드를 스택에 저장
                if (node.right != null)
                {
                    stack.Push(node.right);
                }
                if (node.left != null)
                {
                    stack.Push(node.left);
                }
            }
        }

        public void InorderIterative()
        {
            var stack = new Stack<BinaryTreeNode<T>>();
            var node = this.Root;

            // 왼쪽 노드를 스택에 저장
            while (node != null)
            {
                stack.Push(node);
                node = node.left;
            }

            while (stack.Count > 0)
            {
                // 스택에 저장된 노드 가져오기
                node = stack.Pop();
                // 방문
                Console.WriteLine("{0} ", node.data);

                // 오른쪽 노드 존재 -> 루프 돌아서 오른쪽 노드의 왼쪽 노드도 저장
                if (node.right != null)
                {
                    node = node.right;
                    while (node != null)
                    {
                        stack.Push(node);
                        node = node.left;
                    }
                }
            }
        }

        public void PostorderIterative()
        {
            var stack = new Stack<BinaryTreeNode<T>>();
            var node = this.Root;

            while (node != null)
            {
                if (node.right != null)
                {
                    stack.Push(node.right);
                }
                stack.Push(node);
                node = node.left;
            }

            while (stack.Count > 0)
            {
                node = stack.Pop();
                if (node.right != null && stack.Count > 0 && node.right == stack.Peek())
                {
                    var right = stack.Pop();
                    stack.Push(node);
                    node = right;

                    while (node != null)
                    {
                        if (node.right != null)
                        {
                            stack.Push(node.right);
                        }
                        stack.Push(node);
                        node = node.left;
                    }
                }
                else
                {
                    Console.WriteLine("{0} ", node.data);
                }
            }
        }
    }
}

BinaryTreeNode.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace exam
{
    public class BinaryTreeNode<T>
    {
        public T data;
        public BinaryTreeNode<T> left;
        public BinaryTreeNode<T> right;

        public BinaryTreeNode(T data)
        {
            this.data = data;
        }
    }
}

Graph.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace exam
{
    public class Graph<T>
    {
        private List<Node<T>> nodes;
        private bool directedGraph;     // 방향 그래프 판단 변수

        public Graph(bool directedGraph = false)
        {
            this.nodes = new List<Node<T>>();
            this.directedGraph = directedGraph;
        }

        public Node<T> AddVertex(T data)
        {
            return this.AddVertex(new Node<T>(data));
        }

        public Node<T> AddVertex(Node<T> node)
        {
            this.nodes.Add(node);
            return node;
        }

        public void AddEdge(Node<T> from, Node<T> to, int weight = 1)
        {
            from.Neighbors.Add(to);
            from.Weights.Add(weight);
            if (!directedGraph)
            {
                to.Neighbors.Add(from);
                to.Weights.Add(weight);
            }
        }

        public void DebugPrintGraph()
        {
            foreach (var vertex in nodes)
            {
                int cnt = vertex.Neighbors.Count;
                for (int i = 0; i < cnt; i++)
                {
                    Console.WriteLine("{0}----({1})----{2}",
                        vertex.Data,
                        vertex.Weights[i],
                        vertex.Neighbors[i].Data);
                }
            }
        }

        // 깊이 우선 방식
        public void DFS()
        {
            // 방문 여부를 표시하는 방문테이블
            var visited = new HashSet<Node<T>>();

            // Disconnected Graph를 위해
            // 방문하지 않은 노드들 모두 체크
            foreach (var node in nodes)
            {
                if (!visited.Contains(node))
                {
                    this.DFSRecursive(node, visited);
                    Console.WriteLine();
                }
            }
        }

        private void DFSRecursive(Node<T> node, HashSet<Node<T>> visited)
        {
            // 노드 방문
            Console.Write("{0}", node.Data);
            visited.Add(node);

            // 인접 노드가 있을 때
            foreach (var adjNode in node.Neighbors)
            {
                // 이미 방문하지 않은 인접 노드에 대해서만
                if (!visited.Contains(adjNode))
                {
                    // 재귀 호출
                    DFSRecursive(adjNode, visited);
                }
            }
        }

        public void DFSIterative()
        {
            // 방문 테이블 생성
            var visited = new HashSet<Node<T>>();

            foreach (var node in nodes)
            {
                if (!visited.Contains(node))
                {
                    DFSUsingStack(node, visited);
                }
            }
        }

        private void DFSUsingStack(Node<T> node, HashSet<Node<T>> visited)
        {
            var stack = new Stack<Node<T>>();
            stack.Push(node);

            while (stack.Count > 0)
            {
                var vertex = stack.Pop();
                if (!visited.Contains(vertex))
                {
                    Console.WriteLine("{0}", vertex.Data);
                    visited.Add(vertex);
                }
                foreach (var adjNode in vertex.Neighbors)
                {
                    if (!visited.Contains(adjNode))
                    {
                        stack.Push(adjNode);
                    }
                }
            }
        }

        public void BFS()
        {
            var visited = new HashSet<Node<T>>();

            // 방문하지 않은 노드 체크
            foreach (var node in nodes)
            {
                if (!visited.Contains(node))
                {
                    BFS(node, visited);
                }
            }
        }

        private void BFS(Node<T> node, HashSet<Node<T>> visited)
        {
            var q = new Queue<Node<T>>();
            int count = 0;
            q.Enqueue(node);

            while (q.Count > 0)
            {
                var vertex = q.Dequeue();

                // 노드 방문
                if (!visited.Contains(vertex))
                {
                    //Console.Write("{0}", vertex.Data);
                    count++;
                    visited.Add(vertex);
                }

                foreach (var adjNode in vertex.Neighbors)
                {
                    // 이미 방문하지 않은 인접 노드에 대해
                    if (!visited.Contains(adjNode))
                    {
                        q.Enqueue(adjNode);
                    }
                }
            }

            Console.WriteLine(count);
        }
    }
}

Node.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace exam
{
    public class Node<T>
    {
        public T Data { get; set; }
        public List<Node<T>> Neighbors { get; set; }
        public List<int> Weights { get; set; }

        public Node()
        {
            this.Neighbors = new List<Node<T>>();
            this.Weights = new List<int>();
        }

        public Node(T data) : this()
        {
            this.Data = data;
        }
    }
}