2024.01.10 내일배움캠프 13일차 TIL C#_ProGramming(알고리즘, C# 심화)

알고리즘 특강 2번째 시간이 있었다.

역시 오늘도 중요한 내용인 스택, 큐, 정렬에 대해 학습하였다.

알고리즘은 계속해서 풀어보고 부딪쳐야지만 늘 수 있는 것 같다.

그래서 내일부터 알고리즘 문제 풀이에 들어간다! 하루에 한문제식 1시간 동안 매일 풀어야 되는 과정으로 꼭 최대한 풀어볼 수 있도록 열심히 해야겠다!

팀 과제에서 내가 맞은 부분은 전투 시작 부분으로 전투를 시작할 때 플레이하는 Player(전사)을 구현하는 것이 나의 임무이다. 역시 처음엔 어렵지 않으나 나중에 되면... ^^&

---

알고리즘 특강2

 

01. 스택(Stack)

• 원소의 삽입과 삭제가 한쪽 끝, top에서만 이루어지도록 제한되어 있는 유한 순서 리스트
• 후입선출(LIFO : Last  In First Out)
• 삽입 : Push
• 삭제 : Pop

 

namespace Stack
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Stack myStack = new Stack(5);

            myStack.Push("1");
            myStack.Push("2");
            myStack.Push("3");
            myStack.Push("4");
            myStack.Push("5");

            myStack.PrintStack();

            var str = myStack.Pop();
            Console.WriteLine("Pop : " + str);

            myStack.PrintStack();

            var str2 = myStack.Peek();
            Console.WriteLine("Peek : " + str2);

            myStack.PrintStack();

            myStack.Delete();
            Console.WriteLine("Delete");

            myStack.PrintStack();

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

        public class Stack
        {
            private string[] arr;
            private int top;

            public Stack(int maxSize)
            {
                top = -1;
                arr = new string[maxSize];
            }

            public void Push(string data)
            {
                if (top >= arr.Length - 1)
                {
                    Console.Error.WriteLine("Stack Full");
                    return;
                }

                arr[++top] = data;
            }

            public string Pop()
            {
                if (top < 0)
                {
                    Console.Error.WriteLine("Stack Empty");
                    return null;
                }

                return arr[top--];
            }

            public string Peek()
            {
                if (top < 0)
                {
                    Console.Error.WriteLine("Stack Empty");
                    return null;
                }

                return arr[top];
            }

            public void Delete()
            {
                if (top < 0)
                {
                    Console.Error.WriteLine("Stack Empty");
                    return;
                }

                top--;
            }

            public void PrintStack()
            {
                for (int i = 0; i <= top; i++)
                {
                    Console.Write(arr[i] + " ");
                }
                Console.WriteLine();
            }
        }
    }
}

02. 스택의 응용

• 리스트의 순서를 역순으로 만드는데 유용

03. 큐(Queue)

• 한쪽 끝에서는 삽입만, 또 다른 끝에서는 삭제만 하도록 제한되어 있는 유한 순서 리스트
• 선입선출(FIFO : First In First Out)
• 삽입 : Enqueue
• 삭제 : Dequeue

namespace Queue
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Queue myQueue = new Queue(5);

            myQueue.Enqueue("1");
            myQueue.Enqueue("2");
            myQueue.Enqueue("3");
            myQueue.Enqueue("4");
            myQueue.Enqueue("5");

            myQueue.PrintQueue();

            var str = myQueue.Dequeue();
            Console.WriteLine("Dequeue : " + str);

            myQueue.PrintQueue();

            var str2 = myQueue.Peek();
            Console.WriteLine("Peek : " + str2);

            myQueue.PrintQueue();

            // Queue<string> queue = new Queue<string>();
        }

        public class Queue
        {
            private int front;
            private int rear;
            private int maxSize;
            private string[] arr;

            public Queue(int maxSize)
            {
                front = 0;
                rear = -1;
                this.maxSize = maxSize;
                arr = new string[maxSize];
            }

            public bool isFull()
            {
                //if(rear >= maxSize - 1)
                //{
                //    return true;
                //}
                //else
                //  return false;

                return rear >= maxSize - 1;
            }

            public bool IsEmpty()
            {
                //if(rear < front)
                //{
                //    return true;
                //}
                //else
                //    return false;

                return rear < front;
            }

            public void Enqueue(string data)
            {
                if (isFull())
                {
                    Console.WriteLine("Queue Full");
                    return;
                }

                arr[++rear] = data;
            }

            public string Dequeue()
            {
                if (IsEmpty())
                {
                    Console.Error.WriteLine("Queue Empty");
                    return null;
                }
                return arr[front++];
            }

            public string Peek()
            {
                if (IsEmpty())
                {
                    Console.Error.WriteLine("Queue Empty");
                    return null;
                }
                return arr[front];
            }

            public void PrintQueue()
            {
                for(int i = front; i <= rear; i++)
                {
                    Console.Write(arr[i] + " ");
                }
                Console.WriteLine();
            }
        }
    }
}

04. 선형 큐의 문제점

• rear = Length - 1인 경우, 큐의 상태가 full이라고 판단하지만 반드시 Length개의 원소가 큐에 있지는 않다
• 해당 큐에서 삭제가 일어났다면 그만큼 빈 공간이 생긴다.
• 빈 공간을 없애기 위해 모든 원소들을 앞쪽으로 이동시키고 front와 rear를 재설정한다.
  • 배열의 원소가 많은 경우에 연산의 지연 문제가 심각해진다.

05. 프로그램의 평가 기준

• 원하는 결과의 생성 여부
• 시스템 명세에 따른 올바른 생행 여부
• 프로그램의 성능
• 사용법과 작동법에 대한 설명 여부
• 유지 보수의 용이성
• 프로그램의 판독 용이

06. 프로그래밍의 성능 평가

• 성능 분석(performance analysis)
  
  • 포로그램을 실행하는데 필요한 시간과 공간의 추정
• 성능 측정(performance measurement)
  • 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정

07. 공간 복잡도(space complexity)

• 프로그램을 실행시켜 완료하는데 소요되는 총 저장 공간
• Sp = Sc + Se
  • Sc : 고정 공간
    1. 명령어 공간, 단순 변수, 복합 데이터 구조와 변수, 상수
    2. 입력 크기와 무관하게 항상 필요한 공간
  • Se : 가변 공간
    1. 크기가 변하는 데이터 구조와 변수들이 필요로 하는 저장 공간
    2. 런타임 스택(runtime stack)을 위한 저장 공간
    3. 입력 크기에 따라 메모리 요구량이 달라짐

08. 시간 복잡도(time complexity)

• 프로그램을 실행시켜 완료하는데 걸리는 시간
• Tp = Tc + Te
  • Tc : 컴파일 시간
  • Te : 실행 시간
    1. 단위 명령문 하나를 실행하는데 걸리는 시간
    2. 실행 빈도수(frequency count)

09. 점근식 표기법

• 주어진 알고리즘이 있을 때, 보다 간단한 함수로 만들어 표시하는 방법
• 입력 데이터의 크기에 따라, 수행시간 혹은 사용 공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시
• 연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현합니다
  • F(n) = n^2 + 3n + 1
• Big-O : 상한표기법
  • 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠이 가능
• Big-Omega : 하한표기법
• Big-Theta

10. 시간 복잡도 그래프

• T(n) = n^2 + 3n + 1 시간 복잡도를 n^2 와 3n + 1 로 나우어 그래프로 표현
• n의 값이 증가할수록 3n + 1의 값이 전체 시간 복잡도에 끼치는 영향은 미미
• 그러므로 n의 값이 무한이 증가할수록 n^2 + 3n + 1 그래프는 최고차항인 n^2 그래프와 점금적으로 가까워짐
• 즉, n의 값이 증가할수록 최고차항 이하의 값들은 함수 증가율에 큰 영향을 끼치지 않음

11. 알고리즘 비교

• 함수의 증가율에 따른 다른 함수와 비교를 하는 것이 목표
• 최고차항을 제외한 모든 항과 최고차항의 계수는 무시
• T_1(n) = 10000n + 20000
  • n
• T_2(n) = n^2 + 3n + 1
  • n^2

12. Big-O

• F(n) = O(g(n))
• F(n) <= c * g(n)
• 즉, F(n)의 복잡도는 최악의 경우라도 g(n)보다 작거나 같다는 의미
• T_1(n) = 10000n + 20000
  • n
  • O(n)
• T_2(n) = n^2 + 3n + 1
  • n^2
  • O(n^2)

 

13. 시간 복잡도 순서

• O(1) < O(logN) < O(N) < O(NLogN) < O(N^2) < O(2^N) < O(N!)

14. 버블 정렬

• 서로 인접한 두 원소를 검사하여 오름차순으로 나열합니다.
• 구현하기 쉽고 정밀한 비교가 가능합니다.
• 모든 인덱스를 비교하므로 연산시간과 성능이 불규칙적이고 배열이 클수록 비효율적입니다

 

• A = [6, 3, 1, 7, 9, 2, 4, 5, 8]
  • 0번과 1번 인덱스(6, 3)의 데이터를 비교합니다.
• A = [3, 6, 1, 7, 9, 2, 4, 5, 8]
  • 큰 데이터(6)은 뒤로 배치합니다.
• A = [3, 6, 1, 7, 9, 2, 4,5 , 8]
  • 1번과 2번 인덱스(6, 1)의 데이터를 비교합니다.
• A = [3, 1, 6, 7, 9, 2, 4, 5, 8]
  • 큰 데이터(6)을 다시 뒤로 배치합니다.
• A = [3, 1, 6, 7, 2, 4, 5, 8, 9]
  • 반복하면 데이터가 가장 큰 인덱스(9)가 배열의 마지막으로 이동합니다.
  • 이렇게 원소 개수만큼 처음부터 다시 반복

namespace BubbleArray
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] array = new int[] { 6, 3, 1, 7, 9, 2, 4, 6, 8 };

            int temp;

            for(int i = 0; i < array.Length - 1; i++)
            {
                for(int j = 0; j < array.Length - 1; j++)
                {
                    if (array[i] == array[j + 1])
                    {
                        temp = array[i];
                        array[i] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }

            for(int i = 0;i < array.Length; i++)
            {
                Console.Write(array[i] + " ");
            }
        }
    }
}

15. 선택 정렬

• 원소를 삽입할 위치를 정해두고 어떤 원소를 삽입할지 선택합니다.
• 배열의 최솟값을 찾고 맨 앞의 인덱스와 교체하여 오름차순으로 나열합니다.
• 구현하기 쉽고 버블 정렬보다 값의 복사와 이동이 적어 비교적 빠름
• 데이터가 커질 수록 효율이 떨어지고 정렬 속도가 고정적으로 n의 제곱만큼 걸림

 

• A = [6, 3, 1, 7, 9, 2, 4, 5, 8]
  • 배열을 순차적으로 탐색합니다.
• A = [6, 3, 1, 7, 9, 2, 4, 5, 8]
  • 최솟값(1)을 찾습니다.
• A = [1, 3, 6, 7, 9, 2, 4, 5, 8]
  • 최솟값(1)을 0번 인덱스(6)의 데이터와 교체하고 0번 인덱스(1)는 정렬을 마친 것으로 간주
• A = [1, 3, 6, 7, 9, 2, 4, 5, 8]
  • 처음부터 다시 반복

namespace choiceArray
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] array = new int[] { 6, 3, 1, 7, 9, 2, 4, 6, 8 };

            int temp;
            int min;

            for(int i = 0; i < array.Length - 1; i++)
            {
                min = i;
                for(int j = i + 1; j < array.Length; j++)
                {
                    if (array[j] < array[min])
                    {
                        min = j;
                    }
                }

                temp = array[min];
                array[min] = array[i];
                array[i] = temp;
            }

            for(int i = 0; i < array.Length; i++)
            {
                Console.Write(array[i] + " ");
            }
        }
    }
}

16. 퀵 정렬

• 파벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬
• 가장 보편적으로 쓰이는 정렬
• 현재 모든 정렬 알고리즘보다 빠른 속도를 자랑한다.
• 정렬된 리스트에 대해서는 수행시간이 더 오래 걸린다.

using System.Collections.Concurrent;

namespace QuickArray
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] array = new int[] { 6, 3, 1, 7, 9, 2, 4, 6, 8 };

            QuickSort(array, 0, array.Length - 1);
        }

        static void QuickSort(int[] arr, int left, int right)
        {
            if (left >= right)
            {
                return;
            }

            int pivot = Partition(arr, left, right);

            QuickSort(arr, left, pivot - 1);
            QuickSort(arr, pivot + 1, right);
        }

        static int Partition(int[] arr, int left, int right)
        {
            int pivot = arr[right];
            int i = left - 1;

            for(int j = left; j < right; j++)
            {
                if (arr[i] < pivot)
                {
                    i++;
                    Swap(arr, i, j);
                }
            }

            Swap(arr, i, right);

            return i + 1;
        }

        static void Swap(int[] arr, int i, int j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

---

팀 과제 던전 게임 만들기

namespace spartaTextDungeon
{
    internal class DungeonGame
    {
        static void Main()
        {
            Player player = new Player("Chad", 1, 100);
            // 몬스터 객체들을 저장하는 동적 배열
            // List<T> 클래스는 제네릭 타입으로, 여기서 `T`는 저장되는 요소의 타입을 나타냄
            List<Monster> monsters = new List<Monster>
            {
                new Monster("미니언", 2, 15),
                new Monster("대포미니언", 5, 25),
                new Monster("공허충", 3, 10)
            };

            // 전투 시작
            Console.WriteLine("Battle!!\n");
            DisplayStatus(player, monsters);

            // 플레이어 공격
            PlayerAttack(player, monsters);
        }

        private static void DisplayStatus(Player player, List<Monster> monsters)
        {
            foreach (var monster in monsters)
            {
                Console.WriteLine($"{monster}");
            }
            Console.WriteLine("");
            Console.WriteLine("");
            Console.WriteLine($"[내정보]\n{player}");
        }

        private static void PlayerAttack(Player player, List<Monster> monsters)
        {
            Console.WriteLine("\n1. 공격");
        }
    }

    class Character
    {
        public string Name { get; protected set; }
        public int Level { get; protected set; }
        public int MaxHP { get; protected set; }
        public int HP { get; protected set; }       // protected set: 해당 속성을 클래스 내부와 파생 클래스에서만 수정할 수 있도록 해준다.

        public bool IsDead => HP <= 0;      // IsDead: 현재 체력이 0 이하이면 참을 반환

        public Character(string name, int level, int maxHP)
        {
            Name = name;
            Level = level;
            MaxHP = maxHP;
            HP = MaxHP;
        }

        public virtual void TakeDamage(int damage)      // TakeDamage(int damage): 캐릭터가 피해를 받을 때 호출되는 메서드
        {                                               // 현재 체력에서 피해만큼 감소시키고 체력이 음수가 되지 않도록 조정
            HP -= damage;
            if (HP < 0)
                HP = 0;
        }

        public override string ToString()
        {
            return $"Lv.{Level} {Name} (전사)\nHP {HP}/{MaxHP}";    // 캐릭터의 상태를 문자열로 반환
        }
    }

    class Player : Character
    {
        public int AttackPower { get; private set; }

        public Player(string name, int level, int maxHP) : base(name, level, maxHP) 
        {
            AttackPower = 10;   // 플레이어의 기본 공격력 설정
        }
    }

    class Monster : Character       // 클래스를 상속받아 플레이어 특화 속성을 추가
    {
        public int AttackPower { get; private set; }

        public Monster(string name, int level, int maxHP) : base(name, level, maxHP)
        {
            AttackPower = 5 * level;    // 몬스터의 공격력은 레벨에 비례하도록 설정
        }

        public override string ToString()
        {
            return $"Lv.{Level} {Name} HP {HP}";    // 몬스터의 상태를 문자열로 반환
        }
    }
}

새롭게 알게된 내용: protected set;
속성(Property)에 사용되는 접근 제한자이다.
이를 통해 해당 속성은 클래스 내부에서만 수정할 수 있으며, 파생 클래스에서도 수정이 가능하게 된다

 

이번 팀 과제의 전체 큰 흐름
1. 게임 시작 화면

2. 상태 보기

3. 전투 시작 화면

4. 플레이어가 몬스터 공격
4.1 결과 표시
----턴종료---
5. 몬스터가 플레이어 공격
5.1 결과 표시

 

6. 모든 몬스터가 Dead 상태가 된다면 게임 종료 → Victory

 

7. 내 체력이 0이 되면 게임 종료 → Lose

---

오늘의 오류

깃 허브를 사용 중 갑자기 Changes에 이상한 게 너무 많이 생겼다.
특강에서 기억한 저 문제는 I gnore을 설정하면 없어진다고 했는데 확실히 설정하는 거까지 봤었는데 왜...???
뭐가 문제인지 물어보니 파일에 gnore가 없어서 그렇다고 한다! 작업 도중에 삭제된 듯...

 

해결방법 

깃 허브 주소로 들어가 언제 삭제되었는지 확인하고 삭제된 파일을 복원 시켰다!

복원된 파일

이 파일이 작업하고 있는 프로젝트 파일 안에 있어야 gonre가 정상적으로 설정이 된다!