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

  • 219 minutes to read

알고리즘(Algorithm)은 문제를 해결하기 위한 일련의 절차나 방법을 공식으로 표현한 풀이법입니다. 이번 강의에서는 배우기 쉬운 몇 가지 알고리즘을 소개합니다. 지금까지 배운 C/C#/Java 기능을 기반으로 몇몇 문제를 해결하는 코드를 작성해보겠습니다. 알고리즘을 바탕으로 입력 → 처리 → 출력 단계로 진행되는 절차 지향 프로그래밍 기법도 함께 정리할 것입니다.

> // 알고리즘(Alrogithm): 문제 해결을 위한 일련의 절차나 방법을 공식으로 표현한 풀이법

알고리즘(Algorithm)

알고리즘(풀이법)이란 프로그래밍할 때 생긴 문제의 해결 방법을 체계적으로 정리한 것이라고 볼 수 있습니다. 주어진 문제를 어떻게 풀이하는지에 따라 문제를 해결할 수도 있고 그렇지 못할 수도 있습니다. 이런 이유로 프로그램 작성에서 알고리즘은 중요한 자리를 차지하고 있습니다.

  • 알고리즘은 문제 해결 능력입니다.

  • 프로그램의 가장 작은 단위는 일반적으로 입력(Input) -> 처리(Process) -> 출력(Output) 단계를 거치는데, 여기서 처리 단계가 알고리즘 단계라고 생각하면 됩니다.

    • 입력: 자료 구조(Data Structure)가 담당하는 영역입니다. 변수 및 배열의 데이터가 사용되고 더 나아가서는 컬렉션, 파일, 데이터베이스의 데이터가 사용되는 영역입니다.
    • 처리: 알고리즘 처리 영역입니다.
    • 출력: 화면으로 보여지는 UI(User Interface)를 담당하는 영역입니다. 일반적으로 콘솔, 데스크톱, 웹, 모바일 등의 영역으로 나누어서 가공된 데이터가 출력됩니다.

순서도(FlowChart)

알고리즘을 정해진 기호로 표시한 것을 순서도(흐름도)라고 합니다. 단, 이 강의에서는 따로 순서도는 다루지 않습니다. 만약, 응용 프로그램 제작이 아닌 정보처리기사와 같은 자격증 취득이 목적이라면 순서도가 그때에는 필요할 수 있습니다.

알고리즘의 다섯 가지 주요 특성

알고리즘을 설명할 때 일반적으로 다섯 가지 주요 특성을 강조합니다. 이들은 알고리즘의 정의와 효율성을 평가하는 데 중요한 기준입니다:

  1. 입력(Input, 인풋): 모든 알고리즘은 외부에서 제공받는 0개 이상의 입력을 필요로 합니다. 이 입력은 알고리즘의 작동에 필수적인 데이터입니다.

  2. 출력(Output, 아웃풋): 하나 이상의 출력을 생성해야 합니다. 이 출력은 주어진 입력에 대해 계산된 결과를 나타냅니다. 알고리즘은 문제에 대한 해결책을 제공하는 것을 목표로 하며, 이 결과는 최종적인 출력 형태로 나타납니다.

  3. 명확성(Definiteness, 데피니트니스): 알고리즘의 각 단계는 명확하고 구체적이어야 합니다. 알고리즘 내의 명령은 모호하지 않고, 실행 가능한 명확한 지시로 구성되어야 합니다. 이는 알고리즘을 읽는 모든 사람이나 시스템이 동일하게 이해하고 실행할 수 있도록 합니다.

  4. 유한성(Finiteness, 파이니트니스): 알고리즘은 유한한 수의 단계 후에 종료되어야 합니다. 무한 루프에 빠지지 않고, 결국에는 결과를 반환하며 멈춰야 합니다.

  5. 효과성(Effectiveness, 이펙티브니스): 알고리즘의 각 명령은 기본적이고 실행 가능해야 하며, 각 단계는 충분히 간단하여 종이와 연필을 사용하여 수행할 수 있을 정도로 기본적인 연산으로 구성되어야 합니다. 즉, 각 단계는 컴퓨터에 의해 정확하고 효율적으로 수행될 수 있어야 합니다.

이 다섯 가지 특성은 알고리즘이 효율적이고 정확하며, 실제 문제 해결에 적용 가능함을 보장합니다.

학습용 쉬운 알고리즘

가장 처음에 배워야 하는 학습용 쉬운 알고리즘은 주어진 자료를 가지고 가장 큰 값을 구하거나(최댓값), 가장 작은 값을 구하거나(최솟값), 합을 구하거나(누적합), 자료수를 구하거나(횟수, 건수), 평균을 구하거나(평균), 순서대로 정렬하거나(정렬) 등이 있습니다.

다음 표는 박용준 강사가 생각하는 알고리즘 입문용으로 가장 적합한 내용을 정리해 보았습니다.

표: 학습하기 쉬운 기초 알고리즘

난이도 . 알고리즘 . 사용 유형
초급 . 합계(SUM) . 합계를 출력하시오.
개수(COUNT; 횟수, 건수) . 자료 건수를 출력하시오.
평균(AVERAGE) . 평균을 출력하시오.
최댓값(MAX) . 최댓값을 출력하시오.
최솟값(MIN) . 최솟값을 출력하시오.
중급 최댓값(MAX)→최솟값(MIN) . ~에 대해서 최댓값을 구하되, 동일값이 발생했을 때 ~에 대해서 최솟값을 구하시오.
최솟값(MIN)→최댓값(MAX) ~대해서 최솟값을 구하되, 동일값이 발생했을 때 ~에 대해서 최댓값을 구하시오.
최댓값(MAX)→최댓값(MAX) ~에 대해서 최댓값을 구하되, 동일값이 발생했을 때 ~에 대해서 최댓값을 구하시오.
최솟값(MIN)→최솟값(MIN) ~에 대해서 최솟값을 구하되, 동일값이 발생했을 때 ~에 대해서 최솟값을 구하시오.
최댓값(MAX)-최솟값(MIN) ~에 대해서 최댓값과 최솟값을 구하고, 최댓값과 최솟값의 차를 구하시오.
고급 . 근삿값(NEAR) ~에 가장 가까운 값을 구하시오.
순위(RANK) 순위를 구하시오.
정렬(SORT):오름차순 ~에 대해서 오름차 순 정렬하시오.
정렬(SORT):내림차순 ~에 대해서 내림차 순 정렬하시오.
검색(SEARCH) 자료를 검색하시오.
병합(MERGE) 2개의 배열을 하나의 배열로 합치시오.
최빈값(MODE) 빈도수가 높은 자료를 구하시오.
그룹(GROUP) 항목별 그룹화하여 소계를 구하시오.

앞으로 기초 알고리즘 12개를 학습할텐데요. 모든 코드는 부록의 '디버거 사용하기'를 참고하여 중단점과 함께 [F5]와 [F10] 또는 [F11]을 사용하여 줄 단위로 코드를 실행하면서 코드의 흐름을 익히는 것을 권장합니다.

콘솔 프로젝트 만들기 복습

(이미 콘솔 프로젝트를 만드는 과정에 익숙하다면 다음 절인 합계(SUM) 구하기로 이동하세요. 이 콘솔 프로젝트 만들기 복습 내용은 알고리즘만 따로 강의할 때 사용하려고 임시로 넣어놓은 부분입니다.)

.NET 9.0 콘솔 프로젝트 생성

이미 c# 기초 입문 과정에서 여러 번 설명했지만, Visual Studio 2022와 Visual Studio Code를 사용한 .NET 9.0 기반의 콘솔 프로그램 프로젝트 생성 및 실행 과정에 대해 요약 설명합니다.

Visual Studio 2022를 사용한 방식:

1.1 프로젝트 생성:

Visual Studio 2022를 실행하고 "새 프로젝트 만들기"를 선택합니다. 프로젝트 템플릿 목록에서 ".NET 9.0 콘솔 애플리케이션(C#)"을 선택하고, "다음"을 클릭합니다. 프로젝트의 이름, 위치, 솔루션 이름을 설정한 후 "만들기"를 클릭하여 프로젝트를 생성합니다.

1.2 프로젝트 실행:

생성된 프로젝트를 열고, 솔루션 탐색기에서 "Program.cs" 파일을 찾습니다. "Program.cs" 파일을 열어 "Main" 메서드를 확인합니다. 상단의 툴바에서 "디버그 시작"을 클릭하거나 F5 키를 눌러 프로젝트를 실행합니다. 프로젝트가 실행되면, 콘솔 창이 열리고 "Hello, World!" 메시지가 출력됩니다.

Visual Studio Code와 dotnet CLI를 사용한 방식:

2.1 프로젝트 생성:

터미널을 열고 원하는 프로젝트 위치로 이동합니다.

다음 명령어를 입력하여 콘솔 프로젝트를 생성합니다.

dotnet new console --output MyConsoleApp

생성된 "MyConsoleApp" 폴더로 이동합니다.

cd MyConsoleApp

2.2 Visual Studio Code 실행:

현재 위치에서 Visual Studio Code를 실행합니다.

code .

Visual Studio Code가 열리면, 파일 탐색기에서 "Program.cs" 파일을 찾습니다.

"Program.cs" 파일을 열어 "Main" 메서드를 확인합니다.

2.3 프로젝트 실행:

Visual Studio Code에서 터미널을 엽니다. (단축키: Ctrl+`)

다음 명령어를 입력하여 프로젝트를 실행합니다.

dotnet run

프로젝트가 실행되면, 터미널에 "Hello, World!" 메시지가 출력됩니다.

이렇게 Visual Studio 2022와 Visual Studio Code를 사용한 두 가지 방식으로 .NET 9.0 기반의 콘솔 프로그램 프로젝트를 생성하고 실행할 수 있습니다. 각 방식에 따라 원하는 개발 환경을 선택하여 프로젝트를 진행하세요.

학습자 입장에서는 무조건 Visual Studio 2022 사용 방식을 추천합니다.

하나의 프로젝트에 여러 Main 메서드 만들고 실행하기

먼저, .NET 9.0 기반의 콘솔 프로젝트를 만들고 여러 개의 .cs 파일과 Main 메서드를 만들고 알고리즘 관련 파일들을 모아놓고자 하면 다음과 같은 과정을 진행하시면 됩니다.

콘솔 프로젝트 생성하기:

Visual Studio에서 새로운 프로젝트를 생성합니다. 이때 프로젝트 유형으로 ".NET 9.0 콘솔 애플리케이션(C#)"을 선택합니다.

알고리즘 폴더 만들기:

프로젝트 우클릭 후 "새 폴더"를 선택하여 "Algorithms"라는 이름의 폴더를 생성합니다.

클래스 파일 만들기:

"Algorithms" 폴더를 우클릭하고 "추가" -> "새 항목"을 선택하여 새로운 클래스 파일을 만듭니다. 예를 들어 "SumAlgorithm.cs"라는 이름으로 파일을 생성합니다. 이 파일에 Main 메서드를 추가합니다.

여러 클래스 파일에 Main 메서드 추가하기:

위의 과정을 반복하여 여러 개의 클래스 파일을 만들고 각각에 Main 메서드를 추가합니다.

이제 프로젝트 속성의 시작 개체 설정을 통해 다른 클래스의 Main 메서드를 실행하려면 다음과 같이 진행합니다.

프로젝트 속성으로 이동:

프로젝트를 우클릭하고 "속성"을 선택하여 프로젝트 속성 창으로 이동합니다.

시작 개체 설정하기:

"응용 프로그램" 탭에서 "시작 개체" 드롭다운 메뉴에서 원하는 클래스의 Main 메서드를 포함하는 클래스를 선택합니다. 예를 들어, "SumAlgorithm"을 선택하면 해당 클래스의 Main 메서드가 실행됩니다. 주의: Main 메서드가 두 개 이상 있는 경우, 프로젝트에서 기본 Main 메서드를 실행하려면 시작 개체 설정을 변경해야 합니다.

강의 소스에 대한 다운받은 알고리즘 소스 파일을 프로젝트에 추가하려면 다음과 같이 진행합니다.

다운받은 알고리즘 파일을 "Algorithms" 폴더에 복사합니다.

Visual Studio의 솔루션 탐색기에서 "Algorithms" 폴더를 우클릭하고 "추가" -> "기존 항목"을 선택하여 복사한 알고리즘 파일들을 프로젝트에 추가합니다.

시작 개체 설정이 "(설정 안함)"으로 나올 경우, 다음과 같은 원인과 해결 방법이 있습니다.

원인:

프로젝트가 올바르르게 로드되지 않았거나, Main 메서드가 포함된 클래스가 없을 수 있습니다.

해결 방법:

프로젝트를 닫았다가 다시 열어보세요. Visual Studio가 프로젝트 정보를 올바르게 읽어들일 수 있도록 합니다.

프로젝트 내의 모든 .cs 파일을 확인하여 각 클래스에 정상적으로 Main 메서드가 포함되어 있는지 확인하세요. 만약 없다면, 각 클래스 파일에 다음과 같은 Main 메서드를 추가합니다.

public static void Main(string[] args)
{
    // 코드를 작성하세요.
}

프로젝트를 빌드한 후 다시 프로젝트 속성으로 이동하여 "시작 개체" 드롭다운 목록을 확인하세요. 이제 드롭다운 목록에 Main 메서드가 포함된 클래스가 나타나야 합니다.

만약 여전히 문제가 해결되지 않는다면, Visual Studio를 완전히 종료한 후 다시 시작하여 프로젝트를 로드해 보세요. 이렇게 함으로써 프로젝트 정보가 새롭게 로드되어 문제가 해결될 수 있습니다.

이 모든 단계를 완료한 후에도 문제가 해결되지 않으면, 프로젝트를 새로 만들어 보세요. 프로젝트 파일에 문제가 있을 수 있으므로, 새로운 프로젝트를 생성하고 알고리즘 파일을 복사하여 프로젝트를 다시 시작하는 것이 좋습니다.

프로젝트 하나에 단 하나의 Main 메서드만 만들기 추천

강의 소스에서는 하나의 프로젝트에 여러 Main 메서드를 포함하고 있지만, 각 알고리즘에 대해 학습할 때는 하나의 프로젝트에 하나의 Main 메서드만 두는 것이 좋습니다. 이렇게 하면 각각의 알고리즘에 집중할 수 있고, 프로젝트 관리가 더 쉬워집니다. Sum, Count, ..., Group 알고리즘을 학습하는 경우 아래와 같은 방법을 따르는 것이 좋습니다.

Visual Studio에서 새로운 프로젝트를 생성합니다. 이때 프로젝트 유형으로 ".NET 9.0 콘솔 애플리케이션(C#)"을 선택합니다. 예를 들어, "SumAlgorithm"이라는 이름으로 프로젝트를 생성할 수 있습니다.

생성한 프로젝트에 해당 알고리즘을 구현하는 클래스 파일을 추가합니다. 예를 들어, "SumAlgorithm.cs"라는 이름으로 파일을 생성하고, 해당 파일에 Main 메서드를 추가합니다.

public static void Main(string[] args)
{
    // Sum 알고리즘 구현 코드를 작성하세요.
}

이후 다른 알고리즘을 학습하려면 새로운 프로젝트를 생성하고, 해당 알고리즘을 구현하는 클래스 파일을 추가합니다. 예를 들어, "CountAlgorithm"이라는 이름의 프로젝트를 생성하고, "CountAlgorithm.cs" 파일에 Main 메서드를 추가합니다.

public static void Main(string[] args)
{
    // Count 알고리즘 구현 코드를 작성하세요.
}

각각의 프로젝트에는 하나의 Main 메서드만 포함되므로, 알고리즘을 테스트하려면 해당 프로젝트를 실행하기만 하면 됩니다. 프로젝트를 실행하면 해당 알고리즘의 Main 메서드가 호출되어 결과를 확인할 수 있습니다.

이렇게 각 알고리즘을 별도의 프로젝트로 구성하면 코드 관리가 쉬워지고, 각 알고리즘에 집중할 수 있습니다. 각 프로젝트는 독립적으로 실행되므로, Main 메서드 간의 충돌 문제도 발생하지 않습니다. 또한, 필요한 경우 알고리즘별로 서로 다른 참조나 설정을 적용할 수 있습니다. 이 방식을 사용하여 Sum, Count, ..., Group 알고리즘을 차례대로 학습하시기 바랍니다.

합계(SUM) 구하기

합계(SUM) 알고리즘

합계(SUM)는 조건에 맞는 자료의 합계를 구하는 알고리즘입니다. 관련 데이터를 모두 더하거나 조건에 맞는 데이터를 더할 때 사용되는 구문입니다.

[실습] 합계(SUM) 알고리즘 사용하기

주어진 범위의 데이터를 사용하여 데이터의 합계를 구하는 합계 알고리즘을 적용해보는 예제를 만들어 봅시다.

코드: SumAlgorithm.cs

// SumAlgorithm.cs
//[?] n명의 국어 점수 중에서 80점 이상인 점수의 합계
using System;

/// <summary>
/// 합계 알고리즘(Sum Algorithm): 주어진 범위에 주어진 조건에 해당하는 자료들의 합계
/// </summary>
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() 
285

정보처리기능사 실기 문제: 연속된 수의 합계와 카운트 출력

파일명: ContinuousSum.cs

다음 C# 코드는 1부터 10까지의 수를 더하는 간단한 프로그램입니다. 이 코드는 for 반복문을 활용하여 변수 num의 값을 1부터 10까지 증가시키면서, 각 단계에서 변수 total에 num의 값을 누적합니다.

using System;

class ContinuousSum
{
    static void Main(string[] args)
    {
        int num, total = 0;
        for (num = 1; num <= 10; ++num)
        {
            total += num;
        }
        Console.WriteLine("{0}, {1}", num, total);
    }
}

문제 설명:

  • 위 ContinuousSum.cs 파일에 작성된 C# 코드를 실행했을 때의 출력 결과를 예측하세요.
  • 코드는 변수 num을 1부터 시작하여 10까지 증가시키며, 각 반복에서 total 변수에 num의 값을 더합니다. 반복문이 종료되면, num과 total의 최종 값을 출력합니다.

정답 예측:

  • for 반복문이 완료되면, num는 11이 됩니다(반복문의 조건 num <= 10에 의해 11에서 멈춤).
  • total은 1부터 10까지의 수의 합계인 1 + 2 + 3 + ... + 10 = 55가 됩니다.
  • 따라서 출력 결과는 11, 55입니다.

이 문제는 C#에서 for 반복문을 사용한 연속된 수의 합계 계산 및 반복 횟수 카운팅을 통해 프로그래밍의 기본적인 논리 구조와 변수 사용법을 이해하는 데 중점을 둡니다.

수열 알고리즘

수학에서 배운 수열의 여러가지 내용을 코드로 옮겨보세요.

1 - 2 + 3 - 4 + 5 - 6 + 7 =

1! + 3! + 5! + 7! =

특별한 수열의 합 구하기: 1-2+4-7+11-16+22

31.4. 개수(COUNT) 구하기

31.4.1. 개수(COUNT; 건수, 카운트) 알고리즘

개수(COUNT) 알고리즘은 조건에 맞는 자료의 개수(횟수, 건수)를 구하는 알고리즘입니다. 다른 표현 방식으로 조건에 맞는 레코드의 횟수를 구하는 데 사용되는 구문입니다.

31.4.2. [실습] 개수(COUNT) 알고리즘 사용하기

주어진 범위의 데이터 중 주어진 조건을 만족하는 데이터의 개수를 구하는 COUNT 알고리즘을 적용해보는 예제를 만들어 봅시다.

*** 예제: 1부터 1,000까지의 정수 중 13의 배수의 개수***

코드: CountAlgorithm.cs

//[?] 1부터 1,000까지의 정수 중 13의 배수의 개수(건수, 횟수)
using System;
using System.Linq;

/// <summary>
/// 개수 알고리즘(Count Algorithm): 주어진 범위에 주어진 조건에 해당하는 자료들의 개수 
/// </summary>
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)
            {
                //count = count + 1;
                //count += 1;
                count++; // COUNT
            }
        }

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

1부터 1,000까지의 정수 중 13의 배수의 개수: 76

개수 알고리즘은 간단히 증감 연산자를 사용하여 카운트를 세는 방법으로 구할 수 있습니다. 카운트 알고리즘도 LINQ를 사용하면 다음처럼 간단히 표현할 수 있습니다.

> Enumerable.Range(1, 1000).Where(n => n % 13 == 0).Count()
76
> Enumerable.Range(1, 1000).Count(n => n % 13 == 0)
76

인수 개수 구하기

1부터 n까지 정수를 나눴을 때 나누어 떨어지는 수들의 개수를 구하는 프로그램

평균(AVERAGE) 구하기

평균(AVR) 알고리즘

평균 알고리즘은 자료의 합계(SUM)를 횟수(COUNT)로 나눠 평균을 구하는 알고리즘입니다. 평균값(누적합 / 카운터)을 구하고자 할 때 사용합니다.

[실습] 평균(AVERAGE) 알고리즘 사용하기

주어진 범위의 데이터를 사용하여 데이터의 합계와 개수를 구한 후, 이를 사용하여 평균 알고리즘을 적용해 평균을 구하는 예제를 만들어 봅시다.

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

코드: AverageAlgorithm.cs

//[?] n명의 점수 중에서 80점 이상 95점 이하인 점수의 평균
using System;

/// <summary>
/// 평균 알고리즘(Average Algorithm): 주어진 범위에 주어진 조건에 해당하는 자료들의 평균
/// </summary>
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

평균 알고리즘의 특징은 이미 앞서 학습한 합계와 카운트 알고리즘을 조합해서 사용하는 것입니다. 이처럼 많은 알고리즘이 이미 있는 기능을 조합하거나 확장해서 만들어 나갑니다.

평균 알고리즘을 LINQ로 표현하면 다음과 같이 한 줄이면 충분합니다.

> (new int[] { 50, 65, 78, 90, 95 }).Where(d => d >= 80 && d <= 95).Average()
92.5

최댓값(MAX) 구하기

최댓값(MAX) 알고리즘

주어진 범위 내에서 가장 큰 값을 구하는 알고리즘입니다. 즉, 관련 데이터 중에서 가장 큰 값을 구하는 데 사용됩니다.

31.6.2. [실습] 최댓값(MAX) 알고리즘 사용하기

최댓값 알고리즘을 적용해 주어진 범위의 데이터 중 가장 큰 값을 구하는 예제를 만들어 봅시다.

예제: 주어진 데이터 중에서 가장 큰 값

코드: MaxAlgorithm.cs

//[?] 주어진 데이터 중에서 가장 큰 값
using System;
using System.Linq;

/// <summary>
/// 최댓값 알고리즘(Max Algorithm): (주어진 범위 + 주어진 조건)의 자료들의 가장 큰 값
/// </summary>
class MaxAlgorithm
{
    static void Main()
    {
        //[1] Initialize
        int max = int.MinValue; // 정수 형식의 데이터 중 가장 작은 값으로 초기화

        //[2] Input
        int[] numbers = { -2, -5, -3, -7, -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

최댓값 알고리즘은 최댓값이 담길 변수의 값을 정수형이 가질 수 있는 가장 작은 값으로 초기화한 후 사용해야 한다는 점에 주의해야 합니다. 그리고 최댓값을 LINQ로 구할 때에는 System.Linq 네임스페이스의 Max() 확장 메서드를 사용하면 됩니다.

최솟값(MIN) 구하기

최솟값(MIN) 알고리즘

주어진 범위 내에서 가장 작은 값을 구하는 알고리즘입니다. 즉, 관련 데이터 중에서 가장 작은 값을 구하는 데 사용됩니다.

7.2 [실습] 최솟값(MIN) 알고리즘 사용하기

최솟값 알고리즘을 적용해 주어진 범위의 데이터 중 가장 작은 값을 구하는 예제를 만들어 봅시다.

예제: 주어진 데이터 중에서 가장 작은 짝수 값

코드: MinAlgorithm.cs

//[?] 주어진 데이터 중에서 가장 작은 [짝수] 값
using System;
using System.Linq;
using static System.Console;

/// <summary>
/// 최솟값 알고리즘(Min Algorithm): (주어진 범위 + 주어진 조건)의 자료들의 가장 작은 값
/// </summary>
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

최솟값 알고리즘은 [1]번 코드처럼 최솟값이 담길 변수의 값을 정수 형식이 가질 수 있는 가장 큰 값(int.MaxValue)으로 초기화한 후 사용해야 한다는 점에 주의합니다.

LINQ를 사용하여 최솟값을 구하고자 할 때는 Min() 확장 메서드를 호출하면 됩니다.

근삿값(NEAR) 구하기

근삿값(NEAR) 알고리즘

가까운 값(근삿값)은 주어진 값과 차이가 가장 적게 나는 값을 구하는 알고리즘입니다. 앞서 다룬 최솟값 알고리즘을 조합해서 주어진 값과의 차이가 가장 작은 값을 구하면 됩니다.

[실습] 근삿값 알고리즘 사용하기

근삿값 알고리즘을 적용해 주어진 조건에 해당하는 데이터와 가장 가까운 수를 구하는 예제를 만들어 봅시다.

예제: 원본 데이터 중에서 대상 데이터와 가장 가까운 값

코드: NearAlgorithm.cs

//[?] 원본 데이터 중에서 대상 데이터와 가장 가까운 값
using System;
using System.Linq;
using static System.Console;

/// <summary>
/// 근삿값 알고리즘(Near Algorithm): 가까운 값 -> 차잇값의 절댓값의 최솟값
/// </summary>
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})");
    }
}

//numbers.First(c => Math.Abs(c - target) == numbers.Min(m => Math.Abs(m - target)))
//27

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

근삿값(가까운 값) 알고리즘은 최솟값 알고리즘의 변형 알고리즘으로, 내부적으로 최솟값 알고리즘이 그대로 사용됩니다. 정리하면 근삿값 알고리즘은 *'차잇값의 절댓값 중 최솟값'*을 구하는 알고리즘입니다.

가까운 값(Closest) 모두 구하기

가까운 값이 여러 개 있을 때 여러 개를 모두 구할 수도 있습니다. 다음 코드를 살펴보세요.

예제: 가까운 값 모두 구하기

코드: NearAll.cs

//[?] 가까운 값 모두 구하기: 가까운값(NEAR): 차이의 절댓값의 최솟값 
using System;
using System.Collections.Generic;

class NearAll
{
    static void Main()
    {
        int[] data = { 10, 20, 23, 27, 17 };
        int target = 25; // 25와 가까운 값들은 23, 27
        List<int> nears = new List<int>(); // 가까운 값들...
        int min = Int32.MaxValue;

        //[1] MIN 알고리즘: 차이의 최솟값 구하기 
        for (int i = 0; i < data.Length; i++)
        {
            if (Math.Abs(data[i] - target) < min)
            {
                min = Math.Abs(data[i] - target);
            }
        }

        Console.WriteLine($"차이의 최솟값: {min}"); // 2

        //[2] NEAR 알고리즘: 차이의 최솟값이 min인 값들을 다시 한번 비교 
        for (int i = 0; i < data.Length; i++)
        {
            if (Math.Abs(data[i] - target) == min)
            {
                nears.Add(data[i]); // 가까운 값들 모두 저장
            }
        }

        // 가까운 값들 출력
        foreach (var n in nears)
        {
            Console.WriteLine(n);
        }
    }
}

차이의 최솟값: 2
23
27

25와 가까운 데이터인 23과 27일 모두 구해서 리스트에 넣어 둔 후 출력하는 예제를 만들어 보았습니다.

순위(RANK) 구하기

순위(RANK) 알고리즘

순위 알고리즘 또는 등수 알고리즘은 주어진 자료 중에서 순위(등수)를 구하고자 할 때 사용하는 알고리즘입니다. 모든 점수는 처음에는 1등으로 설정한 후 해당 점수보다 큰 점수가 나타날 때마다 등수를 1씩 증가시켜 순위를 낮추는 게(등수가 밀리는 게) 핵심 로직입니다.

[실습] 순위(RANK) 알고리즘 사용하기

순위 알고리즘을 적용해 주어진 범위의 데이터 중 지정한 범위 내에서 등수(순위)를 구하는 예제를 만들어 보겠습니다.

예제: 순위 알고리즘 적용

코드: RankAlgorithm.cs

//[?] 주어진(지정한 범위) 데이터의 순위(등수)를 구하는 로직
using System;
using System.Linq;

/// <summary>
/// 순위 알고리즘(Rank Algorithm): 점수 데이터에 대한 순위 구하기 
/// </summary>
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]}등");
        }
    }
}

90점: 3등
 87점: 4등
100점: 1등
 95점: 2등
 80점: 5등

순위 알고리즘은 앞서 다룬 개수 알고리즘의 확장형으로 볼 수 있습니다.

이러한 순위 알고리즘을 LINQ와 람다 식으로 표현하면 다음과 같습니다. 단순히 순위 배열만 구하는 것과 점수와 순위를 묶어서 반환하는 내용을 표현했습니다.

코드: RankAlgorithm.cs

> int[] scores = { 90, 87, 100, 95, 80 };
> var rankings = scores.Select(s => scores.Where(ss => ss > s).Count() + 1).ToArray();
> rankings
int[5] { 3, 4, 1, 2, 5 }
> var rankings = scores.Select(s => 
.   new { Score = s, Rank = scores.Where(ss => ss > s).Count() + 1 });
> foreach (var r in rankings)
. {
.     Console.WriteLine($"{r.Score,3} - {r.Rank}");
. }
 90 - 3
 87 - 4
100 - 1
 95 - 2
 80 – 5

10. 정렬(Sort) 알고리즘

10.1. 정렬(Sort) 알고리즘

정렬(Sort) 알고리즘은 주어진 범위 내의 불규칙하게 배열된 데이터를 일정한 기준에 따라 오름차순이나 내림차순으로 정렬하는 알고리즘입니다. 정렬 알고리즘에는 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 퀵 정렬(Quick Sort) 등 다양한 알고리즘이 있지만, 이 강의에서는 선택 정렬 알고리즘을 중점적으로 다룰 것입니다.

  • 오름차순(Ascending) 정렬은 작은 값에서 큰 값 순으로 정렬합니다.
    • 예: 1, 2, 3
    • 예: 가, 나, 다
    • 예: A, B, C
  • 내림차순(Descending) 정렬은 큰 값에서 작은 값 순으로 정렬합니다.
    • 예: 3, 2, 1
    • 예: 다, 나, 가
    • 예: C, B, A

선택 정렬(Selection Sort) 알고리즘

선택 정렬(Selection Sort) 알고리즘은 데이터 중 하나를 기준으로 나머지 데이터와 비교하여 가장 작거나 큰 데이터와 위치를 바꾸는 과정을 반복하여 정렬하는 방식입니다. 데이터의 개수가 n개일 경우, 전체 반복 횟수는 n - 1번입니다. 오름차순 기준으로 배열을 정렬할 때, 선택 정렬은 배열의 처음부터 가장 작은 데이터를 차례대로 채워 나갑니다.

반면, 거품 정렬(Bubble Sort) 알고리즘은 오름차순으로 정렬할 때, 연속된 두 데이터를 비교하여 큰 값을 뒤로 이동시키며 가장 큰 값을 오른쪽으로 밀어 정렬하는 방식을 사용합니다.

선택 정렬 회전수

배열 data[5]에 다음과 같이 데이터가 입력되어 있다고 할 때 선택 정렬을 사용해서 오름차 순으로 정렬시키는 단계를 간단히 표현해 보겠습니다. 지면상 모든 단계를 표현하는 게 아닌 왼쪽에 가장 작은 값이 들어올 때까지만 표현합니다.

data[5]

data[0] data[1] data[2] data[3] data[4]
46 32 11 24 55

1회전:

data[0]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복하면 data[0]에는 가장 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
46 32 11 24 55
32 46 11 24 55
11 46 32 24 55

2회전:

data[1]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 2회전이 끝나면 data[1]에 두 번째로 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
11 46 32 24 55
11 32 46 24 55
11 24 46 32 55

3회전:

data[2]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 3회전이 끝나면 data[2]에 세 번째로 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
11 24 46 32 55
11 24 32 46 55

4회전:

data[3]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 4회전이 끝나면 data[3]에 네 번째로 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
11 24 32 46 55
11 24 32 46 55

참고: 선택 정렬 관련 정보처리기사 필기 문제

코드를 작성하기 전에 선택 정렬 알고리즘의 흐름을 조금 더 정리하는 차원에서, 정보처리기사 필기 시험에 여러 해에 걸쳐서 출제된 선택 정렬 관련 문제를 참고용으로 풀어보겠습니다.

문제: 자료가 다음과 같이 주어졌을 때 선택 정렬(selection sort)을 적용하여 오름차순으로 정렬할 경우 pass 2를 진행한 후의 정렬된 값으로 옳은 것은?

자료: 9, 4, 5, 11, 8

가. 4, 5, 9, 8, 11		나. 4, 5, 9, 11, 8
다. 4, 5, 8, 11, 9		라. 4, 5, 8, 9, 11

정답: 나

해설: 가장 작은 데이터를 왼쪽으로 하나씩 채우는 형태로 각 회전이 끝난 후의 배열 모양은 다음과 같습니다.

1.	pass 1: 4, 9, 5, 11, 8
2.	pass 2: 4, 5, 9, 11, 8
3.	pass 3: 4, 5, 8, 11, 9
4.	pass 4: 4, 5, 8, 9, 11

선택 정렬 알고리즘 순서도

다음은 선택 정렬로 오름차순으로 정렬할 때의 순서도입니다.

오름차순 정렬

선택 정렬 알고리즘 순서도 1

다음은 선택 정렬로 내림차순으로 정렬할 때의 순서도입니다.

내림차순 정렬

선택 정렬 알고리즘 순서도 2

[실습] 정렬(Sort) 알고리즘 사용하기

주어진 데이터를 오름차순 또는 내림차순으로 정렬하는 정렬 알고리즘 중 가장 학습하기 편한 선택 정렬 알고리즘을 적용해 보겠습니다. 다음 내용을 입력한 후 실행해 보세요. 정렬 알고리즘은 오름차순 기준으로 가장 작은 데이터를 왼쪽으로 순서대로 이동합니다.

예제: 데이터를 순서대로 정렬

다음 예제를 작성 후 실행해 보세요.

selection_sort.c

//[?] 무작위 데이터를 순서대로 [오름차순|내림차순] 정렬
#include <stdio.h>
#define N 5

// 정렬 알고리즘(Sort Algorithm): 가장 [작은|큰] 데이터를 왼쪽으로 순서대로 이동
int main(void)
{
    //[1] Input: Data Structure(Array, List, Stack, Queue, Tree, DB, ...)
    int data[] = { 3, 2, 1, 5, 4 };
    int i, j, temp;

    //[2] Process: Selection Sort(선택 정렬) 알고리즘
    for (i = 0; i < N - 1; i++) // i = 0 to N - 1
    {
        for (j = i + 1; j < N; j++) // j = i + 1 to N
        {
            if (data[i] > data[j]) // 부등호 방향: 오름차순(>), 내림차순(<)
            {
                // 3단계 코드에 의해서 데이터 교환 
                temp = data[i];
                data[i] = data[j];
                data[j] = temp; 
            }
        }
    }

    //[3] Output
    for (int i = 0; i < N; i++)
    {
        printf("%d\t", data[i]);
    }
    printf("\n");

    return 0;
}

1       2       3       4       5

코드: 알고리즘_정렬.c

/*
정렬(Sort) 알고리즘 : 데이터를 순서대로 정렬
*/
#include <stdio.h>

int main(void)
{
    //[1] Input
    int intNum[5] = { 2, 3, 1, 5, 4 };
    int i, j, temp;

    //[2] Process : Selection Sort(선택 정렬)
    for (i = 0; i < 5 - 1; i++)
    {
        for (j = i + 1; j < 5; j++)
        {
            if (intNum[i] > intNum[j])
            {
                temp = intNum[i];
                intNum[i] = intNum[j];
                intNum[j] = temp;
            }
        }
    }

    //[3] Output
    for (i = 0; i < 5; i++)
    {
        printf("%d\n", intNum[i]);
    }

    return 0;
}

함수로 구현한 C 언어 선택 정렬 알고리즘 예제

예제: 선택 정렬 알고리즘

코드: selection_sort.c

#include <stdio.h>

void selection_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

int main() {
    int arr[] = {34, 12, 45, 8, 21, 17};
    int size = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, size);

    printf("선택 정렬 후 배열: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

예제: 함수와 포인터를 사용한 선택 정렬 구현

코드: selection_sort.c

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        swap(&arr[min_index], &arr[i]);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

정렬 알고리즘은 현업에서도 굉장히 많이 사용하는 알고리즘입니다. 많은 정렬 알고리즘 중에서도 선택 정렬 알고리즘은 익혀 두어야 하는 필수 알고리즘 중의 하나이므로 꼭 기억하길 권장합니다. 물론 현업에서 일할 때는 선택 정렬 알고리즘보다 훨씬 빠르게 사용할 수 있는 C 언어를 예를 들어 qsort() 함수, C#을 예를 들어 Sort() 메서드와 OrderBy() 등의 메서드가 이미 준비되어 있으니 그걸 사용해도 좋습니다.

거품 정렬(Bubble Sort) 알고리즘

거품 정렬 알고리즘은 오름차순 정렬할 때 앞에서부터 2개씩 비교해서 큰 값을 뒤로 놓는 형태로 가장 큰 값을 오른쪽으로 미는 형태로 정렬을 합니다.

거품 정렬 회전수

배열 data[5]에 다음과 같이 데이터가 입력되어 있다고 할 때 거품 정렬을 사용해서 오름차순으로 정렬시키는 단계를 간단히 표현해보겠습니다.

data[5]

data[0] data[1] data[2] data[3] data[4]
46 32 11 24 55

1회전:

data[0]을 시작으로 바로 옆의 데이터와 비교하여 가장 큰 값과 자리를 바꾸는 과정을 반복하면 data[5 - 1]에는 가장 큰 값이 들어갑니다. 최종으로 data[4]에 가장 큰 55가 들어갑니다. 거품이 버블버블 위로 올라가는 모양이어서 거품 정렬입니다.

0 1 2 3 4
0 46 31 11 24 55 바꿈
1 31 46 11 24 55 바꿈
2 31 11 46 24 55 바꿈
3 31 11 24 46 55 안바꿈
4 31 11 24 46 55 최종

2회전:

data[4]를 빼고 나머지 데이터를 처음부터 이웃 데이터와 비교하여 가장 큰 값과 자리를 바꾸는 과정을 반복합니다. 2회전이 끝나면 data[5 - 2]에 두 번째로 큰 값이 들어갑니다.

0 1 2 3 4
0 31 11 24 46 55 바꿈
1 11 31 24 46 55 바꿈
2 11 24 31 46 55 안바꿈
3 11 24 31 46 55 최종

3회전:

data[3] 이후 데이터를 빼고 나머지 데이터를 처음부터 이웃 데이터와 비교하여 가장 큰 값과 자리를 바꾸는 과정을 반복합니다. 3회전이 끝나면 data[5 - 3]에 세 번째로 큰 값이 들어갑니다.

0 1 2 3 4
0 11 24 31 46 55 안바꿈
1 11 24 31 46 55 안바꿈
2 11 24 31 46 55 최종

4회전:

data[2] 이후 데이터를 빼고 나머지 데이터를 처음부터 이웃 데이터와 비교하여 가장 큰 값과 자리를 바꾸는 과정을 반복합니다. 4회전이 끝나면 data[5 - 4]에 네 번째로 큰 값이 들어갑니다.

0 1 2 3 4
0 11 24 31 46 55 안바꿈
1 11 24 31 46 55 최종

[실습] 버블 소트를 사용하여 내림차 순으로 정렬하기

코드: bubble_sort.c

// bubble_sort.c
//[?] 무작위 데이터를 순서대로 [오름차순(ASC)|내림차순(DESC)] 정렬
// 거품(버블) 정렬 알고리즘(Bubble Sort Algorithm): 
// 가장 [작은|큰] 데이터를 오른쪽으로 순서대로 이동
#include <stdio.h>

int main(void)
{
    //[1] Input
    int data[5] = { 3, 2, 1, 5, 4 };
    int N = 5;

    //[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++)
    {
        printf("%d\t", data[i]);
    }
    printf("\n");

    return 0;
}

5       4       3       2       1

또 다른 모양의 거품 정렬 알고리즘 예제는 다음 링크를 참고하세요.

입력으로 버블 정렬 진행하기

함수로 구현한 버블 정렬 알고리즘

예제: 버블 정렬 알고리즘

코드: bubble_sort_function.c

#include <stdio.h>

/**
 * @brief 버블 정렬 함수
 *
 * 이 함수는 주어진 정수 배열을 오름차순으로 정렬합니다.
 * 정렬 알고리즘으로는 버블 정렬을 사용합니다.
 *
 * @param arr 정렬할 정수 배열
 * @param size 배열의 크기
 */
void bubble_sort(int arr[], int size)
{
    // 'size - 1'번 반복하여 배열의 모든 요소를 확인
    for (int i = 0; i < size - 1; i++)
    {
        // 배열의 'size - i - 1'번째 요소까지 반복
        for (int j = 0; j < size - i - 1; j++)
        {
            // 현재 요소가 다음 요소보다 크다면
            if (arr[j] > arr[j + 1])
            {
                // 두 요소의 위치를 바꿉니다
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

/**
 * @brief 프로그램의 메인 함수
 *
 * 이 함수에서는 정수 배열을 선언하고 버블 정렬 함수를 호출하여 배열을 정렬합니다.
 * 그 후, 정렬된 배열을 출력합니다.
 *
 * @return 프로그램의 종료 상태. 정상 종료 시 0을 반환합니다.
 */
int main(void)
{
    // 정렬할 정수 배열
    int arr[] = { 34, 12, 45, 8, 21 };

    // 배열의 크기 계산
    int size = sizeof(arr) / sizeof(arr[0]);

    // 배열을 버블 정렬
    bubble_sort(arr, size);

    // 정렬된 배열 출력
    printf("버블 정렬 후 배열: ");
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

버블 정렬 후 배열: 8 12 21 34 45

예제: 버블 정렬 구현

코드: bubble_sort_pointer.c

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

코드: BubbleSort.cs

// BubbleSort.cs
//[?] 무작위 데이터를 순서대로 [오름차순(ASC)|내림차순(DESC)] 정렬
using System;

/// <summary>
/// 정렬 알고리즘(Sort Algorithm): 가장 [큰] 데이터를 오른쪽으로 순서대로 이동
/// </summary>
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();
    }
}

5       4       3       2       1

삽입 정렬 알고리즘

정렬 알고리즘의 또 다른 예제인 삽입 정렬은 다음 링크를 참고하세요. 강의 진행상 반드시 필요한 부분은 아니기에 나중에 시간내서 살펴보세요. 단, 알고리즘 시험 또는 코딩 테스트 목적이라면 반드시 학습이 되어 있어야 하는 알고리즘입니다.

삽입 정렬(Insertion Sort) 알고리즘

검색(SEARCH) 알고리즘

검색(SEARCH) 알고리즘

검색 알고리즘은 배열 등의 데이터에서 특정 값을 검색하는 알고리즘입니다. 일반적으로 순차 검색과 이진 검색 등으로 구분할 수 있습니다.

  • 순차 검색(sequential search): 전체 데이터를 처음부터 끝까지 순서대로 검색합니다.
  • 이진 검색(binary search): 정렬되어 있는 데이터를 절반으로 나눠서 검색합니다.

순차 검색 알고리즘

순차 검색(Sequential Search) 알고리즘은 컴퓨터 과학에서 가장 기본적인 검색 알고리즘 중 하나로, 데이터셋에 저장된 요소들을 처음부터 끝까지 순서대로 탐색하여 원하는 값을 찾는 방법입니다. 이 알고리즘은 특별한 자료구조나 추가 메모리 공간이 필요하지 않으며, 정렬되지 않은 데이터셋에서도 사용할 수 있습니다.

순차 검색 알고리즘은 주어진 데이터셋에 원하는 값이 있으면 그 위치를 반환하고, 없으면 실패 또는 값을 찾지 못했다는 결과를 반환합니다. 간단한 구조와 구현이 용이한 장점이 있지만, 데이터셋이 클 경우 검색 속도가 느려질 수 있습니다. 이러한 한계 때문에 더 효율적인 검색 알고리즘들이 개발되었지만, 간단한 문제나 작은 데이터셋에 대해서는 순차 검색 알고리즘이 여전히 유용합니다.

제목: 순차 검색 알고리즘을 사용한 C# 예제

소개: 순차 검색(Sequential Search)은 컴퓨터 과학에서 가장 기본적인 검색 알고리즘 중 하나입니다. 이 알고리즘은 주어진 데이터셋에서 찾고자 하는 값을 찾기 위해 처음부터 끝까지 순서대로 검색하는 방법을 사용합니다. 이 예제에서는 순차 검색 알고리즘을 이용하여 정수 배열에서 사용자가 입력한 값을 찾아냅니다.

소스 코드: SequentialSearch.cs 파일에 저장된 아래의 소스 코드를 참고하세요.

using System;

namespace SequentialSearchExample
{
    class Program
    {
        static void Main(string[] args)
        {
            int i;
            int[] data = {1, 3, 5, 7, 9, 11};
            int search = 0;
            int n = data.Length;
            bool flag = false;

            Console.Write("검색할 정수(1~20) : ");
            search = int.Parse(Console.ReadLine());

            for (i = 0; i < n; i++)
            {
                if (search == data[i])
                {
                    flag = true;
                }
            }

            if (flag == true)
            {
                Console.WriteLine("{0}를 찾았습니다.", search);
            }
            else
            {
                Console.WriteLine("{0}를 못 찾았습니다.", search);
            }
        }
    }
}

검색할 정수(1~20): 5
5을(를) 찾았습니다.

설명:

  1. 먼저 System 네임스페이스를 사용하도록 지정합니다.

  2. "SequentialSearchExample" 네임스페이스와 "Program" 클래스를 정의하고, Main 메서드를 생성합니다.

  3. 변수를 초기화합니다. 배열 data에는 검색할 정수들이 저장되어 있고, search 변수에는 사용자가 입력한 값이 저장됩니다. n 변수는 배열의 길이를 저장하며, flag 변수는 검색된 값을 나타내는 불리언 변수입니다.

  4. 사용자로부터 검색할 정수를 입력받습니다.

  5. 순차 검색 알고리즘을 사용하여 배열에서 사용자가 입력한 값이 있는지 확인합니다. 배열 내에 값이 존재하면 flag 변수를 true로 설정합니다.

  6. 검색이 완료되면 결과를 출력합니다. 만약 flag 변수가 true라면 찾고자 하는 값을 찾았다는 메시지를 출력하고, 그렇지 않으면 값을 찾지 못했다는 메시지를 출력합니다.

이 예제를 통해 순차 검색 알고리즘을 사용하여 주어진 데이터셋에서 특정 값을 찾는 방법을 확인할 수 있습니다. 순차 검색은 간단하고 이해하기 쉽지만, 데이터셋이 클 경우 효율성이 떨어질 수 있습니다.

이진 검색(Binary Search) 알고리즘

이진 검색(binary search) 알고리즘은 주어진 데이터가 오름차순으로 정렬되어 있다고 가정합니다. 만약 데이터가 정렬되어 있지 않다면, 앞서 배운 정렬 알고리즘 등을 이용하여 정렬한 다음에 이진 검색 알고리즘 로직을 적용해야 합니다. 이진 검색 알고리즘은 영어로 Divide and Conquer(나누기 및 정복) 알고리즘으로 표현하는데, 그 의미 그대로 데이터를 절반으로 나눠서 검색하여 순차 검색보다 효율을 높입니다.

다음 그림과 같이 1차원 배열에 1, 3, 5, 7, 9의 데이터가 있을 경우, 9를 검색할 때 이진 검색을 사용하면 중간 인덱스 값을 찾는 것이 핵심 로직입니다. 중간 인덱스를 mid로 놓고 low 인덱스는 0 그리고 high 인덱스는 4로 본 후 각 회전마다 중간 인덱스를 구하고 중간 인덱스의 값이 찾으려는 데이터인지 비교하면 됩니다.

그림: 이진 검색 알고리즘 실행 단계

이진 검색 알고리즘 실행 단계

앞 그림과 다음 설명을 참고해서 한 번 읽고 넘어가세요.

  1. 1회전:
    • A. 1회전 들어가기 전: low = 0, high = 4, mid = (low + high) / 2 = (0 + 4) / 2 = 2
    • B. 1회전: mid 값인 2 인덱스의 데이터인 5와 찾으려는 9 비교, 찾으려는 데이터가 5보다 크므로 왼쪽 영역은 버리고 오른쪽 영역만 비교하기 위해서 low 값을 mid + 1로 증가해서 low를 3으로 재설정합니다.
  2. 2회전:
    • A. 2회전 들어가기 전: low = 3, high = 4, mid = (3 + 4) / 2 = 3
    • B. 2회전: mid 값인 3 인덱스의 데이터인 7과 찾으려는 9 비교, 찾으려는 데이터가 7보다 크므로 왼쪽 영역은 버리고 오른쪽 영역만 비교하기 위해서 low 값을 mid + 1로 증가해서 low를 4로 재설정합니다.
  3. 3회전:
    • A. 3회전 들어가기 전: low = 4, high = 4, mid = (4 + 4) / 2 = 4
    • B. 3회전: mid 값인 4인덱스의 데이터인 9와 찾으려는 9 비교, 3번의 검색 끝에 데이터를 찾습니다.

11.3. 참고: 이진 검색 관련 정보처리기사 필기 문제

이진 검색 알고리즘을 사용하여 데이터를 검색하는 내용 관련해서 코드를 만들기 전에 이해를 돕기 위한 이론 문제를 먼저 풀어보겠습니다.

문제: 다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾을 경우 비교되는 횟수는?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

가. 2번 나. 3번 다. 4번 라. 5번

답: 나

해설:

  1. 1회전: (0 + 14) / 2 = 7번째 인덱스의 값인 8
  2. 2회전: (8 + 14) / 2 = 11번째 인덱스의 값인 12
  3. 3회전: (12 + 14) / 2 = 13번째 인덱스의 값인 14 <- 찾으려는 값

11.4. [실습] 검색(SEARCH) 알고리즘 사용하기

많은 검색 알고리즘 중에서 학습용으로 가장 권장되는 이진 검색 알고리즘을 사용하여 배열에서 특정 데이터를 검색하는 기능을 코드로 구현해보겠습니다. 검색 알고리즘을 적용하면 주어진 데이터에서 특정 데이터를 찾을 수 있습니다.

예제: 정렬되어 있는 데이터를 이진 검색(이분 탐색)을 사용하여 검색

SearchAlgorithm.c

//[?] 정렬되어 있는 데이터를 이진 검색(이분 탐색)을 사용하여 반씩 나눠서 검색
#include <stdio.h>
#include <stdbool.h> // bool, true(1), false(0)

// 검색 알고리즘(Search Algorithm): 주어진 데이터에서 특정 데이터 찾기
int main(void)
{
    //[1] Input
    int data[] = { 1, 3, 5, 7, 9 }; // 오름차순으로 정렬되었다고 가정
    int N = sizeof(data) / sizeof(int); // 의사코드
    int search = 3; // 검색할 데이터: scanf() 등으로 가져오기
    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)
    {
        printf("%d을(를) %d위치에서 찾았습니다.", search, index);
    }
    else
    {
        printf("찾지 못했습니다.");
    }

    return 0;
}

3을(를) 1위치에서 찾았습니다.

이진 검색 알고리즘은 정렬된 데이터를 검색하는데, 찾으려는 값보다 작거나 클 때 반 씩 나눠서 검색합니다. 따라서 순차 검색보다 검색 효율이 상당히 좋습니다.

12. 병합(MERGE) 알고리즘

12.1. 병합(MERGE) 알고리즘

병합 알고리즘은 2개의 정렬된 배열을 합쳐 하나의 정렬된 배열로 만드는 데 사용됩니다.

12.2. [실습] 병합(MERGE) 알고리즘 사용하기

다음은 오름차순으로 정렬되어 있는 두 정수 배열(first, second)을 병합하여 오름 차순 정렬된 배열(merge)을 완성하는 예제입니다. 처리 조건은 다음과 같습니다.

  • 배열 first는 1 ~ M까지, 배열 second는 1 ~ N까지의 자료가 있습니다.
  • 배열 merge는 M + N개의 개수가 있습니다.
  • i, j, k는 배열 첨자 변수로 사용됩니다.

병합 알고리즘 의사 코드

TODO:

병합 정렬 알고리즘 순서도

다음 그림은 병합 알고리즘을 A(I), B(K), C(K) 배열로 표현해 본 참고용 순서도입니다.

다음은 오름차순된 두 배열을 병합하여 오름차순 배열을 갖는 C(K) 배열을 완성하는 알고리즘입니다.

실제 예제 코드에서는 A 대신에 first, B 대신에 second, C 대신에 merge 이름으로 코드를 작성하였습니다.

병합 정렬 알고리즘 순서도

12.2.1 [예제] 오른차순으로 정렬된 두 정수 배열 병합

merge_sort.c, 알고리즘_병합(MEARGE).c

/*
    병합(MEARGE) 알고리즘 : 오름차순으로 나열된 두 그룹의 데이터를 한 그룹의 데이터로 병합한다.
    (1) 데이터 a, b 중에 어느 한 쪽이 끝에 도달할 때까지 다음을 반복
    (2) a(i)와 b(j)를 비교해서 작은쪽을 c(k)에 복사하고 작은 쪽의 첨자를 +1한다.
    (3) 둘 중에 아직 끝까지 도달하지 않은 데이터를 끝까지 복사한다.
*/
#include <stdio.h>

#define M 10
#define N 5

int main(void)
{
    //[1] Init/Input
    static int a[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
    static int b[] = { 1, 3, 5, 7, 9 };
    static int c[M + N];. //병합된 데이터 저장

    //[2] Process
    int i, j, k;

    i = j = k = 0;

    while (i < M && j < N). //a[], b[] 모두 끝에 도달하지 않은 동안
    {
        if (a[i] <= b[j])
        {
            c[k++] = a[i++];
        }
        else
        {
            c[k++] = b[j++];
        }
    }

    while (i < M). . //a[]가 끝에 도달할 때까지
    {
        c[k++] = a[i++];
    }

    while (j < N). . //b[]가 끝에 도달할 때까지
    {
        c[k++] = b[j++];
    }

    //[3] Output
    for (i = 0; i < M + N; i++)
    {
        printf("%d ", c[i]);
    }
    printf("\n");

    return 0;
}

1 2 3 4 5 6 7 8 9 10 12 14 16 18 20

각 회전에 따른 i, j, k 변수의 값과 merge 배열의 값은 다음과 같습니다. 단, 배열 초깃값은 0으로 설정되어 있다고 가정하겠습니다.

0회전
        i: 0, j: 0, k: 0, merge: 0,0,0,0,0
1회전
        i: 1, j: 0, k: 1, merge: 1,0,0,0,0
2회전
        i: 1, j: 1, k: 2, merge: 1,2,0,0,0
3회전
        i: 2, j: 1, k: 3, merge: 1,2,3,0,0
4회전
        i: 2, j: 2, k: 4, merge: 1,2,3,4,0
5회전
        i: 3, j: 2, k: 5, merge: 1,2,3,4,5

first(i) < second(j)이면 first(i) 값을 배열 merge(k)에 대입하고 첨자 i와 k 값을 1 증가시킨다. first(i) > second(j)이면 second(j) 값을 배열 merge(k)에 대입하고 첨자 j와 k 값을 1 증가시킨다.

병합 알고리즘(병합 정렬 알고리즘)의 공식과 같은 코드 모양입니다. 코드 내의 주석을 읽으면서 직접 입력한 후 결과를 확인하길 권장합니다.

참고: 병합 알고리즘 관련 질문과 답변

https://www.dotnetkorea.com/BoardView?BoardName=Qna&Num=1039

merge[k] = first[i];
k++;
i++;

위 세 줄을 한 줄로 줄인 코드가 다음 코드입니다.

merge[k++] = first[i++];

병합 정렬 알고리즘은 이미 정렬된 두 개의 배열을 합쳐서 그 결괏값도 정렬된 형태로 나오는게 목적입니다. 제가 책에도 썼지만, 12개 알고리즘은 공식과 같은 알고리즘이기에, 수학 공식 암기 형태로 익혀두시면 좋습니다. 그리고, Visual Studio 2022에서 F11번 계속 반복하면서 실행해보시면 코드 흐름을 익히는데 도움이 되실 겁니다.

12.3. LINQ로 데이터 병합하기

LINQ와 람다 식을 사용하여 2개의 정수 배열을 병합하려면 다음처럼 메서드 구문이나 쿼리 구문을 사용하면 됩니다.

코드: MergeAlgorithm.cs

// MergeAlgorithm.cs
> int[] first = { 1, 3, 5 };
> int[] second = { 2, 4 };
> int[] merge =
.     (from o in first select o).Union(from t in second select t)
.     .OrderBy(m => m).ToArray();
> merge
int[5] { 1, 2, 3, 4, 5 }
> int[] merge = first.Union(second).OrderBy(m => m).ToArray();
> merge
int[5] { 1, 2, 3, 4, 5 }

최빈값(MODE) 구하기

최빈값(MODE) 알고리즘

최빈값(MODE)은 데이터 중에서 가장 많이 나타나는 값을 의미합니다. 최빈값 알고리즘은 다른 알고리즘과는 또 다른 모양으로 데이터 자체를 배열의 인덱스로 보고 인덱스의 개수(COUNT) 알고리즘을 적용하는 형태입니다.

다음 그림을 보면 각각의 데이터에 해당하는 인덱스를 1씩 증가시켜 최종적으로 3이 2번 나와서 최댓값이 되어 그 때의 데이터(인덱스)인 3이 최빈값이 되는 형태입니다.

그림: 최빈값 선택 과정

최빈값 알고리즘

처음 indexes 배열은 다음 왼쪽 그림처럼 모두 0으로 초기화한 후 각각의 점수에 해당하는 인덱스를 1씩 증가시켜 최종적으로 인덱스 3이 2로, 가장 큰 값이 되어 최빈값으로 정해지는 형태가 최빈값 알고리즘의 핵심 로직입니다.

그림: 최빈값 알고리즘을 사용하여 인덱스에 해당하는 값 증가하기

처음:

처음

변경:

변경

최빈값(MODE) 알고리즘 사용하기

최빈값 알고리즘 공식은 점수 인덱스(0~n)의 개수(COUNT)의 최댓값(MAX)입니다. 최빈값 알고리즘을 나타내는 공식을 코드로 구현해보겠습니다. 다음 코드를 작성한 후 실행해보세요.

최빈값 찾기

코드: ModeAlgorithm.cs

//[?] 주어진 데이터에서 가장 많이 나타난(중복된) 값
using System;
using System.Linq;

/// <summary>
/// 최빈값 알고리즘(Mode Algorithm): 점수 인덱스(0~n)의 개수(COUNT)의 최댓값(MAX)
/// </summary>
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
                mode = i; // MODE
            }
        }

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

최빈값: 3 -> 2번 나타남

최빈값 알고리즘은 점수를 인덱스로 다룬 후 개수 알고리즘과 최댓값 알고리즘을 적용하여 마지막으로 최빈값을 구하는 형태입니다. 다른 알고리즘과 달리 데이터 자체를 배열의 인덱스로 보고 계산하는 독특한 모양의 코드를 작성하기에 필수 학습 알고리즘으로 선택했습니다. 참고로 이번 예제에서는 indexes 배열을 정수 배열을 사용했지만, Hashtable 클래스를 사용하면 좀 더 넓은 범위의 데이터에 대한 최빈값을 구할 수도 있습니다.

14. 그룹(GROUP) 알고리즘

14.1. 그룹(GROUP) 알고리즘

그룹(GROUP) 알고리즘은 반별 총점이나 평균, 제품별 판매금액의 합 같은 그룹별로 구분되는 데이터에 대해 통계를 산출할 때 사용하는 알고리즘입니다. 그룹 알고리즘은 데이터가 미리 정렬되어 있어야 합니다.

코드 관점으로 보면 그룹 알고리즘은 2차원 배열 형태의 리스트에서 특정 속성을 키로 잡아서 데이터를 그룹화할 때 사용되는 알고리즘입니다. 예를 들어 다음과 같은 상품 이름(Name)과 수량(Quantity) 형태의 원본 데이터가 있다고 가정하겠습니다.

  • "RADIO", 3
  • "TV", 1
  • "RADIO", 2
  • "DVD", 4

그러면 이를 상품 이름(Name)으로 그룹화하면 다음과 같이 나옵니다.

  • "DVD", 4
  • "RADIO", 5
  • "TV", 1

그룹 알고리즘은 정렬된 데이터를 기준으로 수량(Quantity)을 SUM하는 형태가 가장 기초적인 모양입니다. 데이터의 흐름을 그림으로 표현해보면 다음과 같습니다.

그림: 그룹 알고리즘 처리 단계

records 리스트 정렬 전:

정렬 전

records 리스트 정렬 후:

정렬 후

groups 리스트에 그룹화:

그룹화

그룹(GROUP) 알고리즘 사용하기

그룹 알고리즘의 가장 기본적인 코드 모양을 살펴보겠습니다. 단, 현재 그룹 알고리즘 예제는 아직 배우지 않은 클래스와 속성의 개념 그리고 컬렉션 이니셜라이저 등의 개념들이 들어가 있습니다. 알고리즘을 주제로 12개를 묶어서 표현하다 보니 이곳에서 미리 소개하게 되었는데요. 일단은 코드에 대한 이해보다는 이렇게 하면 그룹이 되는구나 정도로 가볍게 이번 실습 예제를 살펴보고 넘어간 후 나중에 기회가 되면 다시 한 번 이곳을 찾아서 이 부분의 소스 코드를 확인하길 권장합니다.

예제: 컬렉션 형태의 데이터를 특정 키 값으로 그룹화

코드: GroupAlgorithm.cs

//[?] 컬렉션 형태의 데이터를 특정 키 값으로 그룹화
using System;
using System.Collections.Generic;
using System.Linq;

/// <summary>
/// 그룹 알고리즘(Group Algorithm): 특정 키 값에 해당하는 그룹화된 합계 리스트 만들기
/// </summary>
class GroupAlgorithm
{
    /// <summary>
    /// 테스트용 레코드 클래스
    /// </summary>
    class Record
    {
        /// <summary>
        /// 상품명
        /// </summary>
        public string Name { get; set; }
        /// <summary>
        /// 수량
        /// </summary>
        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());
    }
}

[1] 정렬된 원본 데이터:
  DVD - 4
RADIO - 2
RADIO - 3
   TV - 1
[2] 이름으로 그룹화된 데이터:
  DVD - 4
RADIO - 5
   TV - 1
[3] LINQ로 그룹화된 데이터:
  DVD - 4
RADIO - 5
   TV - 1

[3]번 코드의 LINQ 사용 부분을 보면 GroupBy() 확장 메서드로 편하게 GROUP 알고리즘을 적용한 예를 볼 수 있습니다. 데이터를 그룹화할 때에는 for 문과 if 문으로 직접 작성하는 것보다는 LINQ를 사용하여 손쉽게 그룹화를 진행할 수 있습니다. 이러한 그룹화 기능을 알고리즘 코드로 구현하는 것은 꽤 까다로워 보입니다. 하지만 그룹 알고리즘도 반드시 알아야하는 알고리즘의 형태를 지니고 있기에 소스 코드를 분석해서 나만의 것으로 만들어 보면 좋습니다.

15. 장 요약

동일한 C# 키워드를 사용해도 알고리즘을 어떻게 만들지에 따라서 코드가 정확하게 실행되거나 더 빨리 실행될 수 있습니다. 프로그래밍에서 알고리즘은 굉장히 중요한 영역입니다. 하지만 알고리즘은 갈수록 복잡해지고 수학적인 지식이 많이 필요합니다. 이번 강의는 알고리즘 중에서 가장 쉬운 12가지를 맛보기로 살펴보았습니다. 이를 바탕으로 앞으로 더 많은 알고리즘을 익혀 나가길 권장합니다.

VisualAcademy Docs의 모든 콘텐츠, 이미지, 동영상의 저작권은 박용준에게 있습니다. 저작권법에 의해 보호를 받는 저작물이므로 무단 전재와 복제를 금합니다. 사이트의 콘텐츠를 복제하여 블로그, 웹사이트 등에 게시할 수 없습니다. 단, 링크와 SNS 공유, Youtube 동영상 공유는 허용합니다. www.VisualAcademy.com
박용준 강사의 모든 동영상 강의는 데브렉에서 독점으로 제공됩니다. www.devlec.com