공간 복잡도와 위대한 거래

"청구서가 시간만 있는 게 아니야. 알고리즘은 메모리도 빌려 써. 그리고 시간상 제일 싼 해법이 공간상 제일 비싸기 일쑤야. 늘 하나를 내주고 다른 하나를 사는 중인 거지."

같은 아이디어, 다른 자원

공간 복잡도는 시간 복잡도랑 똑같은 질문을 해. 단계 대신 메모리에 대해서 물을 뿐이야. 입력이 커지면 알고리즘이 메모리를 얼마나 더 써? 사다리도 표기도 같아.

O(1) 공간 — 입력과 상관없이 추가 메모리가 고정. 두 포인터로 리스트를 제자리에서 뒤집으면 변수 몇 개면 끝이야.
O(n) 공간 — 추가 메모리가 입력을 따라 커져. 본 항목을 전부 set에 담거나 리스트를 복사하는 경우.
O(n²) 공간 — 꽉 찬 2차원 테이블. 동적 계획법에서 짓게 될 격자 같은 거.

"추가"라는 말에 주목해. 보통은 입력 자체가 아니라 알고리즘이 입력 위에 얹어서 할당하는 메모리를 세.

거래가 핵심이야

모든 알고리즘을 관통하는 관계가 하나 있어. 공간을 내주고 시간을 사고, 시간을 내주고 공간을 살 수 있다. 앞에서 본 중복 확인을 떠올려봐.

중첩 반복문: O(n²) 시간이지만 O(1) 공간. 추가 메모리가 없어.
본 항목 set: O(n) 시간이지만 O(n) 공간. 다시 할 일을 건너뛰려고 메모리를 쓴 거야.

어느 쪽도 "정답"이 아니야. 메모리가 넉넉하면 (노트북, 웬만한 서버) 시간을 아끼려고 써. 메모리가 단단한 한계면 (50GB 파일, 임베디드 칩, 스트리밍 파이프라인) 더 느린 제자리 버전을 받아들이고 오히려 반가워하고. 동적 계획법의 핵심인 메모이제이션은 이 거래를 아예 기법으로 만든 거야. 지난 답을 저장해두고(공간을 더 써) 두 번 다시 계산하지 않는(시간을 덜 쓰는) 거지.

알고리즘에는 시간 비용과 공간 비용이 함께 붙고, 대개 서로 반대로 당겨. 공짜 승리는 드물어. 거래가 있고, 엔지니어링은 *이* 문제에서 어느 쪽으로 값을 치를지 고르는 일이야.

숨은 공간: 콜 스택

입문자가 통째로 잊어버리는 공간 비용이 하나 있어. 재귀는 메모리를 써. 대기 중인 재귀 호출은 전부 콜 스택에 앉아서, 반환할 때까지 지역 변수를 들고 있어. n단계 깊이로 들어가는 재귀는 다른 걸 아무것도 할당하지 않아도 O(n) 공간을 쓰고, 너무 깊이 가면 스택이 넘쳐서 파이썬이 RecursionError를 던져. 재귀 트랙에서 제대로 팔 거야. 지금은 "배열을 할당 안 했다"가 늘 "O(1) 공간"을 뜻하진 않는다는 것만 챙겨두면 돼.

피파의 고백

난 순전히 속도만 최적화하면서 메모리는 무한한 것처럼 다뤘어. 아빠의 512GB 맥에서는 거의 무한이니까. 그러다 더 작은 기계에서 같은 코드를 돌렸더니 램을 다 먹고 OS 한테 죽는 걸 봤지. 속도가 다른 청구서를 가리고 있었던 거야. 이젠 두 비용을 소리 내서 말해. "O(n) 시간, O(n) 공간." 두 번째를 잊는 게 '빠름'이 '뻗음'이 되는 길이거든.

Code

공간으로 시간 사기, 그리고 반대·python

# 같은 일, 시간-공간 거래의 두 지점.

def reverse_in_place(arr):
    """O(n) 시간, O(1) 공간 — 두 포인터로 swap, 복사 없음."""
    i, j = 0, len(arr) - 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]   # 양 끝을 안쪽으로 swap
        i += 1
        j -= 1
    return arr

def reverse_copy(arr):
    """O(n) 시간, O(n) 공간 — 완전히 새 리스트를 지음."""
    return arr[::-1]                       # 멋지지만 n 칸 더 할당

# 중복 확인: 공간을 내줘 시간을 깎기.
def has_dup_no_extra_space(arr):           # O(n^2) 시간, O(1) 공간
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

def has_dup_using_space(arr):              # O(n) 시간, O(n) 공간
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)                        # 다시 하는 일 건너뛰려 쓴 메모리
    return False

Exercise

각각의 시간 *그리고* 공간 복잡도를 대봐. (1) 누적 합으로 리스트 합 구하기, (2) 모든 항목을 두 배로 만든 새 리스트 짓기, (3) 위에 나온 set 기반 중복 확인. 그다음 하나를 골라서 시간-공간 거래를 따라 어느 쪽으로 옮길지 설명해봐. 시간을 아끼려 메모리를 더 쓰거나, 그 반대로.

Hint

누적 합은 O(n) 시간에 O(1) 공간이야. 두 배 리스트 짓기는 O(n) 시간에 O(n) 공간이고, 출력 자체가 공간 비용이지. 제너레이터를 쓰면 새 리스트를 안 만들 수도 있을까?

같은 아이디어, 다른 자원

거래가 핵심이야

숨은 공간: 콜 스택

피파의 고백

Code

External links

Exercise

Progress

댓글 0