내일배움캠프 8일차 TIL : C#기초4 알고리즘, 정렬

---

■ 학습 개요

○ 오늘 계획

1. 1, 2, 3, 4 주차 강의 정리 복습
2. 5주차 강의 1, 2강 복기 및 노트 정리
3. 팀프로젝트 TextRPG 중간점검 및 GameManager 수정
   
   

○ 학습 회고

1. 1, 2, 3 주차 강의까지는 이제 확실히 공부가 끝난 것 같다. 하지만 4주차에 포함된 델리게이트, LINQ, 람다 등 고급 문법은 아직 어려워서 앞으로도 지속적인 복습이 필요하다.

2. 알고리즘은 아무래도 같은 C계열이어서 그런지 C++과 크게 다를거 없는 것 같다. 하지만 헛갈리는 개념들이 많으니 익숙해질 때까지 복기 해야겠다.

○ TIL 작성계획

1. 본인이 중요하게👍 생각하거나 헛갈리는 부분😥을 집중 작성할 계획

---

■ 학습 내용 정리

○ 알고리즘

• 노트정리 링크
• Big O 표기법은 알고리즘의 효율성을 나타내는 표기법
• 표기법 계산 : 상수 버리기, 최고 차항만 남기기, 다항식의 경우 최고 차항만 고려, 연산자 상수 무시
• 시간 복잡도 : 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도, 입력 크기에 대한 연산 횟수로 측정
• 공간 복잡도 : 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명함
• 예제

public static int[] RemoveDuplicates(int[] array)
{
    List<int> distinctList = new List<int>();

    foreach (int num in array)
    {
        if (!distinctList.Contains(num))
        {
            distinctList.Add(num);
        }
    }

    return distinctList.ToArray();
}
// 시간 복잡도 : O(n)
// 공간 복잡도 : O(n)

○ 정렬 알고리즘

• 노트정리 링크
• 선택 정렬 ( Selection Sort )
  • 시간 복잡도 : 평균, 최악 모두 O(n^2)
  • 공간 복잡도 : O(1) (상수 크기의 추가 공간이 필요하지 않음)
    // 가장 작은 원소를 찾아서 맨 앞에 위치하는 것을 반복하여 정렬하는 알고리즘

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

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;
}

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

• 삽입 정렬 ( Insertion Sort )
  • 시간 복잡도 : 최악 O(n^2), 하지만 정렬되어 있는 경우에는 O(n)
  • 공간 복잡도 : 공간 복잡도 : O(1) (상수 크기의 추가 공간이 필요하지 않음)
    // 현재 위치에서 그 이하의 배열을 정렬된 배열 부분에 삽입하는 방법으로 정렬하는 알고리즘

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

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;
}

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

• 퀵 정렬 ( Quick Sort )😥
  • 시간 복잡도: 평균 O(n log n), 최악 O(n^2)
  • 공간 복잡도: 평균 O(log n), 최악 O(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);
}

• 병합 정렬 ( Merge Sort )😥
  • 시간 복잡도: 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);
}