C#교과서 마스터하기 20. 알고리즘과 절차 지향 프로그래밍

min seung moon·2021년 7월 11일

C#

목록 보기

21/54

https://www.youtube.com/watch?v=dUr_YVBUZP0&list=PLO56HZSjrPTB4NxAsEP8HRk6YKBDLbp7m&index=51

1. 알고리즘

초급
중급
고급

// [1] Input, 자료구조
// [2] Process, 알고리즘
// [3] Output, 결과

_1. desc

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] datas = { 3, 2, 1, 5, 4 };
            /*
            foreach (int data in datas)
                WriteLine(data);
            */
            for(int i = 0; i < datas.Length; i++)
            {
                for(int j = i + 1; j < datas.Length; j++)
                {
                    if(datas[i] < datas[j])
                    {
                        int temp = datas[i];
                        datas[i] = datas[j];
                        datas[j] = temp;
                    }
                }
            }
            foreach (int data in datas)
                Write(data);
        }
    }
}

2. 합계 알고리즘(SumAlgorithm)

6명의 점수 중 80점이 이상의 총점

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {
            // [1] Input, 자료구조
            // n명의 국어 점수
            int[] score = { 100, 75, 50, 37, 90, 95};
            int sum = 0;

            // [2] Process, 알고리즘

            // LINQ 사용(식)
            // sum = score.Where(s => s >= 80).Sum();

            // 합계 알고리즘 영역 : 주어진 범위에 주어진 조건(문)
            for (int i = 0; i < score.Length; i++)
            {
                if (score[i] >= 80) sum += score[i];
            }


            // [3] Output, 결과
            WriteLine($"{score.Length}명의 점수 중 80 점 이상의 총점 : {sum}");
        }
    }
}

3. 갯수 알고리즘(CountAlgorithm)

1부터 1000까지의 정수 중 13의 배수의 개수

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {
            // [1] Input
            int[] numbers = Enumerable.Range(1, 1_000).ToArray();
            int count = 0;

            // [2] Process

            // LINQ
            // count = numbers.Count(n => n % 13 == 0);

            for(int i = 0; i <= numbers.Length; i++)
            {
                if (numbers[i] % 13 == 0) count++;
            }

            // [3] Output
            WriteLine($"1부터 1,000까지의 정수 중 13의 배수의 개수 : {count}");
        }
    }
}

4. 평균 알고리즘(AverageAlgorithm)

n명의 점수 중에서 80점 이상 95점 이하인 점수의 평균

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {
            // [1] Input
            int[] score = { 90, 65, 78, 50, 95 };
            int count = 0, sum = 0;

            // [2] Process

            // LINQ
            // average = score.Where(n => n >= 80 && n <= 95).Average();
            for(int i = 0; i < score.Length; i++)
            {
                if(score[i] >= 80 && score[i] <= 95)
                {
                    sum += score[i];
                    count++;
                }
            }
            double average = sum / (double)count; ;

            // [3] Output
            WriteLine($"{score.Length}명의 점수 중에서 80점 이상 95점 이하인 점수의 평균 : {average}");
        }
    }
}

5. 최댓값 알고리즘(MaxAlgorithm)

주어진 값 중 가장 큰 값

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {
            // [1] Initalizie
            int max = int.MinValue;

            // [2] Input
            int[] numbers = { -2, -5, -3, -7, -1 };

            // [3] Process

            // LINQ
            // max = numbers.Max();
            for(int i = 0; i < numbers.Length; i++)
            {
                if (numbers[i] > max) max = numbers[i];
            }

            // [4] Output
            WriteLine($"최댓값 : {max}");
        }
    }
}

6. 최솟값 알고리즘(MinAlgorithm)

주어진 값 중 가장 작은 값

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {
            // [1] Initalizie
            int min = int.MaxValue;

            // [2] Input
            int[] numbers = { -2, -5, -3, -7, -1 };

            // [3] Process

            // LINQ
            // min = numbers.Min();

            for (int i = 0; i < numbers.Length; i++)
            {
                if (numbers[i] < min) min = numbers[i];
            }

            // [4] Output
            WriteLine($"최솟값 : {min}");
        }
    }
}

7. 근삿값 알고리즘(NearAlgorithm)

가까운 값(차잇값의 절댓값의 최솟값)

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {
            // [0] 절댓값 구하기 로컬 함수 : Math.Abs() 함수와 동일한 기능 구현
            int Abs(int number) => (number < 0) ? -number : number;

            // [1] Initalizie
            int min = int.MaxValue; // 차잇값의 절댓값의 최솟값이 담긴 그릇

            // [2] Input
            int[] numbers = { 10, 20, 30, 27, 17 };
            int target = 25;
            int closest = 0; // 가까운 값


            // [3] Process

            // LINQ
            // 차잇값의 최솟값
            // min = numbers.Min(m => Math.Abs(m - target));
            // 근삿값
            // closest = numbers.First(n => Math.Abs(n - target) == minimum);

            for (int i = 0; i < numbers.Length; i++)
            {
                int abs = Abs(numbers[i] - target); // 차잇값의 절대값
                if(abs < min)
                {
                    min = abs;
                    closest = numbers[i];
                }
            }

            // [4] Output

            WriteLine($"{target}와 가장 가까운 값 : {closest}(차이 : {min})");
        }
    }
}

8. 순위 알고리즘(RankAlgorithm)

주어진(지정한 범위) 데이터의 순위를 구하는 로직

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {

            // [1] Input
            int[] scores = { 90, 87, 100, 95, 80 };
            int[] ranks = Enumerable.Repeat(1, scores.Length).ToArray();
            // [2] Process

            // LINQ
            // ranks = scores.Select(s => scores.Where(ss => ss > s).Count() + 1).ToArray();

            for(int i = 0; i < scores.Length; i++)
            {
                for (int j = 0; j < scores.Length; j++)
                {
                    if (scores[i] < scores[j]) ranks[i]++;
                }
            }

            // [3] Output
            for (int i = 0; i < ranks.Length; i++)
            {
                WriteLine($"{scores[i], 3}점 : {ranks[i]}등");
            }
        }
    }
}

10. 정렬 알고리즘(SortAlgorithm)

Selection Sort(선택 정렬) 알고리즘
무작위 데이터를 순서대로 [오름차순|내림차순] 정렬

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {

            // [1] Input
            int[] datas = { 3, 2, 1, 4, 5 };
            int N = datas.Length; // 의사코드(슈도코드) 형태로 알고리즘을 표현하기 위함
            // [2] Process

            // LINQ
            
            for(int i = 0; i < N; i++)
            {
                for(int j = i+1; j < N; j++)
                {
                    if(datas[i] > datas[j])
                    {
                        int temp = datas[i];
                        datas[i] = datas[j];
                        datas[j] = temp;
                    }
                }
            }

            // [3] Output
            // Array.Sort(datas);
            Write("오름차순 : ");
            for (int i = 0; i < datas.Length; i++)
            {
                Write($"{datas[i]}, ");
            }
            WriteLine();

            for (int i = 0; i < N; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    if (datas[i] < datas[j])
                    {
                        int temp = datas[i];
                        datas[i] = datas[j];
                        datas[j] = temp;
                    }
                }
            }

            // Array.Reverse(datas);
            Write("내림차순 : ");
            for (int i = 0; i < datas.Length; i++)
            {
                Write($"{datas[i]}, ");
            }
        }
    }
}

11. 검색 알고리즘(SearchAlgorithm)

순차 검색, 이진 검색
정렬되어 있는 데이터를 이진 검색을 사용하여 반씩 나눠서 검색

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {

            // [1] Input
            int[] datas = { 1, 3, 5, 7, 9 }; // 오름차순으로 정렬되었다고 가정
            int N = datas.Length;
            int search = 3;
            bool flag = false; // 플래그 변수: 찾으면 true, 찾지 못하면 false
            int index = -1;

            // [2] Process
            int low = 0; // min : 낮은 인덱스
            int high = N - 1; // max : 높은 인덱스

            while(low <= high)
            {
                int mid = (low + high) / 2;
                if(datas[mid] == search)
                {
                    flag = true;
                    index = mid;
                    break;
                }else if(datas[mid] > search)
                {
                    high = mid - 1;
                }else
                {
                    low = mid + 1;
                }
            }

            // LINQ || lamda
            // index = datas.ToList().BinarySearch(search);


            // [3] Output
            if (flag)
            {
                WriteLine($"{search}을(를) {index}위치에서 찾았습니다.");
            }
            else
            {
                WriteLine($"찾지 못했습니다");
            }
        }
    }
}

12. 병합 알고리즘(MergeAlgorithm, 병합 정렬)

오름차순으로 정렬되어 있는 정수 배열을 하나로 병합
2개의 정수 배열 합치기, 단 2개의 배열은 오름차순으로 정렬되어 있다고 가정

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {

            // [1] Input
            int[] first = { 1, 3, 5 };
            int[] second = { 2, 4 };
            int M = first.Length, N = second.Length; // M:N 관행
            int[] merge = new int[M + N];
            int i = 0, j = 0, k = 0;

            // [2] Process

            // LINQ || lamda || query expression
            // merge = (from o in first select o).Union(from t in second select t).OrderBy(m => m).ToArray();
            // merge = first.Union(second).OrderBy(m => m).ToArray();

            while(i < M && j < N)
            {
                if (first[i] < second[j])
                {
                    merge[k++] = first[i++];
                }
                else
                {
                    merge[k++] = second[j++];
                }
            }
            while(i < M) // first 배열의 데이터를 전부 전달했는지 확인
            {
                merge[k++] = first[i++];
            }
            while (j < N) // second 배열읟 ㅔ이터를 전부 전달했는지 확인
            {
                merge[k++] = second[j++];
            }


            // [3] Output
            foreach (int m in merge)
            {
                Write($"{m}\t");
            }
        }
    }
}

13. 최빈값 알고리즘(ModeAlgorithm)

주어진 데이터에서 가장 많이 나타난 값
점수 인덱스(0 ~ n)의 개수(Count)의 최댓값(Max)

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        static void Main(string[] args)
        {

            // [1] Input
            int[] datas = { 1, 3, 4, 3, 5 }; // 0 ~ 5까지만 들어온다고 가정
            int[] indexes = new int[6]; // 0 ~ 5까지 점수 인덱스의 갯수
            int count = int.MinValue; // MAX 알고리즘 적용
            int mode = 0; // 최빈값이 담긴 그룻

            // [2] Process

            // LINQ || lamda || query expression
            // var q = datas.GroupBy(d => d).OrderByDescending(g => g.Count()).First();
            // count = q.Count();
            // mode = q.Key;

            
            foreach(int d in datas)
            {
                indexes[d]++;
            }
            for(int i = 0; i < indexes.Length; i++)
            {
                if(indexes[i] > count)
                {
                    mode = i;
                    count = indexes[i];
                }
            }
            

            // [3] Output
            WriteLine($"최빈값 : {mode} - {count}번 나타남");
        }
    }
}

14. 그룹 알고리즘(GroupAlgorithm)

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace testProject
{
    class Program
    {
        // Test Class
        class Record
        {
            // 상품명
            public string Name { get; set; }
            // 수량
            public int Quantity { get; set; }
        }
        static void Main(string[] args)
        {
            // [0][1]local function, 테스트용 데이터 채우기용
            List<Record> GetAll()
            {
                return new List<Record>
                {
                    new Record{Name = "RADIO", Quantity = 3},
                    new Record{Name = "TV", Quantity = 1},
                    new Record{Name = "RADIO", Quantity = 2},
                    new Record{Name = "DVD", Quantity = 4}
                };
            }

            // [0][2] 컬렉션 데이터 출력용 로컬 함수
            void PrintData(string message, List<Record> datas)
            {
                WriteLine(message);
                foreach(Record data in datas)
                {
                    WriteLine($"{data.Name,5} - {data.Quantity}");
                }
            }

            // [1] Input
            List<Record> records = GetAll();
            List<Record> groups = new List<Record>();
            int N = records.Count();

            // [2] Process (Sort -> Sum -> Group)
            // [Sort] 그룹 정렬
            for(int i = 0; i < N - 1; i++)
            {
                for(int j = i + 1; j < N; j++)
                {
                    if(String.Compare(records[i].Name, records[j].Name) > 0)
                    {
                        Record temp = records[i];
                        records[i] = records[j];
                        records[j] = temp;
                    }
                }
            }

            // [Group] 그룹 소계
            int subTotal = 0; // 소계를 담을 그릇
            for (int i = 0; i < N; i++)
            {
                subTotal += records[i].Quantity; // [Sum] 합계
                if((i + 1) == N || (records[i].Name != records[i+1].Name))
                {
                    groups.Add(new Record { Name = records[i].Name, Quantity = subTotal });
                    subTotal = 0;
                }
            }

            // LINQ || lamda || query expression


            // [3] Output
            PrintData("[1]원본 데이터", records);
            PrintData("[2]이름으로 그룹화된 데이터", groups);
            PrintData("[3]LINQ로 그룹화된 데이터", records.GroupBy(r => r.Name)
                                                        .Select(g => new Record { Name = g.Key, Quantity = g.Sum(n => n.Quantity) }).ToList());
        }

    }
}