11.16 (TIL)

알고리즘 ( Algorithm )

1) 알고리즘 개념

알고리즘은 문제를 해결하기 위한 명확한 절차나 방법

알고리즘은 입력을 받아 원하는 출력을 생성하기 위한 절차

알고리즘은 입력, 출력, 명확한 단계, 실행 가능성의 특성

알고리즘은 주어진 입력에 대해 정확하고 일관된 결과를 제공

알고리즘은 컴퓨터 프로그래밍뿐만 아니라 다양한 분야에서 사용

 

2) 알고리즘의 중요성

효율적인 알고리즘은 컴퓨터 프로그래밍에서 매우 중요

같은 문제를 해결하는 두 알고리즘이 있다면,

효율적인 알고리즘은 덜 효율적인 알고리즘보다 더 적은 컴퓨팅 자원(시간, 메모리 등)을 사용

가능한 한 효율적인 알고리즘을 사용하는 것이 중요

 

 

Big O 표기법

1) Big O 표기법

Big O 표기법은 알고리즘의 효율성을 나타내는 표기법

Big O 표기법은 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지를 설명

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

 

2) Big O 표기법의 예

O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.

O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다.

O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.

O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.

 

3) Big O 표기법 계산

1. 상수 버리기

알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살피자.

상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버린다.

예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있다.

 

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)로 간소화할 수 있다.

 

 

시간 복잡도 (Time Complexity)

1) 시간 복잡도란?

시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도

코드의 실행 시간을 실제 시간(초)으로 측정하는 것이 아니라, 입력 크기에 대한 연산 횟수로 측정

Big-O 표기법을 사용하여 표시함

 

간단 예제1

int Sum(int n)
{
    int sum = 0;
    for (int i = 0; i <= n; i++)
    {
        sum += i;
    }
    return sum;
}

// for 루프가 0부터 n까지 순회하며 합계를 계산합니다. 따라서 n회의 연산이 필요하며, 시간 복잡도는 O(n)

 

간단 예제2

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

// 두 개의 중첩된 for 루프를 포함

// 각 루프는 0부터 n까지 순회하므로, 전체 연산 횟수는 n^2이며, 시간 복잡도는 O(n^2)

 

간단 예제3

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

// 재귀적으로 피보나치 수열을 계산하는 함수

// 각 호출마다 두 번의 재귀 호출을 수행하므로, 시간 복잡도는 O(2^n)

// 매우 비효율적인 방법으로, 실제 문제 해결에서는 동적 프로그래밍 등의 기법을 사용해 효율성을 높이는 것이 중요

 

간단 예제4

1번

 

def print_first_element(arr):
    """
    배열의 첫 번째 요소를 출력하는 함수
    :param arr: 입력 배열
    """
    if len(arr) > 0:
        print(arr[0])

# 예시 배열
my_array = [1, 2, 3, 4, 5]

# 함수 호출
print_first_element(my_array)

// print_first_element 함수는 배열의 첫 번째 요소를 출력하는데, 배열의 크기에 상관없이 오직 한 번의 연산만 필요

// 함수의 시간 복잡도는 O(1). 이를 "상수 시간"이라고 부름

 

 

2번

 

def linear_search(arr, target):
    """
    선형 탐색 알고리즘
    :param arr: 탐색할 배열
    :param target: 찾고자 하는 값
    :return: 찾고자 하는 값의 인덱스 (찾지 못한 경우 -1)
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 값을 찾으면 인덱스를 반환
    return -1  # 값을 찾지 못한 경우 -1 반환

 

// 선형 탐색(Linear Search)으로 구현

// 알고리즘의 시간 복잡도는 배열의 길이에 선형으로 비례하므로 O(n)

// n은 배열의 길이를 나타냄

// 최악의 경우 배열을 처음부터 끝까지 모두 확인해야 하기 때문에 선형 시간이 걸림

// 주의 : Big O 표기법에서 상수 계수는 무시되므로, 선형 탐색의 시간 복잡도가 O(2n)이 아니라 O(n)으로 표기

 

공간 복잡도 (Space Complexity)

1) 공간 복잡도란?

코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명

Big-O 표기법을 사용하여 표시

 

간단 예제

def calculate_sum(arr):
    """
    배열의 합을 계산하는 함수
    :param arr: 입력 배열
    :return: 배열의 합
    """
    # 합을 저장할 변수
    total_sum = 0

    # 배열의 각 요소를 순회하면서 합을 계산
    for element in arr:
        total_sum += element

    return total_sum

# 예시 배열
my_array = [1, 2, 3, 4, 5]

# 함수 호출
result = calculate_sum(my_array)

# 결과 출력
print(result)

 

// calculate_sum 함수는 배열의 합을 계산하기 위해 total_sum이라는 변수를 사용

// 변수는 입력 배열의 크기에 비례하지 않고, 상수 크기의 메모리를 차지, 따라서 이 함수의 공간 복잡도는 O(1)

// 주의 : 공간 복잡도에서도 Big O 표기법이 사용되며, 입력 크기에 대한 함수로 표현 , 그러나 일반적으로 상수 크기의 메모리를 사용하는 경우에는 O(1)으로 표기

 

간단 예시2

// 시간 복잡도: 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, 5 };

// FindMax 메서드의 시간 복잡도: O(n), 공간 복잡도: O(1)
int max = FindMax(arr);

// 배열의 크기에 비례하여 실행 시간이 증가하므로 O(n)이라 할 수 있습니다. 또한 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다.

// FindMax2 메서드의 시간 복잡도: O(n^2), 공간 복잡도: O(1)
int max2 = FindMax2(arr);

// 이중 반복문을 사용하기 때문에 배열의 크기에 제곱에 비례하여 실행 시간이 증가하므로 O(n^2)이라 할 수 있습니다. 이 알고리즘은 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다.

 

"추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)"이라는 주장은 일반적으로 맞다.

그러나 이것은 "추가적인" 메모리 공간을 강조하는 것.

알고리즘이 상수 개의 변수를 사용하고 입력 크기에 비례하지 않는 메모리를 사용한다면, 공간 복잡도는 O(1)로 간주.

 

여기서 중요한 것은 알고리즘이 동적 메모리를 할당하거나 입력 크기에 따라 선형적으로 메모리를 사용하는 경우, 그것은 O(n) 공간 복잡도를 가질 수 있다는 것

 

"일반적으로 상수 크기의 메모리를 사용하는 경우에는 O(1)"이라는 주장은 일반적인 관례

알고리즘이 상수 개의 고정된 크기의 메모리를 사용한다면 O(1)으로 간주

그러나 이 역시 추가 메모리 사용이 없는 경우에 한정

 

따라서 두 경우 모두 추가 메모리를 사용하지 않기 때문에 O(1)로 간주할 수 있다.

알고리즘이나 코드에 따라서는 추가 메모리를 사용하는 경우가 있을 수 있으므로 일반적인 규칙은 "추가적인 메모리가 사용되지 않을 때 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;
}

• 시간 복잡도: 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)
• 공간 복잡도: 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)

 

 

알고리즘 시각화 참고 사이트

https://visualgo.net/en