24년 8월 25일 알고리즘 공부 3일차

스파르타에서 제공 해주는 알고리즘 강의가 있었다. ㅎㅎ.. 알고 있었지만 그 때 당시에는 대체 무슨 소리일까 하고 안 봤었는데 지금 다시 보니 많이 도움이 된 것 같다. 

 

 

Big O 표기법 :

알고리즘의 효율성을 나타내는 표기법. 얼마나 많은 시간이나 공간을 필요로 하는지 설명. 

Big O 표기법은 알고리즘의 최악의 경우 성능을 나타내므로 알고리즘의 효율성을 과장 하지 않는다. 

 

빅오 표기법 계산 방법 : 

1. 상수는 버린다. 

빅오 표기법을 할 때는 몇 번을 계산 하는지는 실질적으로 입력이 천 번이 되고, 만 번이 되고 한다면 상수값은 크게 중요하지 않다고 한다. 그래서 +1을 하든 +10을 하든 상수값은 버린다. 

 

2. 최고차수 항목만 남긴다. 

빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춘다고 한다. 

따라서 가장 큰 차수의 항목만을 남기고 나머지는 버린다. 예를 들어 O(n^2 + n)의 경우 O(n^2)로 간소화 할 수 있다고 한다.

 

3. 다항식의 경우 최고 차수 항목만 고려한다. 

다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춘다고 한다. 상수항이나 낮은 차수의 항목은 무시, 예를 들어 

O(3n^3 + 5n^2 + 2n +7)의 경우 O(n^3)로 간소화 할 수 있다고 한다. 

상수는 버리고 가장 높은 것만 남긴다. 

 

4. 연산자 상수 무시

빅오 표기법에서는 연산자도 무시한다. 

예를 들어서 O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화 할 수 있다. 

 

Big O 표기법의 예

O(1) : 입력 크기에 상관 없이 항상 일정한 시간이 걸릴 때 

O(n) : 입력 크기에 비례하여 시간이 걸릴 때 

O(n^2) : 입력 크기의 제곱에 비례하여 시간이 걸릴 때

O(log n) : 로그에 비례하여 시간이 걸릴 때 

 

시간 복잡도

시간복잡도는 시간을 실제로 체크 하는 것이 아니라 연산의 횟수를 체크 하는 것이다. 

입력에 따른 연산의 횟수가 얼마나 나오냐 라는 것이고, 빅오 표기법을 사용 한다. 

 

 

공간 복잡도

입력에 들어오는 것에 따라서 메모리를 얼마나 더 사용 하는 것이다. 빅오표기법을 사용한다. 

메모리를 더 만들지 않으면 O(1)

 

 

예제문제 1

다음은 주어진 배열에서 특정 숫자를 찾는 메서드 FindNumber 입니다. 배열의 크기는 n이라고 가정합니다. 해당 숫자가 배열에 존재하면 true를 반환하고, 존재하지 않으면 false를 반환해야 합니다. 이때, 시간 복잡도와 공간 복잡도를 계산하세요.

 

public static bool FindNumber(int[] array, int target)
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == target)
        {
            return true;
        }
    }
    return false;
}

 

이 함수의 시간 복잡도는 어떻게 말을 해야 하지. 계산을 n번만 하기에 O(n), 공간복잡도는 메모리 증가가 없어서 O(1)이다. 

 

정답 : 시간 복잡도: O(n), 공간 복잡도: O(1)

 

 

예제문제 2

다음은 n개의 숫자로 이루어진 배열에서 최대값을 찾는 메서드 FindMax 입니다. 배열의 크기는 n이라고 가정합니다. 이때, 시간 복잡도와 공간 복잡도를 계산하세요.

 

public static int FindMax(int[] array)
{
    int max = int.MinValue;

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

    return max;
}

 

시간복잡도는 O(n)이고, 공간복잡도는 int를 하나 생성을 하니까 O(n)? 인 것 같다. 

 

정답: 시간 복잡도 : O(n), 공간복잡도 : O(1)

이유: 

공간 복잡도는 알고리즘이 사용 하는 추가 메모리 양을 나타낸다. 여기서 중요한 점은 입력 크기와 추가 메모리 사용량의 관계를 이해 하는 것이다. 

이 함수의 입력 크기는 입력 배역 array의 길이이다. 

추가 메모리 사용량은 알고리즘이 사용 하는 변수나 자료구조에 의해 결정 된다. 여기서 '추가'라는 말은 함수가 입력 데이터 외에 추가로 사용 하는 메모리를 말한다. 

 

위 코드에서 사용 되는 추가 메모리는 다음과 같다. 

1. int max : 최대값을 저장 하기 위해 사용

2. int i : for 반복문을 위해 사용

 

이 변수들은 상수 크기의 메모리 공간을 차지 한다. 즉, 이 변수들이 사용하는 메모리 양은 입력 배열의 크기와 상관이 없고 항상 일정 하기 때문에 공간 복잡도는 O(1)이 되는 것이다. 상수 공간 복잡도로 간주.

공간복잡도가 O(n)이 되려면, 입력 크기에 비례해서 메모리 사용이 증가 해야 한다. 예를 들어 입력배열의 복사본을 만들거나, n개의 추가적인 변수를 사용 하게 될 때 해당이 된다. 

 

따라서 이 함수에서 사용 된 int  max나 int i 같은 경우 입력 크기에 관계 없이 일정한 메모리만 사용 하기 때문에 공간 복잡도는 O(1)이 된다. 

 

 

 

예제 문제 3

다음은 n개의 숫자로 이루어진 배열에서 중복된 숫자를 제거하는 메서드 RemoveDuplicates 입니다. 배열의 크기는 n이라고 가정합니다. 중복된 숫자가 제거된 새로운 배열을 반환해야 합니다. 이때, 시간 복잡도와 공간 복잡도를 계산하세요.

 

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)이다. 

정답 : 시간 복잡도: O(n), 공간 복잡도: O(n)

 

 

정렬 알고리즘 

정렬 알고리즘은 CS에서 중요한 주제 중에 하나이다. 

주어진 데이터 세트를 특정순서로 배열 하는 방법을 제공 한다. 

 

 

1) 선택 정렬(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);
}

작은 숫자를 저장 할 용도인 int 하나를 생성을 해서 반복문을 다 돌리고 나서 배열의 i번째에다가 찾아낸 작은 수의 인덱스로 변경을 하고, 기존에 있던 i번째에 있는 데이터를 작은 숫자가 있던 공간에 저장을 시키는 방법이다. 

이렇게 해서 시간 복잡도는 O(n^2)이 되고, 공간 복잡도는 O(1)이다. 

하지만 반복문을 전부 돌기 때문에 빠른 알고리즘은 아니다. 

 

 

2) 삽입 정렬(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);
}

 

처음 반복문을 1번 부터 돌게 하고 j에 -1을 해주게 하고 key값을 저장 한다. 

그리고 조건문을 만들어서 정렬이 되게 만들고 마지막에는 저장 해둔 key값을 넣어줌으로써 정렬을 하게 했다. 

항상 O(n^2)이 아니라 정렬이 되어 있어서 while이 실행을 안 할 경우면 O(n)이 된다.

 

 

3) 퀵 정렬(Quick Sort)

퀵 정렬은 피벗을 기준으로 작은 요소들은 왼 쪽으로, 큰 요소들은 오른 쪽으로 나누고 이것을 재귀적으로 계속 해서 정렬 하는 방법이다. 

시간 복잡도 : 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)이다. 

공간 복잡도 : 평균적으로 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);
}

 

촤하하하하하!!!! 나중에 분석 해주마.

 

 

4) 병합 정렬(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);
}

흠.