[C# 교과서] 14. C# 활용(8) - 알고리즘과 절차 지향 프로그래밍

알고리즘과 절차 지향 프로그래밍

 

알고리즘(algorithm)은 문제를 해결하는 일련의 절차나 방법을 공식으로 표현한 풀이법이다.

 

알고리즘

• 알고리즘은 '문제 해결 능력'이다.
• 프로그램의 가장 작은 단위는 일반적으로 입력(input) - 처리(process) - 출력(output) 단계를 거치는데, 여기서 처리 단계가 알고리즘 단계이다.

 

합계 구하기: SUM 알고리즘

using System;

class SumAlgorithm
{
    static void Main()
    {
        //[1] Input: n명의 점수
        int[] scores = { 100, 75, 50, 37, 90, 95 };
        int sum = 0; // 합계가 담길 그릇

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

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

//6명의 점수 중 80점 이상 총점 : 285

합계 알고리즘 LINQ 버전: new int[] { 100, 75, 50, 37, 90, 95 }).Where(s => s >= 80).Sum()

 

 

개수 구하기: COUNT 알고리즘

개수(COUNT) 알고리즘은 조건에 맞는 자료 개수(횟수, 건수)를 구한다.

using System;

class CountAlgorithm
{
    static void Main()
    {
        //[1] Input: 1부터 1,000까지의 데이터 
        var numbers = Enumerable.Range(1, 1_000).ToArray();
        int count = default; // 개수를 저장할 변수는 0으로 초기화

        //[2] Process: 개수 알고리즘 영역: 주어진 범위에 주어진 조건(필터링)
        for (int i = 0; i < numbers.Length; i++)
        {
            if (numbers[i] % 13 == 0) // 13의 배수면 개수 증가
            {
                //count = count + 1;
                //count += 1;
                count++; // COUNT
            }
        }

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

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

카운트 알고리즘 LINQ 버전: Enumerable.Range(1, 1_000).ToArray().Where(n => n % 13 == 0).Count()

 

 

평균 구하기: AVERAGE 알고리즘

평균(AVERAGE) 알고리즘은 자료 합계(SUM)를 횟수(COUNT)로 나누어 평균을 구한다.

using System;

class AverageAlgorithm
{
    static void Main()
    {
        //[1] 입력: n명의 성적
        int[] data = { 90, 65, 78, 50, 95 };
        int sum = 0; // 합계 담는 그릇
        int count = 0; // 개수 담는 그릇

        //[2] 처리: AVG = SUM / COUNT
        for (int i = 0; i < data.Length; i++) // 주어진 범위
        {
            if (data[i] >= 80 && data[i] <= 95) // 주어진 조건
            {
                sum += data[i]; // SUM
                count++; // COUNT
            }
        }

        double avg = 0.0f;
        if (sum != 0 && count != 0) // 예외 처리
        {
            avg = sum / (double)count; // AVERAGE
        }

        //[3] 출력
        Console.WriteLine($"80점 이상 95점 이하인 자료의 평균: {avg:0.00}"); // 92.5
    }
}

//80점 이상 95점 이하인 자료 평균 : 92.50

AVERAGE 알고리즘 LINQ 버전: (new int[] { 50, 65, 78, 90, 95 }).Where(d => d >= 80 && d <= 95).Average()

 

 

최댓값 구하기: MAX 알고리즘

최댓값(MAX) 알고리즘은 주어진 범위 내에서 가장 큰 값을 구한다.

using System;

class MaxAlgorithm
{
    static void Main()
    {
        //[1] Initialize
        int max = int.MinValue; // 정수 형식의 데이터 중 가장 작은 값으로 초기화

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

        //[3] Process: MAX
        for (int i = 0; i < numbers.Length; i++)
        {
            if (numbers[i] > max) // 더 큰 데이터가 있다면
            {
                max = numbers[i]; // MAX: 더 큰 값으로 할당 
            }
        }

        //[4] Output
        Console.WriteLine($"최댓값(식): {numbers.Max()}");
        Console.WriteLine($"최댓값(문): {max}"); // -1 
    }
}

// 최댓값(식): -1
// 최댓값(문): -1

최댓값 알고리즘 LINQ 버전: int[] numbers = { -2, -5, -3, -7, -1 }; numbers.Max()

 

 

최솟값 구하기: MIN 알고리즘

최솟값(MIN) 알고리즘은 주어진 범위 내에서 가장 작은 값을 구한다.

using System;
using static System.Console;

class MinAlgorithm
{
    static void Main()
    {
        //[1] Initialize
        var min = Int32.MaxValue; // 정수 형식의 데이터 중 가장 큰 값으로 초기화

        //[2] Input: 이진수로 표현 + 숫자 구분자 사용({ 2, 5, 3, 7, 1 })
        int[] numbers = { 0b0010, 0B_0101, 0b0011, 0B_0111, 0b0000_0001 };

        //[3] Process: MIN
        for (int i = 0; i < numbers.Length; i++)
        {
            if (numbers[i] < min && numbers[i] % 2 == 0)
            {
                min = numbers[i]; // MIN: 더 작은 값으로 할당 
            }
        }

        //[4] Output
        WriteLine($"짝수 최솟값(식): {numbers.Where(n => n % 2 == 0).Min()}");
        WriteLine($"짝수 최솟값(문): {min}");
    }
}

//짝수 최솟값(식): 2
//짝수 최솟값(문): 2

최솟값 알고리즘 LINQ 버전: numbers.Where(n => n % 2 == 0).Min()

 

 

근삿값 구하기: NEAR 알고리즘

근삿값(NEAR) 알고리즘은 주어진 값과 차이가 가장 적게 나는 값을 구한다.

using System;
using static System.Console;

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

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

        //[2] Input: 2진수와 16진수로 표현({ 10, 20, 30, 27, 17 }) 
        int[] numbers = { 0b1010, 0x14, 0b11110, 0x1B, 0b10001 }; 
        int target = 25; // target과 가까운 값
        int near = default; // 가까운 값: 27

        //[3] Process: NEAR
        for (int i = 0; i < numbers.Length; i++)
        {
            int abs = Abs(numbers[i] - target); // 차잇값의 절댓값
            if (abs < min)
            {
                min = abs; // MIN: 최솟값 알고리즘
                near = numbers[i]; // NEAR: 차잇값의 절댓값 중 최솟값일 때의 값
            }
        }

        //[4] Output
        var minimum = numbers.Min(m => Math.Abs(m - target));
        var closest = numbers.First(c => Math.Abs(target - c) == minimum);
        WriteLine($"{target}와/과 가장 가까운 값(식): {closest}(차이: {minimum})");
        WriteLine($"{target}와/과 가장 가까운 값(문): {near}(차이: {min})");
    }
}

// 25와/과 가장 가까운 값(식): 27(차이: 2)
// 25와/과 가장 가까운 값(문): 27(차이: 2)

근삿값 알고리즘 LINQ 버전: numbers.First(c => Math.Abs(c - target) == numbers.Min(m => Math.Abs(m - target)))

 

 

순위 구하기: RANK 알고리즘

순위 알고리즘은 주어진 범위의 데이터 중 지정한 범위 내에서 등수(순위)를 구하는 알고리즘이다.

using System;

class RankAlgorithm
{
    static void Main()
    {
        //[1] Input
        int[] scores = { 90, 87, 100, 95, 80 }; // 등수: 3, 4, 1, 2, 5
        int[] rankings = Enumerable.Repeat(1, 5).ToArray(); // 모두 1로 초기화

        //[2] Process: RANK
        for (int i = 0; i < scores.Length; i++)
        {
            rankings[i] = 1; // 1등으로 초기화, 순위 배열을 매 회전마다 1등으로 초기화
            for (int j = 0; j < scores.Length; j++)
            {                
                if (scores[i] < scores[j]) // 현재(i)와 나머지들(j) 비교
                {
                    rankings[i]++; // RANK: 나보다 큰 점수가 나오면 순위 1증가
                }
            }
        }

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

순위 알고리즘 LINQ 버전: scores.Select( s => scores.Where(ss => ss > s).Count() + 1).ToArray()

 

 

순서대로 나열하기: SORT 알고리즘

정렬(SORT) 알고리즘은 주어진 범위 내에서 불규칙적으로 나열된 순서를 일정 기준에 따라 순서대로 나열한다.

정렬 알고리즘의 종류로는 선택 알고리즘(selection sort), 버블 정렬(bubble sort), 퀵 정렬(quick sort)이 있다.

 

선택 정렬 알고리즘

• 선택 정렬 알고리즘은 데이터 하나를 기준으로 나머지 데이터와 비교하여 가장 작거나 큰 데이터와 자리를 바꾸는 식으로 반복해서 비교하는 정렬방법이다.
• 선택 정렬은 데이터 개수가 n개이면 전체 회전수는 n-1회이다.

예를 들어 [9, 4, 5, 11, 8]이라는 배열에서 선택 정렬 알고리즘을 적용한다고 할 때,

1회전을 거치면 [4, 9, 5, 11, 8]이 되고 2회전을 거치면 [4, 5, 9, 11, 8]이 된다.

배열의 첫번째 요소부터 순서대로 회전을 거치며, 해당 요소보다 작은 값이 나오면 값을 바꾼다.

using System;

class SortAlgorithm
{
    static void Main()
    {
        //[1] Input: Data Structure(Array, List, Stack, Queue, Tree, DB, ...)
        int[] data = { 3, 2, 1, 5, 4 }; // 정렬되지 않은 데이터
        int N = data.Length; // 의사코드(슈도코드) 형태로 알고리즘을 표현하기 위함

        //[2] Process: Selection Sort(선택 정렬) 알고리즘
        for (int i = 0; i < N - 1; i++) // i = 0 to N - 1
        { 
            for (int j = i + 1; j < N; j++) // j = i + 1 to N
            {
                if (data[i] > data[j]) // 부등호 방향: 오름차순(>), 내림차순(<)
                {
                    int temp = data[i];
                    data[i] = data[j];
                    data[j] = temp; // SWAP
                }
            }
        }

        //[3] Output: UI(Console, Desktop, Web, Mobile, ...)
        for (int i = 0; i < N; i++)
        {
            Console.Write($"{data[i]}\t");
        }
        Console.WriteLine();
    }
}

1회전: 1, 3, 2, 5, 4

2회전: 1, 2, 3, 5, 4

3회전: 1, 2, 3, 5, 4

4회전: 1, 2, 3, 4, 5

정렬(sort) 알고리즘 LINQ 버전: Array.Sort(Data) or data.OrderBy(n => n).ToArray()

 

버블 정렬 알고리즘

using System;

class BubbleSort
{
    static void Main()
    {
        //[1] Input
        int[] data = { 3, 2, 1, 5, 4 };
        int N = data.Length;

        //[2] Process: Bubble Sort(거품 정렬) 알고리즘
        for (int i = 0; i < N - 1; i++)
        {
            for (int j = 1; j < (N - i); j++)
            {
                if (data[j - 1] < data[j]) // 부등호 방향: 오름차순(>), 내림차순(<)
                {
                    int temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                }
            }
        }

        //[3] Output
        for (int i = 0; i < N; i++)
        {
            Console.Write($"{data[i]}\t");
        }
        Console.WriteLine();
    }
}

 

 

특정 값 검색하기: SEARCH 알고리즘

검색(search) 알고리즘은 배열 등 데이터에서 특정 값을 검색한다.

• 순차 검색(sequence search): 전체 데이터를 처음부터 끝까지 순서대로 검색
• 이진 검색(binary search): 정렬된 데이터를 절반으로 나누어서 검색

 

이진 검색 알고리즘

• 이진 검색 알고리즘은 주어진 데이터가 오름차순으로 정렬되어 있다고 가정한다. 만약 데이터가 정렬되어 있지 않다면, 정렬 알고리즘 등을 사용하여 정렬한 후 이진 검색 알고리즘 로직을 적용해야 한다.
• 이진 검색 알고리즘을 영어로 divide and conquer(나누기 및 정목) 알고리즘이라고도 하는데, 의미 그대로 데이터를 절반으로 나누어서 검색하여 순차 검색보다 효율이 높다.

using System;

class SearchAlgorithm
{
    static void Main()
    {
        //[1] Input
        int[] data = { 1, 3, 5, 7, 9 }; // 오름차순으로 정렬되었다고 가정
        int N = data.Length; // 의사코드
        int search = 3; // 검색할 데이터: Console.ReadLine() 등으로 가져오기
        bool flag = false; // 플래그 변수: 찾으면 true 찾지못하면 false 
        int index = -1; // 인덱스 변수: 찾은 위치

        //[2] Process: 이진 검색(Binary Search) 알고리즘: Full Scan -> Index Scan
        int low = 0; // min: 낮은 인덱스
        int high = N - 1; // max: 높은 인덱스 
        while (low <= high)
        {
            int mid = (low + high) / 2; // 중간 인덱스(mid) 구하기
            if (data[mid] == search) // 중간 인덱스에서 찾기
            {
                flag = true; index = mid; break; // 찾으면 플래그, 인덱스 저장 후 종료
            }
            if (data[mid] > search)
            {
                high = mid - 1; // 찾을 데이터가 작으면 왼쪽 영역으로 이동 
            }
            else
            {
                low = mid + 1; // 찾을 데이터가 크면 오른쪽 영역으로 이동
            }
        }

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

[1, 3, 5, 7, 9]라는 배열이 있을 때 9를 찾는 이진 검색 알고리즘의 로직을 설명해보자면

우선 배열의 첫번째 인덱스인 low, 마지막 인덱서인 high, 그리고 중간 index인 mid를 설정한다.

1회전: low = 0, high = 4, mid = (low+high)/2 = 2, mid의 데이터 값은 5이고 찾는 값은 9이다. 찾는 값이 mid의 값보다 크니까 왼쪽 영억은 버리고 오른쪽 영역만 비교하기 위해 low를 mid+1 로 변경한다.

2회전: low = 3, high = 4, mid = (low+high)/2 = 3, mid의 데이터 값은 7이고 찾는 값은 9이다. 찾는 값이 mid의 값보다 크니까 왼쪽 영역은 버리고 오른쪽 영역만 비교하기 위해 low를 mid+1로 변경

3회전: low = 4, high = 4, mid = (low+high)/2 = 4, mid의 데이터 값은 9로 찾는 값이기 때문에 검색 알고리즘 종료

 

 

배열을 하나로 합치기: MERGE 알고리즘

병합(MERGE) 알고리즘은 배열 2개를 합쳐 하나로 만든다.

using System;

class MergeAlgorithm
{
    static void Main()
    {
        //[1] Input
        int[] first = { 1, 3, 5 }; // 오름차순 정렬됨
        int[] second = { 2, 4 }; // 오름차순 정렬됨
        int M = first.Length; int N = second.Length; // M:N 관행
        int[] merge = new int[M + N]; // 병합된 배열을 담을 그릇
        int i = 0; int j = 0; int k = 0; // i, j, k 관행

        //[2] Process: MERGE
        while (i < M && j < N) // 둘 중 하나라도 배열의 끝에 도달할 때까지
        {
            if (first[i] <= second[j]) // 더 작은 값을 merge 배열에 저장
            {
                merge[k++] = first[i++]; // 작은 값 대입 후 각각의 인덱스 증가
            }
            else
            {
                merge[k++] = second[j++]; // 작은 값 대입 후 각각의 인덱스 증가
            }
        }
        while (i < M) // 첫 번째 배열이 끝까지 도달할 때까지
        {
            merge[k++] = first[i++];
        }
        while (j < N) // 두 번째 배열이 끝까지 도달할 때까지
        {
            merge[k++] = second[j++];
        }

        //[3] Output
        foreach (var m in merge)
        {
            Console.Write($"{m}\t");
        }
        Console.WriteLine();
    }
}

위 예제의 처리 조건은 다음과 같다.

• first 배열은 1 ~ M, second 배열은 1 ~ N 자료가 있다.
• merge 배열은 M + N개가 있다.
• i, j, k는 배열 첨자 변수로 사용된다.

LINQ로 데이터 병합하기: (from o in first select o).Union(from t in second select t).OrderBy(m => m).ToArray();

 

 

최빈값 구하기: MODE 알고리즘

최빈값(MODE) 알고리즘은 데이터 자체를 배열의 인덱스로 보고, 인덱스 개수(COUNT) 알고리즘을 적용하는 형태이다.

using System;

class ModeAlgorithm
{
    static void Main()
    {
        //[1] Input: 범위는 0부터 n점까지의 점수만 들어온다고 가정
        int[] scores = { 1, 3, 4, 3, 5 }; // 0~5까지만 들어온다고 가정
        int[] indexes = new int[5 + 1]; // 0~5까지 점수 인덱스의 개수 저장  
        int max = int.MinValue; // MAX 알고리즘 적용
        int mode = 0; // 최빈값이 담길 그릇

        //[2] Process: Data -> Index -> Count -> Max -> Mode
        for (int i = 0; i < scores.Length; i++)
        {
            indexes[scores[i]]++; // COUNT
        }
        for (int i = 0; i < indexes.Length; i++)
        {
            if (indexes[i] > max)
            {
                max = indexes[i]; // MAX -> 2
                mode = i; // MODE -> 3
            }
        }

        //[3] Output
        Console.WriteLine($"최빈값(문): {mode} -> {max}번 나타남");
        var q = scores.GroupBy(v => v).OrderByDescending(g => g.Count()).First();
        int modeCount = q.Count(); // 2
        int frequency = q.Key; // 3
        Console.WriteLine($"최빈값(식): {frequency} -> {modeCount}번 나타남");        
    }
}

 

 

그룹화하기: GROUP 알고리즘

그룹(GROUP) 알고리즘은 그룹별로 구분되는 데이터의 통계를 산출할 때 사용되며, 데이터가 미리 정렬되어 있어야 한다.

using System;
using System.Collections.Generic;
using System.Linq;

class GroupAlgorithm
{
    class Record
    {
        public string Name { get; set; }
        public int Quantity { get; set; }
    }

    static void Main()
    {
        //[0][1] 테스트용 데이터 채우기용 로컬 함수
        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> data)
        {
            Console.WriteLine(message);
            foreach (var item in data)
            {
                Console.WriteLine($"{item.Name,5} - {item.Quantity}");
            }
        }

        //[1] Input
        List<Record> records = GetAll(); // 입력 데이터 
        List<Record> groups = new List<Record>(); // 출력 데이터
        int N = records.Count; // 의사코드

        //[2] Process: Group 알고리즘(SORT -> SUM -> GROUP)
        //[A] 그룹 정렬: 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)
                {
                    var t = records[i]; records[i] = records[j]; records[j] = t;
                }
            }
        }

        //[B] 그룹 소계: GROUP
        int subtotal = 0; // 소계
        for (int i = 0; i < N; i++)
        {
            subtotal += records[i].Quantity; // 같은 상품명의 수량을 누적(SUM)
            if ((i + 1) == N || // 단락(short circuiting)이면 아래 조건 무시 
                (records[i].Name != records[i + 1].Name))
            {
                //[!] 다음 레코드가 없거나, 현재 레코드와 다음 레코드가 다르면 저장
                groups.Add(new Record
                {
                    Name = records[i].Name, // 한 그룹의 키(Key) 지정
                    Quantity = subtotal // 소계
                }); // 하나의 그룹 저장

                subtotal = 0; // 하나의 그룹이 완료되면 소계 초기화
            }
        }

        //[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());
    }
}

// 원본 데이터를 상품명으로 그룹화: 그룹 알고리즘
// RADIO  3           DVD    4
// TV     1    -->    RADIO  5
// RADIO  2           TV     1
// DVD    4

 

 

 

 

 

<Reference>