알고리즘

개념

• 문제를 해결하기 위한 명확한 절차나 방법
• 입력을 받아 원하는 출력을 생성하기 위한 절차
• 속도나 성능에 대한 고려
• 주어진 입력에 대해 일관된 결과를 제공해야 함

중요성

• 효율적인 알고리즘은 프로그래밍에서 매우 중요
• 같은 문제를 해결하는 두 알고리즘 중
  더 효율적인 알고리즘은 더 적은 자원을 소모함(메모리, 시간).
• 그러므로 효율적인 알고리즘을 사용하는 것이 중요.

효율성

Big O 표기법

• 알고리즘의 효율성을 나타내는 표기법 중 하나
• 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는 지 설명
• 주로 알고리즘의 최악의 경우 성능을 나타냄.

예시

1. O(1) : 상수 시간, 입력의 크기에 상관없이 항상 일정한 시간 소요
2. O(n) : 선형 시간, 입력의 크기에 비례해서 시간 소요
3. O(n ^ 2) : 이차 시간, 입력 크기의 제곱에 비례해서 시간 소요
4. O(log n) : 지수 시간, 입력 크기의 로그에 비례해서 시간 소요

계산법

1. 상수버리기
   O(3n) => O(n), O(2n ^ 2) => O(n ^ 2)
2. 최고 차수 항목만
   O(2n ^ 2 + 4n) => O(n ^ 2)
3. 다항식 일때, 최고 차수 항목만
   O(3n ^ 3 + 2n ^ 2 + 4n) => O(n ^ 3)
4. 연산자 상수 무시
   O(3n ^ 3 + 4n) => O(n ^ 3)

시간 복잡도

얼마나 오래 걸리는지.
시간 초가 아니라 연산 횟수로 계산

for(int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
    	Console.WriteLine("{0}\n", i + j);

• n의 횟수만큼 이중 반복문을 진행 : O(n^2)

예시 : 피보나치

int Fibonacci(int n)
{
    if (n <= 1) 
    	return n;
    else 
    	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

• 재귀 함수로 구성된 함수.
• 내부에서 재귀가 2번 실행되므로 O(2 ^ n)
• 이는 매우 비효율적인 방법이므로, 실제 문제 해결에는 동적 프로그래밍 등의 기법 사용해서 효율성을 높여야함.

공간 복잡도

코드가 사용하는 메모리의 크기를 측정.

예시

// 시간 복잡도: O(n)
int FindMax(int[] arr)
{
    int max = arr[0];

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

    return max;
}

// 시간 복잡도: O(n^2)
int FindMax2(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        bool isMax = true;

        for (int j = 0; j < arr.Length; j++)
        {
            if (arr[j] > arr[i])
            {
                isMax = false;
                break;
            }
        }

        if (isMax)
        {
            return arr[i];
        }
    }

    return -1;
}

int[] arr = new int[]{1,2,3,4};
int max = FindMax(arr);
// 시간 복잡도 : O(n)
// 공간 복잡도 : O(1)
// 입력받은 배열을 그대로 사용. => 메모리 변화가 없음.

int max2 = FindMax2(arr);
// 시간 복잡도 : O(n ^ 2)
// 공간 복잡도 : O(1)
// 입력받은 배열을 그대로 사용. => 메모리 변화가 없음.

예시 2

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)

정렬

주어진 데이터 세트를 알맞은 순서로 배열하는 것
오름차순, 내림차순, 사전식...

종류

1. 선택 정렬 (Selection Sort)
2. 삽입 정렬 (Insertion Sort)
3. 퀵 정렬 (Quick Sort)
4. 병합 정렬 (Merge Sort)

1. 선택 정렬

배열에서 최솟값이나 최댓값을 찾아 맨 앞이나 뒤로 교환하는 방법.
가장 구현하기 쉽고 아이디어가 간단하지만 성능은 좋지 못함.

• 시간 복잡도 : O(n ^ 2)
  최악, 평균 모두 동일
• 공간 복잡도 : O(1)
  추가 공간이 필요하지 않음

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

// 이중 for문 = 시간복잡도 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;
        }
    }
	// 가장 작은 것과 swap
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

2. 삽입 정렬

정렬되지 않은 요소를 가져와서 정렬된 부분의 적절한 곳에 삽입.

• 시간 복잡도 :
  최악의 경우 O(n ^ 2), 정렬된 경우 O(n)
• 공간 복잡도 : O(1)
  추가 공간이 필요하지 않음

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

// 이중 for문
for (int i = 1; i < arr.Length; i++)
{
    int j = i - 1;
    int key = arr[i]; // 기준점

	// 앞의 숫자가 기준점보다 크다면 뒤로 swap => 뒤로 밀어냄
    // 앞에 숫자가 없거나 작을 때까지 반복
    while (j >= 0 && arr[j] > key)
    { 	
        arr[j + 1] = arr[j];
        j--;
    }
	
    //이번 기준점의 위치 찾기 완료
    arr[j + 1] = key;
}

3. 퀵 정렬

피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬.
(분할 정복 방법)
대다수 라이브러리에서 sort라고 하면 이 방식을 사용,

• 시간 복잡도 :
  최악은 O(n^2)이지만 평균적으로 O(n log n)
• 공간 복잡도 :
  평균 O(log n), 최악 O(n) 재귀호출에 필요한 스택 공간

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

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 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[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
QuickSort(arr, 0, arr.Length - 1);

4. 병합 정렬

배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후 병합하는 방법.
(분할 정복 방법)

• 시간 복잡도 : 모든 경우 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);

C# Sort

실제로 사용할 때 이런 식으로 다 구현하면서 쓰는 경우는 거의 없음.
이유는 대다수의 언어가 기본 라이브러리에 Sort 기능을 제공하고 있기 때문.
C#에서도 물론 sort를 제공하고 있음.

Sort

• 매개변수로 입력한 배열을 직접 수정해서 반환값이 없음.

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();