[멋쟁이사자처럼 부트캠프 TIL회고] Unity 게임개발 3기 22일차

오늘 배울 것 : 정렬(in 알고리즘)

 

프로그래밍 언어에서 알고리즘이란 ? 

• 프로그래밍에서 문제를 해결하기 위한 단계적 절차나 방법을 의미
• 특정 작업을 수행하거나, 결과를 얻기 위해 따라야 할 '명확하고 정확한 지시사항'의 집합

알고리즘의 주요 특징

• 입력 : 알고리즘은 하나 이상의 입력을 받음
• 출력 : 알고리즘은 하나 이상의 결과를 생성
• 명확성 : 각 단계는 모호하지 않고 명확해야 함
• 유한성 : 알고리즘은 유한한 수의 단계 후에 반드시 종료되어야 함
• 효율성 : 알고리즘은 가능한 한 효율적으로 설계되어야 함

종류

• 정렬 알고리즘 : 버블 정렬, 퀵 정렬, 병합 정렬 등
• 검색 알고리즘 : 선형 검색, 이진 검색 등
• 그래프 알고리즘 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라 알고리즘 등
• 동적 프로그래밍 : 최적화 문제를 해결하는데 사용되는 기법
• 분할 정복 알고리즘 : 문제를 작은 부분으로 나누어 해결하는 방식
• 그리디 알고리즘 : 각 단계에서 최적의 선택을 하는 방식

알고리즘은 프로그램 성능 향상, 복잡한 문제 해결을 위해 필수적임

 

정렬

정렬

• 데이터들을 특정한 기준에 따라 줄세우는 것 ( Ex : 오름차순, 내림차순)

버블 정렬(Bubble Sort)

 버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘임

우선 코드를 보면

public void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // 두 원소 교환
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

arr[j] 가 그 다음 원소인 arr[j +1]보다 크다면 그 둘을 바꾸게 된다. 

이걸 j = 0부터 j < n-i -1까지 반복하게 되는데 이러면 제일 큰 원소가 끝 부분에 가게 된다.

그리고 다음 반복에서 두 번째로 큰 원소가 끝 부분에서 하나 전에 가게 된다. 

이걸 계속해서 반복하다보면 오름차순 정렬이 완성되게 된다. 

이미지를 보고 싶다면 

참고 :

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

 

 

퀵 정렬( Quick Sort)

 퀵 정렬은 분할 정복 방법을 통해 정렬하는 알고리즘.

pivot, 즉 기준점을 선택하는 방법에 따라 3가지로 구현할 수 있음

1. low, 배열의 첫 번째 원소를 기준으로 정렬하는 방법

2. high, 배열의 마지막 원소를 기준으로 정렬하는 방법

3. 배열의 중간 원소를 잡아서 기준으로 배열하는 방법

 

코드로 구현해 본 것은 이 중 2번째 방법이다. 

public void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pi = Partition(arr, low, high);
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

private int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp1 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp1;

    return i + 1;
}

재귀 함수의 형태로 정렬이 된다. 

 

과정을 살펴보자

QuickSort는 재귀함수로 일단 분할 기능을 수행하고, 분할되어서 나온 기준값으로 또 다시 QuickSort를 반복하게된다.

제일 중요한 Partition 함수를 분해해보자. 

 

기준점인 Pivot을 배열 상의 가장 끝에 있는 원소(high)로 잡는다. 

그리고 교환할 원소의 인덱스인 i를 low -1 (0)으로 설정한다. 이는 한 칸씩 앞으로 가며 진행될 것이다. 

 

반복문

j는 배열의  첫 번째 원소부터, 한 칸 씩 앞으로 가며 진행되는데 

만약 j번째 있는 원소가 기준점( high이자 pivot) 보다 작다면

i를 1 더해주고, i번째 원소와 j번째 있는 원소를 뒤바꾼다. 

즉, 배열의 첫 번째 원소에 기준점보다 작은 원소를 넣겠다는 뜻이다.

이를 반복해주면, 배열의 두 번째 원소도, 세 번째 원소도 기준점보다 작게될 것이다.

(그렇지 않은 경우도 있다, 마지막 원소가 굉장히 작을경우)

이 과정을 끝내면, 모든 pivot점보다 작은 원소들이 i +1 (마지막에 교체한 원소의 다음 원소) 의 왼쪽에 모두 가 있게 된다.

(순서대로 가 있지 않다는 점에 주의)

 

그리고 기준점과 마지막 교체한 원소의 다음 원소(i + 1) 와 교체해준다. 

그럼 기준점의 위치는 확정된다. (왼쪽에는 기준점보다 낮은, 오른쪽에는 기준점보다 높은 원소들이 존재함)

 

그리고 QuickSort()를 왼쪽, 오른쪽으로 나눠서 다시 진행하고 이걸 반복한다. 

(이때 들어가는 매개변수를 올바르게 설정해줌)

 

이렇게 Quick Sort가 완성된다. 

 

 

병합 정렬(Merge Sort)

Merge Sort

• 분할 정복 알고리즘 , 배열을 더 작은 부분으로 나누어 정렬함.\
• 재귀 방식을 이용해 배열을 작은 부분 부분으로 분할하고 Merge 함수를 이용해 정렬하며 병합
• 게임 오브젝트의 점수 정렬이나, AI 의사 결정 과정에서 활용할 수 있음

 

코드는 크게 두 부분으로 나뉜다. 

1. MergeSort( int[] arr, int left, int right]

• 배열과 맨 왼쪽에 있는 원소의 인덱스 넘버인 0 , 마지막에 있는 원소의 인덱스 넘버인 right를 매개변수로 받음

2. Merge( int [] arr, int left, int middle, int right)

• 위에 더해서 MergeSort에서 계산한 값인( left + (left + right)/2 ) middle을 매개변수로 받는다.

 

 

1. MergeSort ()

이 부분은 주어진 배열을 최대한 분할하는 부분이다. 

균등하게 분할하기 위해서 middle 지점을 left + (left + right)/2로 잡아 주고 

middle 지점을 기준으로 좌 우로 나뉜 배열들을 또 다시 분할해준다. (양쪽 모두)

무한히 반복될 순 없으므로, 배열의 크기가 1이 되면 멈출 수 있도록 조건을 달아준다. ( if ( left < right))

분할이 완료되었으면, 다시 병합하는 과정을 Merge 함수를 통해 해 준다. 

 

public void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int middle = left + (right - left) / 2;
        MergeSort(arr, left, middle);
        MergeSort(arr, middle + 1, right);
        Merge(arr, left, middle, right);
    }
}

 

2. Merge()

 분할된 배열을, 다시 재정렬하며 병합하는 함수다.

재정렬하기 위해서는 새로운 배열이 필요하다. 이 배열의 크기는 left, right, middle을 조합해서 정한다.

left부터 middle 까지 포함할 새 배열의 크기를 n1 ( middle - left + 1// middle을 포함하므로)

middle +1 부터 right 까지 포함할 새 배열의 크기를 n2 ( right - middle// middle을 포함하지 않으므로)

그리고 새 배열을 n1, n2로 만들고 각각 이름을 L, R로 붙여준다. 

이제 새 배열에 원소들을 넣어준다. left 값과 middle 값을 기준으로 ,배열의 크기만큼 원래 함수에서 가져온다.

private void Merge(int[] arr, int left, int middle, int right)
{
    int n1 = middle - left + 1;
    int n2 = right - middle;

    int[] L = new int[n1];
    int[] R = new int[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[middle + 1 + j];

지금까지의 과정은 새 배열을 만들고, 배열 안에 값을 순서대로 넣어준 것이다. 예제와 함께 진행해보자면

1. 처음에 [38, 27, 43, 3, 9, 82, 10] 라는 배열이 주어졌다면, 
2. MergeSort를 통해 모든 배열이 [38, 27, 43, 3]과 [9, 82, 10]으로 분할
3. MergeSort를 반복해 결국 [38], [27], [43], [3], [9], [82], [10]이 될 때까지 분할 
4. Merge 함수로 들어온 변수는 결국 ( 0, 0, 1), 즉 left는 0번째, middle도 0번째, right는 1번째이고 
   각각의 값은 0번째는 {38}, 1번째는 {28} 임.
5. 바로 위의 코드를 통해 n = 1, n2 = 1  >>> L[]  = { 38 } , R[] = { 28 } 이 됨. 

이제 이 두 L과 R 배열의 원소들을 비교하며 (재정렬) arr에 집어넣을 것이다. 

지금은 각각 원소가 하나씩 존재하지만, 병합되고 또 병합되는 과정에서 원소가 늘어날 것이므로

몇 번째 원소인지를 알려줄 변수를 두 개만든다 (i1, j1).

병합되어진 배열의 몇 번째 원소인지를 표현할 변수도 만든다(k).

우리에게 주어진 조건은 다음과 같다.

1.  L와 R은 이미 그 안에서는 정렬된 채로 우리에게 주어진다. (정렬 과정을 거쳐 병합된 것들이 들어오므로)
2.  L과 R의 최대 원소의 갯수 차이는 1이다. ( MergeSort가 배열을 중간점으로 나누므로)

그렇다면, L의 첫 번째 원소와 R의 첫 번째 원소를 비교하고 더 작은 것을 배열에 집어넣고,

계속해서 집어넣은 원소를 제외한(L에서 넣었다고 가정) L의 두 번째 원소와 R의 첫 번쨰 원소를 비교하고,

이를 반복하다가 L 혹은 R의 모든 원소가 다 배열에 들어갔다면, 아직 원소가 남아 있는 L 혹은 R의 원소들을

뒤에 그냥 붙여주기만 한다면 ( 이미 정렬되어 있는 배열이므로 ) 정렬이 완성될 것이다. 

 

이를 코드로 구현한다면 다음과 같다. 

 int i1 = 0, j1 = 0;
    int k = left;
    while (i1 < n1 && j1 < n2)
    {
        if (L[i1] <= R[j1])
        {
            arr[k] = L[i1];
            i1++;
        }
        else
        {
            arr[k] = R[j1];
            j1++;
        }
        k++;
    }

    while (i1 < n1)
    {
        arr[k] = L[i1];
        i1++;
        k++;
    }

    while (j1 < n2)
    {
        arr[k] = R[j1];
        j1++;
        k++;
    }

 

 처음의 while문이 원소들을 비교해서 하나씩 배열에 집어넣는 것이고,

나머지 2개의 while문은 남은 원소들을 배열에 집어넣는 것이다. 

 

계속해서 예제를 통해 알아보면 

   6.  Merge(0,0,1)L과 R을 병합하며 정렬해 [ 28, 38 ]배열이 됨.

   7.  Merge(2,2,3) 호출 : [43] , [3]이 [ 3, 43 ] 배열이 됨

   8.  Merge(4,4,5) 호출 : [9], [82]이 [9, 82] 배열이 됨

   9.  Merge(6,6,6) 호출 : [10]

  10. Merge(0,1,3) 호출// 6번과 7번의 left, right를 기준으로 middle을 구하면 됨 : [27, 38], [3, 43] > [3, 27, 38, 43]

  11. Merge(4,5,6) 호출 : [9, 82], [10] >>> [9, 10, 82]

  12. Merge(0,3,6) 호출 : [3, 27, 38, 43], [9, 10, 82] >>>  [3, 9, 10, 27, 38, 43, 82] 

 

이와 같이 MergeSort를 할 수 있다. 

 

장단점 비교

1. Bubble Sort

 

시간 복잡도

• 최악 : O(n²) (거의 정렬되지 않았을 경우 모든 요소 비교)
• 평균 : O(n²)
• 최선 : O(n) (이미 정렬된 경우, 한 번만 순회) 

공간 복잡도

• O(1) ( 추가 공간 필요 없음 )

장점

• 구현이 매우 간단
• 배열의 크기가 작거나, 거의 정렬된 경우 유용

단점

• 성능이 매우 낮음 (O(n²)).
• 큰 데이터셋에 비효율적

배열의 크기가 작거나, 거의 정렬된 상태일때 적합

 

2. Quick Sort

 

시간 복잡도

• 최악 : O(n²) (이미 정렬된 배열에서 첫 번째 요소를 피벗으로 선택하는 경우)
• 평균 : O(n log n) (랜덤 피벗 선택 시)
• 최선 : O(n log n) 

공간 복잡도

• 평균 : O(log n) (재귀 호출 스택)
• 최악 : O(n) 한쪽으로 치우진 경우

장점

• 평균적으로 매우 빠름(시간복잡도 O(n log n))
• 대부분의 실전에서 우수한 성능

단점

• 최악의 경우 성능이 나쁨 ( O(n²))
• 안정 정렬이 아님 (동일한 값의 순서가 바뀔 수 있음)

대규모 데이터셋이나 메모리가 제한된 환경에서 적합(추가 메모리 사용이 적음).

 

3. MergeSort

 

시간 복잡도

• 최악 : O(n log n) (분할 + 병합 과정)
• 평균 : O(n log n)
• 최선 : O(n log n)

공간 복잡도

• O(n) (병합 과정에서 추가 배열 필요

장점

• 항상 O(n log n)의 안정적 성능 보장
• 안정 정렬로, 동일 값의 순서 유지
• 분할이 동시에 진행될 수 있어 병렬 처리에 적합

단점

• 추가 메모리 공간이 필요 ( 공간복잡도 O(n))
• 데이터가 큰 경우 메모리 효율이 낮아질 수 있음

데이터의 크기가 크고, 안정 정렬이 필요하거나 외부 정렬시 이용

 

요약하자면 

 

• Bubble Sort: 간단하고 작은 배열에 적합하지만, 성능이 낮음.
• Quick Sort: 평균적으로 가장 빠르며, 대부분의 대규모 정렬 작업에서 우수.
• Merge Sort: 안정성이 필요하거나 병렬 처리가 필요한 상황에서 유리.

 

A* 알고리즘은 주말에...따로 봐야겠다..