공간 복잡도 — 메모리를 얼마나 쓰는가

이 토픽을 마치면

공간 복잡도가 무엇인지, 시간 복잡도와 어떤 관계인지, 그리고 실무에서 언제 메모리를 신경 써야 하는지 이해하게 됩니다.

시간만 빠르면 되는 줄 알았는데

알고리즘을 평가할 때 "얼마나 빠른가"만 생각하기 쉽습니다. Big-O 표기법으로 O(n), O(n log n), O(n^2)를 비교하면서 시간 복잡도를 따집니다.

하지만 컴퓨터에는 CPU만 있는 게 아닙니다. **메모리(RAM)**도 있습니다. 아무리 빠른 알고리즘이라도 메모리를 100GB 쓰면 보통 컴퓨터에서는 실행이 안 됩니다.

공간 복잡도는 알고리즘이 입력 크기에 따라 메모리를 얼마나 사용하는지 분석하는 것입니다. 시간 복잡도와 같은 Big-O 표기법을 씁니다.

O(1) — 입력과 무관한 고정 메모리

python

def find_max(arr):
    result = arr[0]
    for x in arr:
        if x > result:
            result = x
    return result

배열이 100개든 100만 개든 추가로 사용하는 변수는 result 하나입니다. 공간 복잡도 **O(1)**입니다. "상수 공간"이라고 합니다.

O(n) — 입력에 비례하는 메모리

python

def get_squares(arr):
    result = []
    for x in arr:
        result.append(x * x)
    return result

입력 배열과 같은 크기의 새 배열을 만듭니다. 입력이 n개면 메모리도 n개분 추가로 씁니다. 공간 복잡도 **O(n)**입니다.

python

def reverse_string(s):
    return s[::-1]

이것도 O(n)입니다. 원본과 같은 길이의 새 문자열을 만들기 때문입니다.

O(n^2) — 2차원 구조

python

def create_matrix(n):
    return [[0] * n for _ in range(n)]

n×n 행렬을 만들면 공간 복잡도는 **O(n^2)**입니다. 인접행렬이 대표적인 예입니다.

재귀의 숨겨진 공간

재귀 함수는 호출될 때마다 콜 스택에 프레임을 쌓습니다. 이것도 메모리입니다.

python

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(1000)을 호출하면 콜 스택에 프레임이 1000개 쌓입니다. 공간 복잡도 **O(n)**입니다. Python에서는 기본 재귀 깊이가 1000으로 제한되어 있어서, 이를 초과하면 RecursionError가 발생합니다.

반복문으로 바꾸면 O(1)로 줄일 수 있습니다:

python

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

같은 결과지만 스택을 쓰지 않습니다. 이처럼 재귀를 반복문으로 바꾸면 공간을 절약할 수 있습니다.

시간과 공간의 트레이드오프

"시간을 아끼면 공간을 더 쓰고, 공간을 아끼면 시간이 더 걸린다." 이걸 **시공간 트레이드오프(Time-Space Tradeoff)**라고 합니다.

대표적인 예가 캐싱입니다:

python

# 공간 O(1), 시간 O(n) — 매번 계산
def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 공간 O(n), 시간 O(1) 조회 — 미리 계산해서 저장
cache = {}
def fib_cached(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        result = n
    else:
        result = fib_cached(n - 1) + fib_cached(n - 2)
    cache[n] = result
    return result

메모리를 더 쓰는 대신 같은 값을 두 번 계산하지 않습니다. 동적 프로그래밍(DP)의 핵심이 바로 이 트레이드오프입니다.

해시 테이블도 마찬가지입니다. 배열을 정렬해서 이진 탐색하면 추가 공간 O(1)이지만, 해시 테이블을 만들면 추가 공간 O(n)을 쓰는 대신 조회가 O(1)로 빨라집니다.

실무에서 공간이 문제 되는 순간

일반적인 웹 개발에서는 공간 복잡도를 신경 쓸 일이 적습니다. RAM이 충분하기 때문입니다. 하지만 다음 상황에서는 메모리가 병목이 됩니다:

대용량 데이터 처리 — 10GB 로그 파일을 분석할 때, 전부 메모리에 올리면 터집니다. 한 줄씩 읽으면서 처리해야 합니다 (스트리밍).

모바일/임베디드 — 스마트폰이나 IoT 기기는 RAM이 제한적입니다. 알고리즘이 메모리를 적게 쓰도록 설계해야 합니다.

코딩 테스트 — 문제에 "메모리 제한: 256MB" 같은 조건이 있습니다. O(n^2) 공간을 쓰는 풀이가 메모리 초과로 실패할 수 있습니다.

핵심

공간 복잡도는 알고리즘이 입력 크기에 따라 메모리를 얼마나 사용하는지 분석하는 것입니다. 재귀의 콜 스택도 공간입니다. 재귀를 반복문으로 바꾸면 O(n) → O(1)로 줄일 수 있습니다. 시간과 공간은 트레이드오프 관계이며, 상황에 따라 어느 쪽을 우선할지 판단해야 합니다.