공간 복잡도

공간 복잡도(Space Complexity)는 알고리즘이 문제를 해결하는 과정에서 얼마나 많은 메모리 공간을 사용하는가를 분석하는 개념이다. 시간 복잡도가 “얼마나 오래 걸리는가”를 의미한다면, 공간 복잡도는 “얼마나 많은 공간을 차지하는가”를 뜻한다. 쉽게 말해, 입력값이 커질수록 프로그램이 차지하는 메모리 양이 얼마나 늘어나는지를 보는 것이다. 입력값이 두 배가 되면 필요한 공간이 두 배로 늘어나는지, 혹은 네 배로 늘어나는지를 관찰함으로써 알고리즘의 효율성을 평가할 수 있다.

우리는 보통 공간을 적게 사용하는 알고리즘을 효율적이라고 생각하지만, 모든 경우에 그렇지는 않다. 실제로는 시간과 공간은 서로 트레이드오프 관계를 가진다. 속도를 높이기 위해 데이터를 더 많이 저장해야 하는 경우도 있고, 반대로 메모리를 절약하기 위해 계산을 여러 번 반복해야 하는 경우도 있다. 따라서 공간 복잡도는 독립적인 지표라기보다는, 시간 복잡도와 함께 고려해야 하는 균형의 문제라고 볼 수 있다.

예를 들어 문자열에서 가장 많이 등장한 알파벳(최빈값)을 찾는 문제를 생각해보자.

첫 번째 방법은 알파벳 배열을 미리 만들어두고, 각 알파벳마다 문자열 전체를 돌면서 몇 번 등장했는지를 세는 방식이다.

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", 
                      "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

이 함수는 alphabet_array라는 배열을 선언해 26개의 공간을 사용하고, max_occurrence, max_alphabet, occurrence 같은 변수를 추가로 사용한다. 총 29개의 공간이 필요하지만, 문자열의 길이가 아무리 커져도 이 크기는 변하지 않는다. 즉, 입력 크기 N과 관계없이 일정한 공간을 사용하는 상수 공간, 다시 말해 O(1)의 공간 복잡도를 가진다.

이제 두 번째 방법을 보자. 이번에는 알파벳 빈도수를 저장하는 배열을 활용한다.

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))

이 함수는 [0] * 26으로 26개의 공간을 확보하고, arr_index, max_occurrence, max_alphabet_index 등의 변수를 사용한다. 전체적으로 약 30개의 공간이 필요하며, 역시 입력 길이 N과는 무관한 상수 크기이므로 O(1)의 공간 복잡도를 가진다.

이쯤 되면 “29개를 쓰는 첫 번째 방법이 더 효율적이지 않을까?”라는 생각이 들 수도 있다. 그러나 공간 복잡도에서 중요한 것은 절대적인 숫자가 아니라 입력 크기 증가에 따른 변화율이다. 29와 30은 모두 상수이기 때문에 의미 있는 차이가 없다.

따라서 이 두 알고리즘은 공간 복잡도 면에서는 사실상 동일하다고 볼 수 있다. 대신 효율성을 판단할 때는 시간 복잡도를 함께 고려해야 한다. 첫 번째 방법은 모든 알파벳에 대해 문자열 전체를 반복 탐색하므로 약 26×N번의 연산이 필요하고, 두 번째 방법은 문자열을 한 번만 순회하므로 N번의 연산으로 충분하다. 즉, 두 번째 방법이 훨씬 빠르다.

이 예시에서 알 수 있듯이, 대부분의 알고리즘은 공간보다 시간에 의해 효율성이 결정된다. 물론 예외도 있다. 만약 어떤 알고리즘이 입력 크기에 따라 N², N³ 수준의 공간을 사용한다면 메모리 사용량이 급격히 증가해 프로그램이 느려지거나 실행조차 불가능할 수 있다. 이런 경우에는 공간 복잡도가 중요한 판단 기준이 된다.

정리하자면, 공간 복잡도는 입력값의 크기와 메모리 사용량의 관계를 나타내며, 상수 크기의 차이는 중요하지 않다. 대신 입력이 커질 때 메모리 사용량이 얼마나 증가하는지를 보는 것이 핵심이다. 효율적인 알고리즘은 필요한 만큼만 공간을 사용하면서도 빠르게 동작하는 코드이다. 결국 공간 복잡도는 프로그램이 얼마나 가볍고 단순하게 작동하는지를 보여주는 또 하나의 지표라고 할 수 있다.