TIL(Today I Learned)

C# : 정렬, 탐색 알고리즘 - TIL#11

Najdorf 2024. 1. 8. 22:15
728x90

알고리즘하면 빼먹을 수 없는 정렬, 탐색 알고리즘이다.

 

정렬 알고리즘은,

어떤 데이터 세트가 있을 때, 특정 순서(오름차순, 내림차순 등)로 배열하는 알고리즘이다.

 

즉, {5, 1, 2, 6, 4, 3}이란 데이터가 주어진다면,

오름차순으로 {1, 2, 3, 4, 5, 6}으로 정리하는 방법 등을 말한다.

 

정렬 알고리즘은 대표적으로 4가지가 있다.

  • 선택 정렬 (Selection Sort)
  • 삽입 정렬 (Insertion Sort)
  • 퀵 정렬 (Quick Sort)
  • 병렬 정렬 (Merge Sort)

https://www.youtube.com/watch?v=kPRA0W1kECg

정렬 알고리즘을 방법별로 아주 쉽게 이해할 수 있는 영상. 시각화랑 청각화가 동시에 되어있다.

 

위 영상에서 처음 4개의 정렬 알고리즘이 순서대로 선택, 삽입, 퀵, 병렬 정렬이다.

선택 정렬은 주어진 배열에서 최소값을 찾아서 맨 앞과 교환하는 방법이다.

(또는 최대값으로 그 반대의 경우도 가능하다.)

 

알고리즘 동작 방식은 배열의 가장 작은 원소를 찾아서

맨 앞에 위치하는 것을 반복해서 정렬하는 방식이다.

 

변수가 2개인 중첩 반복문을 이용하기 때문에

일반적인 경우와 최악의 경우 모두 시간 복잡도는 O(n^2)이 된다.

더보기 
for (int i = 0; i < arr.Length - 1; i++)
{
    int minIndex = i;

    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[j] < arr[minIndex])
        {
            minIndex = j;
        }
    }

    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

 

첨언하자면, 아래 부분은 대표적인 스왑 코드로, 두 변수의 값을 서로 바꾸는 코드이다.

int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;

 

일반적으론 이렇게 쓰인다.

int num1 = 10;
int num2 = 20;

int temp = num1; // temp 값 = 10
num1 = num2; // num1 값 = 20
num2 = temp; // num2 값 = 10

 

 

 

삽입 정렬은 배열을 처음부터 스캔?하면서 정렬되지 않은 부분에서 요소를 가져와

정렬된 부분에 적절한 위치에 삽입하는 것을 반복하는 방법이다.

 

주어진 배열이 난잡하게 섞여있으면 시간 복잡도가 O(n^2)이고,

정렬되어 있으면 삽입을 위해 처음으로 돌아갈 필요가 없으니 O(n)이 된다.

더보기 
for (int i = 1; i < arr.Length; i++)
{
    int j = i - 1;
    int key = arr[i];

    while (j >= 0 && arr[j] > key)
    {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = key;
}

 

 

 

다음은 퀵 정렬인데,

앞선 방법들과 방식이 차이가 나서 처음 봤을 때는 이해가 쉽지 않을 수 있다.

(상단 영상의 0:39 참고)

 

작동 방식은 피벗을 기준으로 하나 정해두고,

피벗보다 작은 요소들은 왼쪽, 크면 오른쪽으로 분할하고

이것을 재귀적으로 반복해서 정렬하는 방법이다. (분할 정복 방법의 일종)

 

시간 복잡도는 최악의 경우 O(n^2)이지만,

일반적으로는 (n log n)이다.

 

재귀 호출에 스택 공간이 필요하기에

공간 복잡도는 최악의 경우 O(n), 평균적으로 O(log n)이다.

더보기 
void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}

int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }

    Swap(arr, i + 1, right);

    return i + 1;
}

void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

QuickSort(arr, 0, arr.Length - 1);

foreach (int num in arr)
{
    Console.WriteLine(num);
}

 

 

병합 정렬은 주어진 배열을 반으로 나눈 뒤,

각 부분을 정렬될 때까지 재귀적으로 반복해 정렬하고,

작은 단위부터 병합하는 방식이다.

 

반으로 나누는 횟수가 갈 수록 줄어든다는 특징이 있어

모든 경우에 대해 시간 복잡도가 O(n log n)이다.

 

다만, 정렬을 위한 임시 배열을 새로 생성해야 해서

공간 복잡도가 O(n)이 되는 특징이 있다.

더보기 
void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;

        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] temp = new int[arr.Length];

    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid)
    {
        temp[k++] = arr[i++];
    }

    while (j <= right)
    {
        temp[k++] = arr[j++];
    }

    for (int l = left; l <= right; l++)
    {
        arr[l] = temp[l];
    }
}

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

MergeSort(arr, 0, arr.Length - 1);

foreach (int num in arr)
{
    Console.WriteLine(num);
}

 

대표적인 4가지의 정렬 알고리즘에 대해 알아봤는데,

C#에서는 이를 일일이 다 구현하지는 않고

C# Sort라는 메서드를 사용해 정렬을 한다.

다음으로 알아볼 것은 탐색 알고리즘이다.

 

정렬 알고리즘은 주어진 데이터를 어떠한 정해진 순서대로 정렬하는 것이었다면,

탐색 알고리즘은 주어진 데이터 내의 찾고 싶은 자료를 얻는 방법이다.

 

가장 일반적인 방법으로는 선형 탐색(Linear Search)과 이진 탐색(Binary Search)이 있다.

 

 

 

선형 탐색은 가장 단순한 방법이다.

말 그대로 처음부터 끝까지(...) 얻고자 하는 자료가 나올 때까지 비교하는 방식이다.

 

따라서, 얻고자 하는 자료가 맨 끝에 위치한 최악의 경우,

시간 복잡도가 O(n)이 된다.

 

 

이진 탐색은 주어진 배열이 정렬되어 있을 때 사용할 수 있는데,

중간 요소와 찾고자 하는 항목을 비교해서 중간보다 작으면 왼쪽,

반대의 경우 오른쪽을 탐색하는 방법이다.

 

이것도 앞선 병렬 정렬과 비슷하게 반씩 나눠서 비교하는 방법이라

시간 복잡도가 최악의 경우 O(log n)이 된다.

 

 

 

이 외에 탐색 알고리즘을 이해하기 위해 중요한 개념이 하나 있는데,

바로 그래프(Graph)다.

방향 그래프(Directed Graph)의 예시.

 

그래프는 정점(Vertex)과 간선(Edge)로 이루어진 자료 구조로,

방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉜다.

가중치 그래프(Weighted Graph)라는 간선에 가중치가 있는 그래프도 있다.

 

어디서 많이 낯이 익은 자료형이라고 생각했는데...

[출처: https://www.thedatahunt.com/trend-insight/deep-learning]

 

바로 딥러닝(Deep Learning)에서 쓰이던 자료 구조의 모습이었다.

딥러닝의 자료 구조가 대표적인 가중치 그래프 모양을 가지고 있다.

 

 

그래프의 구조를 알아봤으니,

이러한 구조에서 탐색은 어떻게 하는지가 궁금해진다.

 

그래프 탐색 방법은 크게 두 가지로 나뉜다.

깊이 우선 탐색(Depth-First Search, DFS)과

너비 우선 탐색(Breadth-First Search, BFS)이 바로 그것이다.

 

뭔가.... 뭔가 이름이 길어보여서 복잡해보이는데....

사실 별 거 없다.

 

나무 뿌리 같은 자료 구조의 그림

 

위 그림처럼 나무 뿌리같은 자료구조가 있다고 하자.

 

그럼 뿌리가 내리기 시작하는 부분에서부터

어디에 원하는 자료가 있는지 찾아야 하는데,

 

 

DFS, 깊이 우선 탐색의 경우

말 그대로 가능한 한 깊게 우선적으로 탐색하고 자료가 나올 때까지 그걸 반복하는 방법이다.

그림에서 1번 경로로 우선 탐색하고 그 다음 2번으로 넘어가는 식이다.

 

BFS, 너비 우선 탐색도 이름 그대로 넓게 먼저 찾아보겠다는 뜻이다.

그림에서와 같이 가장 큰 가닥부터 하나 하나 찾아보고

그 다음으로 큰 뿌리를 살펴보는 방식이다.

 

두 방식 모두 시간 복잡도는 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수) 라는 특징이 있다.

 

이로써, 오늘 다루고자 하는 정렬과 탐색 알고리즘에 대해 알아봤다.

다른 때보다 분량이 적은 것 같은데....

 

사실, 오늘은 아침부터 무슨 바람이 불었는지

Python 개발 환경을 다시 구축하다가

 

C 드라이브 용량이 부족해져버린 바람에... 이도 저도 못하고

Anaconda를 설치하고 여러 에러 코드를 마주쳐버려서

구글링에 정신이 팔린 날이었다.

 

Python, Anaconda 가상환경에 관련된 글은 따로 다룰 예정이다.

728x90

'TIL(Today I Learned)' 카테고리의 다른 글

중간 점검 : EventManager는 어떻게 동작하는가  (0) 2024.01.10
텍스트 RPG 게임, 팀원과 협업하기 - TIL#12  (0) 2024.01.09
텍스트 RPG 게임 만들기 (3), 알고리즘 기초 - TIL#10  (0) 2024.01.05
텍스트 RPG 게임 만들기 (2) - TIL#9  (0) 2024.01.04
C# 기초 문법 나머지, 텍스트 RPG 게임 만들기 - TIL#8 (2)  (0) 2024.01.03

'TIL(Today I Learned)'의 다른글

  • 현재글C# : 정렬, 탐색 알고리즘 - TIL#11

관련글

티스토리툴바