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

아침 9시부터 알고리즘 특강이 있었다!

개발자에겐 필수이자 중요한 자료구조와 알고리즘은 개발하는 데 있어 효율적이고 실력을 증명해 낼 수 있는 심화된 코드와 문제 해결능력을 강화시켜주기 때문에 꼭 녹여내야 하는 핵심 기술 중 하나이다!

때문에 내배캠 과정에서도 매일 같이 알고리즘에 관한 문제를 풀어야 되는 시간이 따로 있을 정도이고 매일 생각하고 매일 고민하면서 혼자 스스로 해결하여 하루에 한 문제 씩 풀어가게 될 것이다.

 

이어서 오늘부터는 C# 문법 기초 과정이 끝나고 심화 과정에 들어간다.

기초 과정은 개인 과제로 개인이 학습하여 혼자서 던전 게임을 구현했다면 심화 과정부터는 팀 단위로 학습하여 다 같이 게임을 만드는 것이다! 각자 학습 정도나 이해할 수 있는 범위 내에서 역할과 임무를 나눴고 코드를 공유하고 합쳐야 되기 때문에 깃 허브를 다시 사용하였다.

우리에 첫 번째 목표는 필수 요구사항 완벽하게 구현하기!

아직 기초 문법도 익숙하지 않은 우리 팀 이기때문에 먼저 앞서 나가기보단 필수 요구사항을 먼저 보다 완벽하게 구현할 수 있도록 하는 것이 우리 팀의 첫 번째 목표이다!

---

알고리즘 특강

 

1. 알고리즘

• 특정 문제를 해결하기 위해 기술한 일련의 명령문

2. 프로그램

• 알고리즘을 컴퓨터가 이해하고 실행할 수 있는 특정 프로그래밍 언어로 표현한 것

Program = algorthhm + data structures

 

3. 알고리즘의 요건

• 안전성과 명확성
  • 수행 단계와 순서가 완전하고 명확하게 명세되어야 함
  • 순수하게 알고리즘이 지시하는 대로 실행하기만 하면 의도한 결과가 얻어져야 함
• 입력과 출력
  • 입력 : 알고리즘이 처리해야 할 대상으로 제공되는 데이터
  • 출력 : 입력 데이터를 처리하여 얻은 결과
• 유한성
  • 유한한 단계 뒤에는 반드시 종료

4. 왜 해야 하는거지?

• 기초체력

Q. 배열 A = [3, 4, 5, 6, 7, 8, 9] 에서 숫자 8이 있는지 찾아보시오

S1. 순차적으로 하나씩 검사하기

• A[0] == 8, A[1] == 8 ...... A[5] == 8 >>>> 총 6번

S2. 배일 A가 순서대로 정렬되어 있으니 중간값을 기준으로 대소 비교

• A[length / 2] >= 8 ... True
• (A[4], A[5], A[6]) ...A[5] >= 8 ... True >>>> 총 2번

5. 배열

• 동일한 데이터 유형을 가지는 데이터 요소들을 한 번에 모아서 다룰 수 있는 구조

6. 배열의 특성

•  순차적 메모리 할당 방식
• <인덱스, 원소> 쌍의 집합 - 각 쌍은 인덱스와 그와 연관된 원소값의 대응 관계를 나타냄
• 원소들이 모두 같은 타입, 같은 크기
• 배열을 이용하면 많은 수의 변수를 하나의 문장으로 선언 가능
• 배열을 구성하는 변수에 순차적으로 접근 가능
• 배열 인스턴스의 멤버변수 length에는 배열의 길이 정보가 저장되어있다.

7. 인덱스

•  순서를 나타내는 원소의 유한 집합
• 배열 내에서 원소의 상대적인 위치를 나타냄
• 인덱스만으로 원하는 원소에 직접 접근이 가능

8. 1차원 배열 A[n]

• 연속적인 메모리 주소를 배열에 할당
• 원소는 할당된 메모리 내에서 인덱스 순서에 따라 저장

internal class Algorithm
{
    static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5 };

        Console.WriteLine(arr.Length);

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

9. 2차원 배열 A[n1, n2]

• n1 : 행(row)의 수
• n2 : 열(column)의 수

# 2차원 배열
            //int[,] arr2 = 
            //{ 
            //    { 1, 2 }, 
            //    { 3, 4 }, 
            //    { 5, 6 } 
            //};

            //Console.WriteLine(arr2.Length);
            //Console.WriteLine(arr2.GetLength(0));
            //Console.WriteLine(arr2.GetLength(1));

            //for(int i = 0; i < arr2.GetLength(0); i++) 
            //{
            //    for (int j = 0; j < arr2.GetLength(1); j++)
            //    {
            //        Console.Write(arr2[i, j] + " ");
            //    }
            //    Console.WriteLine();
            //}

10. 가변 배열 A[n][??]

• 행마다 원소 개수가 서로 다름
• 배열의 배열

internal class Algorithm
{
    static void Main(string[] args)
    {
        int[][] arr =
        {
            new int[] {1, 2, 3},
            new int[] {4, 5, 6},
            new int[] {6, 7, 8, 9},
        };

        //Console.WriteLine(arr2.Length);
        //Console.WriteLine(arr2.GetLength(0));
        //Console.WriteLine(arr2.GetLength(1));

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

11. 리스트 L = (e1, e2, .....en)

• 동적으로 크기를 조절할 수 있는 배열
•  할당한 크기가 넘어가는 경우 2배의 크기로 재할당
• List<T> list = new List<T>();

internal class Algorithm
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>();

        list.Add(1);
        list.Add(2);
        list.Add(3);
        list.Add(4);
        list.Add(5);
        list.Add(6);

        Console.Write($"1 >> Count : {list.Count} >> ");
        printList(list);

        list.Insert(2, 0);

        Console.Write($"2 >> Count : {list.Count} >> ");
        printList(list);

        list.Remove(5);

        Console.Write($"3 >> Count : {list.Count} >> ");
        printList(list);

        list.Clear();

        Console.Write($"4 >> Count : {list.Count} >> ");
        printList(list);


    }

    static void printList(List<int> list)
    {
        for(int i = 0; i < list.Count; i++)
        {
            Console.Write(list[i] + " ");
        }
        Console.WriteLine();
    }
}

12. 배열과 리스트의 차이

• 배열
  • 연속된 메모리 공간에 할당되어 접근에 빠름
  • 참조를 위한 추가 메모리 할당이 필요 없음
  • 삽입 / 삭제 시 뒤에 요소들을 이동해야 해서 비효율적
  • 크기 변경 불가
  • 메모리 재할당 불가능
• 리스트
  • 삽입 / 삭제 시 전후 노드의 참조 관계만 수정하면 되기 때문에 배열보다 비교적 효율적
  • 메모리 재사용 가능
  • 참조를 위한 메모리가 필요
  • 배열보다 실행속도가 느리다

13. 연결 리스트(Linked List)

• 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식
• 데이터 필드 - 리스트의 원소, 즉 데이터 값을 저장하는 장소
• 링크 필드 - 다른 노드의 주소값을 저장하는 장소(포인터)

14. 단일 연결 리스트

• 하나의 링크 필드를 가진 노드들이 모두 자기 후속 노드와 연결되어 있는 리스트
• 마지막 노드의 링크 필드는 리스트의 끝을 표시하는 null 값을 가짐

15. 이중 연결 리스트

• 하나의 노드가 데이터, Llik(왼쪽 링크), Rlink(오른쪽 링크) 필드를 가짐
• 양방향으로 탐색으로 탐색이 가능해서 선행 노드를 검색하기가 쉬움

internal class Algorithm
{
    static void Main(string[] args)
    {
        LinkedList list = new LinkedList();

        list.Add("사과");
        list.Add("오렌지");
        list.Add("복숭아");
        list.Add("포도");
        list.Add("샤인머스캣");
        list.Add("감");

        Console.Write("1 >> Count : " + list.Count() + " >> ");
        list.printList();

        list.AddAfter("오렌지", "체리");

        Console.Write("2 >> Count : " + list.Count() + " >> ");
        list.printList();

        list.AddBefore("샤인머스캣", "딸기");

        Console.Write("3 >> Count : " + list.Count() + " >> ");
        list.printList();
        
        list.Remove("포도");
        
        Console.Write("4 >> Count : " + list.Count() + " >> ");
        list.printList();
    }
    
    static void printList(List<int> list)
    {
        for (int i = 0; i < list.Count; i++)
        {
            Console.Write(list[i] + " ");
        }
        Console.WriteLine();

        foreach(var item in list)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();

        list.ForEach(item =>
        {
            Console.Write(item + " ");
        });
        Console.WriteLine();
    }

    public class Node
    {
        public string Data;
        public Node Next;

        public Node(string data)
        {
            Data = data;
            Next = null;
        }
    }

    public class LinkedList
    {
        private Node Head;
        
		// 새 노드를 추가
        public void Add(string newData)
        {
            Node newNode = new Node(newData);

			// 리스트가 비어있으면 헤드에 새로운 노드를 할당
            if (Head == null)
            {
                Head = newNode;
            }
            else
            {
                Node current = Head;
                // 마지막 노드를 탐색(current = last)
                while (current != null && current.Next != null)
                    current = current.Next;
                    
				// 마지막 노드 Next에 새로운 노드를 할당
                current.Next = newNode;
            }
        }
		
        // 새 노드를 중간에 삽입
        public void AddAfter(string currentData, string newData)
        {
            Node current = GetNode(currentData);
			
            // 값에 오류가 있는 경우 리턴
            if (current == null)
            {
                Console.Error.WriteLine("ERROR");
                return;
            }
            Node newNode = new Node(newData);

			// 기존 노드의 Next를 새로운 노드의 Next로 변경
            newNode.Next = current.Next;
            // 기존 노드의 Next를 새로운 노드로 할당
            current.Next = newNode;
        }
		
        // 특정 노드를 삭제
        public void Remove(string removeData)
        {
            Node removeNode = GetNode(removeData);
			
            // 값에 오류가 있는 경우 리턴
            if(removeNode == null)
            {
                Console.Error.WriteLine("ERROR");
                return;
            }
            
            // 만약 헤드를 삭제해하는 경우
            if (Head == removeNode)
            {
            	// 헤드의 Next를 헤드로 지정
                Head = Head.Next;
                removeNode = null;
            }
            else
            {
                Node current = Head;
				
                // 제거할 노드를 탐색
                while (current != null && current.Next != removeNode)
                    current = current.Next;

                if (current != null)
                {
                    current.Next = removeNode.Next;
                }
            }
        }
        
        public Node GetNode(int index)
        {
        	// 값에 오류가 있는 경우 리턴
            if (Head == null)
            {
            	// 값에 오류가 있는 경우 리턴
                Console.Error.WriteLine("ERROR");
                return null;
            }

            Node current = Head;
            
            // index만큼 노드를 탐색
            for(int i = 0; i < index; i++)
            {
                if (current != null)
                    current = current.Next;
            }

            return current;
        }

        public Node GetNode(string data)
        {
        	// 값에 오류가 있는 경우 리턴
            if(Head == null)
            {
                Console.Error.WriteLine("ERROR");
                return null;
            }

            Node current = Head;

            while (current != null)
            {
            	// data를 찾을때 까지 탐색
                if (current.Data != null && current.Data == data)
                    break;

                current = current.Next;
            }
            return current;
        }

        public int Count()
        {
            int cnt = 0;
             
            Node current = Head;

            while (current != null)
            {
                cnt++;
                current = current.Next;
            }
            return cnt;
        }

        public void printList()
        {
            Node current = Head;

            while(current != null)
            {
                Console.Write(current.Data + " ");
                current = current.Next;
            }
            Console.WriteLine();
        }
    }
}

// 이중 연결 리스트
internal class Algorithm
{
    static void Main(string[] args)\
    {	
    	...........
   	    // 이중 연결 리스트
        public class Node_D
        {
            public string Data;
            public Node_D Prev;
            public Node_D Next;

            public Node_D(string data, Node_D prev, Node_D next)
            {
                Data = data; 
                Prev = prev; 
                Next = next;
            }

            public Node_D(string data)
            {
                Data = data;
                Prev = null;
                Next = null;
            }
        }

        public class LinkedList_D
        {
            private Node_D Head;

            // 새 노드를 추가
            public void Add(string newData)
            {
                Node_D newNode = new Node_D(newData);

                // 리스트가 비어있으면 헤드에 새로운 노드를 할당
                if (Head == null)
                    Head = newNode;
                // 리스트가 비어있지 않으면
                else
                {
                    Node_D current = Head;
                    // 마지막 노드를 탐색(current = last)
                    while (current != null && current.Next != null)
                        current = current.Next;

                    // 마지막 노드 Next에 새로운 노드를 할당
                    current.Next = newNode;
                    newNode.Prev = current;
                }
            }

            public void AddAfter(string currentData, string newData)
            {
                Node_D current = GetNode(currentData);

                // 값에 오류가 있는 경우 리턴
                if (current == null)
                {
                    Console.Error.WriteLine("ERROR");
                    return;
                }

                Node_D newNode = new Node_D(newData, current, current.Next);
                current.Next.Prev = newNode;
                current.Next = newNode;
            }

            public void AddBefore(string currentData, string newData)
            {
                Node_D current = GetNode(currentData);

                // 값에 오류가 있는 경우 리턴
                if (current == null)
                {
                    Console.Error.WriteLine("ERROR");
                    return;
                }

                Node_D newNode = new Node_D(newData, current.Prev, current);
                current.Prev.Next = newNode;
                current.Prev = newNode;
            }

            // 특정 노드를 삭제
            public void Remove(string removeData)
            {
                Node_D removeNode = GetNode(removeData);

                // 값에 오류가 있는 경우 리턴
                if (removeData == null)
                {
                    Console.Error.WriteLine("ERROR");
                    return;
                }

                // 만약 헤드를 삭제해하는 경우
                if (Head == removeNode)
                {
                    // 헤드의 Next를 헤드로 지정
                    Head = Head.Next;

                    // 새로 지정된 헤드가 null이 아닐경우 헤드의 Prev를 삭제
                    if (Head != null)
                        Head.Prev = null;
                }
                else
                {
                    removeNode.Prev.Next = removeNode.Next;
                    if(removeNode.Next != null)
                        removeNode.Next.Prev = removeNode.Prev;
                }
            }

            public Node_D GetNode(int index)
            {
                // 값에 오류가 있는 경우 리턴
                if (Head == null)
                {
                    Console.Error.WriteLine("ERROR");
                    return null;
                }

                Node_D current = Head;

                // index만큼 노드를 탐색
                for (int i = 0; i < index; i++)
                {
                    if (current != null)
                        current = current.Next;
                }

                return current;
            }

            public Node_D GetNode(string data)
            {
                // 값에 오류가 있는 경우 리턴
                if (Head == null)
                {
                    Console.Error.WriteLine("ERROR");
                    return null;
                }

                Node_D current = Head;

                while (current != null)
                {
                    // data를 찾을때 까지 탐색
                    if (current.Data != null && current.Data == data)
                        break;

                    current = current.Next;
                }

                return current;
            }

            public int Count()
            {
                int cnt = 0;

                Node_D current = Head;
                while (current != null)
                {
                    cnt++;
                    current = current.Next;
                }

                return cnt;
            }

            public void printList()
            {
                Node_D current = Head;

                while (current != null)
                {
                    Console.Write(current.Data + " ");
                    current = current.Next;
                }
                Console.WriteLine();
            }
        }
    }
}

---

팀 프로젝트!

 

깃 허브 연동 (GitHub Desktop)

먼저 팀원들과 협업을 해야 하기 때문에 깃 허브를 연동하였다!

 

팀원 임무 역할

게임 시작 화면 구현 - 조기조님

> 기초 문법과 지식을 학습하면서 게임 시작 화면을 구현

상태 보기 구현 - 허아영님

> 개인 과제에서 학습하고 구현한 것을 바탕으로 상태 보기를 더욱 완벽하게 구현

전투 시작 - 나, 심선규님

> 전투 시작에 필요한 모든 과정들을 구현 (겹치는게 많이 있을 것 같음)