0925 TIL - C# 알고리즘1

알고리즘이란 거창한게 아니라 입력을 받아 원하는 출력을 생성하기 위한 절차이다.

 

주변에 있는 물건으로 생각해보자면

음료수 자판기 같은 물건은 어떤 알고리즘으로 작동될까

 

입력은 돈이고 출력은 음료수일것이다

 

돈을 입력받으면 어떤 지폐나 동전인지 분류 한 후 총 투입 금액을 표시하고

투입 금액 내로 음료수 버튼을 활성화 하고

활성화된 음료수 버튼을 누르면

해당 음료수를 하나 투하하고

투입금액이 최소금액보다 적다면

거스름돈을 내보내고 투입금액을 0으로 만든다.

만약 반환버튼을 누른다면 투입금액만큼 반환한다.

 

를 코드로 써보자.

 

using System.Net.Http.Headers;

namespace TextRPG
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Coin oneThousand = new Coin(1000);

            Soda eyeOfSol = new Soda(700, "솔의 눈");
            Soda drPepper = new Soda(1200, "닥터 페퍼");
            Soda dejawa = new Soda(700, "데자와");
            Soda morningSunshine = new Soda(800, "아침햇살");
            List<Soda> sellList = new List<Soda>();
            sellList.Add(eyeOfSol);
            sellList.Add(drPepper);
            sellList.Add(dejawa);
            sellList.Add(morningSunshine);

            VendingMachine vender = new VendingMachine(sellList);

            while (true) 
            {
                Console.WriteLine("자판기");
                Console.WriteLine("1. 솔의눈 2. 닥터페퍼 3. 데자와 4. 아침햇살");
                Console.WriteLine("   700        1200        700        800");
                Console.WriteLine("5.반환버튼");
                Console.WriteLine("6.천원 넣기");
                int a;
                int.TryParse(Console.ReadLine(), out a);
                switch (a)
                {
                    case 1:
                        vender.BuySoda(sellList[0]); break;
                    case 2:
                        vender.BuySoda(sellList[1]); break;
                    case 3:
                        vender.BuySoda(sellList[2]); break;
                    case 4:
                        vender.BuySoda(sellList[3]); break;
                    case 5:
                        vender.returnButton = true; break;
                    case 6:
                        vender.InputCoin(oneThousand); break;
                }
                vender.ChangeMoney();
            }
        }
    }

    public class Coin
    {
        public int price;

        public Coin(int numb)
        {
            price = numb;
        }
    }

    public class VendingMachine
    {
        public int inputMoney = 0;
        public int changeMoney = 0;
        List<Soda> Sodas;
        public bool returnButton = false;
        public bool bought = false;

        public VendingMachine(List<Soda> sellList)
        {
            Sodas = sellList;
        }
        public void InputCoin(Coin coin)
        {
            Console.WriteLine($"{coin.price}원 짜리를 넣었습니다.");
            inputMoney += coin.price;
            Console.WriteLine($"현재 투입 금액은 {inputMoney}원 입니다.");
        }
        public void ChangeMoney()
        {
            int minPrice = 2000;
            if (returnButton == false)
            {
                for (int i = 0; i < Sodas.Count; i++)
                {
                    for (int j = 0; j < Sodas.Count; j++)
                    {
                        if (Sodas[i].price < Sodas[j].price)
                        {
                            minPrice = Sodas[i].price;
                        }
                    }
                }
                if (minPrice > inputMoney)
                {
                    changeMoney = inputMoney;
                    inputMoney = 0;
                    Console.WriteLine($"반환금액은 {changeMoney}원 입니다.");
                }
                else changeMoney = 0;
            }
            else
            {
                changeMoney = inputMoney;
                inputMoney = 0;
                Console.WriteLine($"반환금액은 {changeMoney}원 입니다.");
                returnButton = false;
            }
            
        }
        public void BuySoda(Soda soda)
        {
            if (inputMoney > soda.price)
            {
                inputMoney -= soda.price;
                Console.WriteLine($"{soda.name}을 구매했습니다.");
                Console.WriteLine($"현재 투입금액은 {inputMoney}원 입니다.");
            }
            else Console.WriteLine($"돈이 모자랍니다.");
        }
    }

    public class Soda
    {
        public int price;
        public string name;

        public Soda(int p, string n)
        {
            name = n;
            price = p;
        }
    }
}

짠~ 135줄~

 

나중에 코딩 능력이 상승한다면 더 짧게 쓸 수 있을까?

 

하여튼 실행해보자.

잘 작동한다.

 

2천원 넣어서 솔의눈을 사고 반환해보자.

잘 작동한다.

 

이처럼 입력에서 출력까지 가는 프로세스를 알고리즘이라고 부르며

지금 만든거는 음료수자판기(간소화) 알고리즘이다.

 

알고리즘을 효율적으로 제작할 수록 더 적은 컴퓨팅 자원(시간, 메모리)를 사용하기 때문에

효율적인 알고리즘을 고민하는 것은 필수이다.

 

효율적인 알고리즘을 만들기 위한 계산 방법이 있는데

Big O표기법에 대해 알아보자.

 

Big O 표기법은 입력한 크기에 따라 알고리즘이 얼마나 많은 시간이나 메모리를 필요로 하는지 설명한다.

 

크게 4가지로 나뉘는데

O(1) : 상수시간으로 입력의 크기에 상관없이 일정한 시간이 소요된다.

O(n) : 선형시간으로 입력의 크기에 비례한 시간이 걸린다.

O(n^2) : 이차시간으로 입력의 크기의 제곱에 비례해 시간이 걸린다.

O(log n) : 로그시간으로 입력크기 로그값에 비례하여 시간이 걸린다.

 

간단하게 생각해서 1을 입력했을 때 n + 2라는 메소드를 통해 3이라는 결과가 나온다면 상수시간

10을 입력했을 때 1~10까지의 합을 구해야한다면 입력값에 비례해 시간이 소모되므로 선형시간

10을 입력했을 때 배열 내에서 가장 작은 숫자를 구해야한다면

int[n]을 한 번 읽는 for문과 비교를 위한 for문이 중첩되어 있으므로

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (array[i] < arr[j])
        {
            min = array[i];
        }
    }
}

n * n (n^2)의 횟수만큼 연산을 진행하게되므로 이차시간이다.

 

공간 복잡도는 입력에 따른 내부 변수의 크기를 생각하면 되는데

바로 위의 최솟값 for문의 경우 입력값이 배열의 크기에 영향을 주지 않기 때문에 공간 복잡도는 O(1)이라고 본다.

 

n을 입력해서 배열값을 [n]으로 늘린다면 공간 복잡도는 O(n)이 될 것이고

[n,n]으로 늘린다면 공간복잡도는 O(n^2)가 될 것이다.

 

간단하게 요약하자면

시간복잡도

평문 1 for문 n 중첩 for문 n^2 3중첩 이상 n^3이상

공간복잡도

단순 변수 1 배열의 크기지정 n 배열의 크기지정 및 내부 배열 생성 또는 2차 배열 n^2

가 되겠다

 

이제 본격적인 알고리즘에 돌입해보자.

 

정렬 알고리즘에 대해 배워보자.

 

첫번째로는 선택정렬이다.

 

using System;

namespace TextRPG
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] { 5, 7, 4, 2, 9, 6, 8 }; //길이가 7인 배열

            for (int i = 0; i < arr.Length; i++)
            {
                int min = i; //min에 i값 저장

                for (int j = i+1; j < arr.Length; j++) //같은 수끼리 비교하지 않기 위해 i+1
                {
                    if (arr[j] < arr[min])
                    {
                        min = j; //모든 수를 비교하여 가장 작은 값을 저장
                    }
                }
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }
}

한 바퀴 한 바퀴 뜯어보자

 

첫 바퀴(i = 0) : 

최초의 min 값은 0이다.

두번째 for문에 진입하면서

arr[j] < arr[min]을 만족하는건 arr[2] = 4와 arr[3] = 2이다.

하지만 아직 두 번째 for문을 빠져나오지 못했다.

 

모든 수를 비교하기 때문에 for문을 빠져나올때 min에는 3이 들어있게 된다. (arr[3] = 2)

temp(임시변수)에 arr[0] = 5값을 저장해두고

arr[0]에 arr[3] = 2를 저장한다.

arr[3]에 arr[0] = 5를 저장하면서 첫 바퀴가 끝난다.

첫 바퀴가 끝났을 때 배열은 2, 7, 4, 5, 9, 6, 8이 된다.

 

두 바퀴(i = 1):

min 값은 1이고 두 번째 for문을 빠져나올때에는 min = 2 (arr[2] = 4)가 된다.

temp에 arr[1] = 7값을 저장하고 arr[1]에는 4를 넣고 arr[2]에는 7을 넣으면서 두바퀴가 종료된다.

이 시점에 배열은 2, 4, 7, 5, 9, 6, 8이 된다.

 

대충 어떤 방식으로 돌아가는지 눈에 보일 것이다.

min변수를 선언함으로써 i값과 별개로 가장 낮은 값이 들어있는 배열[n]에 접근하여

n을 가져와서 해당 기존 배열[i]값을 임시로 저장해둔 후 

배열[n]값을 배열[i]에 넣고 기존 배열[i]값은 배열[n]에 넣어준다.

즉 i를 사용하는 for문이 종료될 시점에는 낮은 수 부터 높은 수까지 정렬이 완료될 것이다.

이 시점에 배열은 2, 4, 5, 6, 7, 8, 9가 된다.

 

이를 선택 정렬이라고 하며 가장 낮은 수를 직접 뽑아와 자리를 바꿔가며 비교한다.

실행해보자.

 

잘 정렬된 것을 볼 수 있다.

이 경우 두번의 for문을 거치기 때문에 평균적인 시간 복잡도는 O(n^2) 공간 복잡도는 O(1)이 된다.

 

다음은 삽입 정렬이다.

 

예제를 보자.

using System;

namespace TextRPG
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

            for (int i = 1; i < arr.Length; i++) //i는 1부터 시작
            {
                int j = i - 1;
                int temp = arr[i]; //임시저장 변수

                while (j >= 0 && arr[j] > temp) //j는 0보다 크거나 같다면 && 임시저장 변수보다 크다면
                {
                    arr[j + 1] = arr[j];
                    j--;
                }

                arr[j + 1] = temp;
            }

        }
    }
}

 

이것도 한 바퀴 한 바퀴 뜯어보자.

 

첫바퀴 : i = 1,  arr[i] = 2

j = i - 1이므로 j = 0, arr[j] = 5

5 > 2는 참이므로 arr[j+1 = 1] 에 j를 넣고

j--로 -1이 되므로 while문 이탈

임시변수를 기존 arr[j]자리에 넣어준다.

이 시점에서 배열은 2, 5, 4, 6, 1, 3

 

두바퀴 : i = 2,  arr[i] = 4

j = 1, arr[j] = 5

5 > 4는 참이므로 arr[2]에 5를 넣어준다.

이 시점에서 배열은 2, 5, 5, 6, 1 ,3

다시 j = 0 arr[1] = 5

5 > 5는 거짓이므로 while문 이탈

이 시점에서 배열은 2, 5, 5, 6, 1, 3

while문 탈출하자마자 arr[j+1 = 1]에 임시저장한 4를 넣어준다.

이 시점에서 배열은 2, 4, 5, 6, 1, 3

 

중요한건 4바퀴 째 부터인데

 

네바퀴 : i = 4 arr[i] = 1

1을 temp에서 임시저장하고

j = 3, arr[j] = 6

6 > 1은 참이므로 

arr[4] = arr[3]을 통해 1자리에 6을 넣어준다.

이 시점에서 배열은 2, 4, 5, 6, 6, 3

 

while문 재실행

j = 2 arr[j] = 5

5 > 1은 참이므로

arr[3] = arr[2]

이 시점에서 배열은 2, 4, 5, 5, 6, 3

 

while문 재실행

j = 1 arr[1] = 4

4 > 1은 참이므로

arr[2] = arr[3]

이 시점에서 배열은 2, 4, 4, 5, 6, 3

 

while문 재실행

j = 0 arr[0] = 2

2 > 1은 참이므로 배열은 2, 2, 4, 5, 6, 3

 

j가 -1이라서 while문 탈출

arr[j-1 = 0] = temp = 1

이 시점에서 배열은 1, 2, 4, 5, 6, 3이 된다.

위에서는 금방 금방 연산이 되었지만

정렬이 되지 않은 부분에서 순식간에 많은 연산이 지나갔다.

 

그래서 최악의 경우에는 시간복잡도가 O(n^2)이 되지만 (6,5,4,3,2,1 순으로 되어있었다면)

이미 모두 정렬되어 있는 경우에는 O(n)이 된다. (1,2,3,4,5,6 이라면 단순 실행 후 최초의 for문을 거치고 종료)

공간복잡도는 O(1)이 된다.

 

마지막 바퀴 까지 풀어보면 3이 정확이 2와 3사이에 삽입되게 되는데

이러한 특성 때문에 삽입정렬이라 부르게 된다.

 

다른 알고리즘은 내일 공부해보도록 하자. TTE