공간 복잡도와 위대한 거래

"시간만 청구서가 아니야. 모든 알고리즘은 메모리도 빌려 — 그리고 시간상 제일 싼 해법이 공간상 제일 비싼 경우가 많아. 넌 늘 하나를 다른 하나랑 맞바꾸고 있어."

같은 아이디어, 다른 자원

공간 복잡도는 시간 복잡도랑 정확히 같은 질문을 해, 단계 대신 메모리에 대해서: 입력이 커지면, 알고리즘이 추가로 얼마나 메모리가 필요해? 같은 사다리, 같은 표기:

O(1) 공간 — 입력과 상관없이 고정량 추가 메모리. 두 포인터로 제자리에서 리스트 뒤집기: 변수 몇 개뿐.
O(n) 공간 — 추가 메모리가 입력에 따라 커짐. 본 항목 전부의 set 짓기, 또는 리스트 복사.
O(n²) 공간 — 꽉 찬 2D 테이블, Dynamic Programming 에서 지을 격자 같은 거.

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

거래가 핵심 전부야

모든 알고리즘을 관통하는 관계: 아주 자주 공간으로 시간을 사고, 시간으로 공간을 살 수 있어. 앞의 중복 확인 기억해?

중첩 반복문: O(n²) 시간, 근데 O(1) 공간 — 추가 메모리 없음.
본 항목 set: O(n) 시간, 근데 O(n) 공간 — 다시 하는 일을 건너뛰려고 메모리를 썼어.

어느 쪽도 "정답" 이 아니야. 메모리가 넉넉하면 (네 노트북, 대부분 서버), 시간 아끼려고 써. 메모리가 단단한 한계면 (50 GB 파일, 임베디드 칩, 스트리밍 파이프라인), 더 느린 제자리 버전을 받아들이고 좋아해. 메모이제이션 — Dynamic Programming 의 심장 — 은 이 거래를 기법으로 만든 거야: 지난 답을 저장해서 (공간 더) 절대 다시 계산 안 해 (시간 덜).

모든 알고리즘은 시간 비용과 공간 비용이 있고, 보통 서로 반대로 당겨. 공짜 승리는 드물어 — 거래가 있고, 엔지니어링은 *이* 문제에 대해 어느 쪽에서 값을 치를지 고르는 거야.

숨은 공간: 콜 스택

입문자가 통째로 잊는 공간 비용 하나: 재귀는 메모리를 써. 대기 중인 모든 재귀 호출이 콜 스택에 앉아, 반환할 때까지 지역 변수를 들고 있어. n 단계 깊이로 가는 재귀는 다른 걸 아무것도 할당 안 해도 O(n) 공간을 써 — 그리고 너무 깊이 가면 스택이 넘쳐 Python 이 RecursionError 를 던져. Recursion 트랙에서 파볼 거야; 지금은 "배열 할당 안 함" 이 늘 "O(1) 공간" 을 뜻하진 않는다는 것만 알아.

피파의 고백

난 순전히 속도만 최적화하고 메모리는 무한한 것처럼 다뤘어 — 아빠의 512 GB 맥에선 거의 그렇거든. 그러다 더 작은 기계에서 같은 코드를 돌렸더니 RAM 을 다 먹어서 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