알고리즘의 시간 복잡도 분석 (1)

• 알고리즘 공부를 시작하면서 읽었던 ⟪ 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 ⟫ 시리즈에 대한 내용을 정리해보려고 합니다!
• 책에는 C++ 코드를 위주로 설명하고 있지만, 제가 현재 코딩 테스트나 대회에서 사용하는 파이썬 코드로 따로 정리하고 싶었습니다.
• 먼저 시간 복잡도 분석에 대한 부분입니다.

 

개요

• 알고리즘의 속도를 효과적으로 측정하는 것은 더 빠른 알고리즘을 개발하는 데 필수적입니다.
• 가장 간단한 방법은 두 알고리즘을 구현하여 동일한 입력에 대한 실행 시간을 비교하는 것이지만, 알고리즘의 효율성을 평가하는 일반적인 기준으로는 부족할 수 있습니다.
• 실행 시간은 다양한 외부 요인에 영향을 받기도 하고, 같은 알고리즘이라도 입력의 크기나 특성에 따라 수행 시간이 달라질 수 있습니다.

 

• 알고리즘의 수행 시간을 결정하는 주요 요소는 반복문입니다. 대부분의 경우, 반복문의 수행 횟수를 입력 크기의 함수로 표현하여 알고리즘의 수행 시간을 측정합니다. 예를 들어, 배열 내에서 가장 많이 등장하는 숫자를 찾는 알고리즘은 배열의 크기 N에 따라 수행 시간이 달라지며, 이는 보통 $N^2$으로 표현됩니다.

# 주어진 배열에서 가장 많이 등장하는 숫자를 반환하기

# 주어진 배열 A에서 가장 많이 등장하는 숫자를 반환합니다.
# 만약 두 가지 이상 있을 경우 아무것이나 반환합니다.
def majority1(A: list) -> int:
    N = len(A)
    majority, majority_cnt = -1, 0
    for i in range(N):
        V, cnt = A[i], 0
        for j in range(N):
            if A[j] == V:
                cnt += 1
        # 지금까지 본 최대 빈도보다 많이 출현했다면 답을 갱신합니다.
        if cnt > majority_cnt:
            majority_cnt = cnt
            majority = V
    
    return majority

 

• 하지만, 입력의 특성에 따라 더 효율적인 방법을 사용할 수도 있습니다. 예를 들어, 100점 만점의 점수 배열에서 가장 많이 등장하는 숫자를 찾는 경우, 더 효율적인 알고리즘이 가능하답니다!

# 주어진 배열에서 가장 많이 등장하는 숫자를 반환하기 2

# A의 각 원소가 0부터 100 사이의 값일 경우 가장 많이 등장하는 숫자를 반환합니다.
def majority2(A: list) -> int:
    N = len(A)
    cnt = [0] * 101
    for i in range(N):
        cnt[A[i]] += 1
    # 지금까지 확인한 숫자 중 빈도수가 제일 큰 것을 majority에 저장합니다.
    majority = 0
    for i in range(1, 101):
        if cnt[i] > cnt[majority]:
            majority = i
    
    return majority

• 위 경우에는 반복문이 총 두 번 수행되므로, 전체 수행 횟수는 N+100이 됩니다. 그러나 큰 N에서는 100번 반복되는 부분이 수행 시간에 미치는 영향이 줄어들어, 결국 수행 시간은 주로 N에 의해 결정됩니다.

 

선형 시간 알고리즘

• 이동 평균은 시간에 따라 변하는 값들을 관찰할 때 유용한 통계적 기준입니다. 예를 들어, 월별로 측정된 몸무게 데이터에서 각 달의 이동 평균은 최근 몇 달 간의 평균 몸무게로 계산됩니다.
• 이를 계산하는 기본적인 방법은 각 달마다 지난 M개월 동안의 몸무게 합을 구하고 M으로 나누는 것입니다.

# 이동 평균 구하기

# 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구합니다.
def moving_average1(A: list, M: int) -> list:
    result = []
    N = len(A)
    for i in range(M-1, N):
        # A[i]까지의 이동 평균 값
        partial_sum = 0
        for j in range(M):
            partial_sum += A[i-j]
        result.append(partial_sum / M)
    return result

 

• 하지만 이 방법은 매우 비효율적일 수 있습니다. 예를 들어, 매일 몸무게를 측정하는 경우에는 계산량이 엄청나게 증가합니다.
• 이런 상황에서는 중복된 계산을 제거하는 것이 중요합니다. 즉, 각 새로운 이동 평균을 계산할 때 이전 이동 평균에서 가장 오래된 데이터를 빼고 새로운 데이터를 추가하는 방식으로 최적화할 수 있습니다.
• 이렇게 하면, 이동 평균의 계산은 선형 시간(즉, 입력 데이터의 크기에 비례하는 시간)에 가능해집니다.

# 선형 시간에 이동 평균 구하기

# 길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구합니다.
def moving_average2(A: list, M: int) -> list:
    result = []
    N = len(A)
    partial_sum = 0
    for i in range(M-1):
        partial_sum += A[i]
    for i in range(M-1, N):
        partial_sum += A[i]
        result.append(partial_sum / M)
        partial_sum -= A[i-M+1]
    return result

• 이런 최적화를 통해, 입력 데이터가 아무리 많아도 효율적으로 이동 평균을 계산할 수 있습니다.

 

선형 이하 시간 알고리즘

• 이진 탐색은 입력된 자료의 크기에 비례하는 선형 시간 알고리즘보다 빠르게 동작하는 효율적인 알고리즘입니다.
• 이진 탐색의 핵심은 중복된 계산을 줄이고, 필요한 정보만을 빠르게 추출하는 것입니다. 예를 들어, 사진이 시간 순으로 정렬되어 있다면, 가운데 사진을 먼저 확인하고, 이를 기준으로 필요한 부분만을 더 살펴보면 됩니다.
• 이진 탐색은 주어진 데이터를 절반씩 줄여가며 원하는 데이터를 빠르게 찾아내는 방식을 사용합니다. 매우 큰 데이터 세트에서도 빠르게 원하는 정보를 찾을 수 있는 효과적인 방법입니다.
• 이 방법은 앞선 선형 시간과는 다르게 선형 이하 시간(Sublinear time)에 작업을 완료할 수 있게 해준답니다!

 

지수 시간 알고리즘

• 알고리즘의 효율성을 평가할 때, 다항 시간과 지수 시간 알고리즘을 이해하는 것이 중요합니다.
• 다항 시간 알고리즘은 변수 N과 그 거듭제곱들의 선형 결합으로 이루어진 식을 사용하여 수행 시간을 표현합니다.
• 예를 들어, $N^2$나 $N^6$ 같은 식으로 표현됩니다. 이는 대부분의 알고리즘이 다항 시간에 속한다는 것을 의미합니다.

 

• 반면, 지수 시간 알고리즘은 입력의 크기가 증가함에 따라 수행 시간이 급격히 증가합니다.
• 예를 들어, 집들이 음식 메뉴 결정 문제에서는 M가지 음식 중 어떤 것을 준비해야 모든 친구들이 먹을 수 있는지 판단해야 합니다.
• 이 경우 가능한 모든 조합을 고려해야 하므로, 선택지는 $2^M$가지가 되며, 이러한 문제가 지수 시간 알고리즘의 예시입니다. 관련 코드는 다음과 같습니다.

# 음식 메뉴 정하기

INF = float('inf')
# 해당 메뉴로 모두가 식사할 수 있는지 여부를 반환해줍니다.
def can_everybody_eat(menu: list) -> bool:
    pass
# 음식의 개수는 임의로 설정해주시면 됩니다.
M = 10
# food번째 음식을 만들지 여부를 결정합니다.
def select_menu(menu: list, food: int) -> int:
    # 기저 사례: 모든 음식에 대해 만들지 여부를 결정했을 때
    if food == M:
        if can_everybody_eat(menu):
            return len(menu)
        # 아무것도 못 먹는 사람이 있으면 INF를 반환합니다.
        return INF
    # 이 음식을 만들지 않는 경우의 답을 계산합니다.
    result = select_menu(menu, food + 1)
    # 이 음식을 만드는 경우의 답을 계산해서 더 작은 것을 취합니다.
    menu.append(food)
    result = min(result, select_menu(menu, food + 1))
    menu.pop()
    return result

 

• 이와 유사하게 소인수 분해 알고리즘은 주어진 숫자 N을 소인수로 분해하는 과정에서 최악의 경우 N-1번의 반복을 필요로 하며, 이 또한 지수 시간 알고리즘에 해당합니다.

# 가장 간단한 형태의 소인수 분해 알고리즘

# 자연수 n의 소인수 분해 결과를 담은 정수 배열을 반환합니다.
def factor(n: int) -> list:
    if n == 1:
        # n = 1인 경우는 예외로 합니다.
        return [1, 1]
    result = []
    div = 2
    while n > 1:
        while n % div == 0:
            n //= div
            result.append(div)
        div += 1
    return result

• 이러한 다항 시간과 지수 시간 알고리즘의 차이는 계산적으로 쉬운 문제와 어려운 문제를 구분하는 데 중요한 기준이 됩니다. 보통 다항 시간 알고리즘은 계산적으로 쉬운 문제에 적용되는 반면, 지수 시간 알고리즘은 더 어려운 문제에 사용됩니다.
• 빅 오 표기법이나 주먹구구 법칙 등에 관한 내용은 다음 포스팅에 이어서 작성하겠습니다!