공간 복잡도: 메모리의 수학

O(1) — 상수: 입력 크기 무관 (변수 몇 개)
O(n) — 선형: 입력 크기 비례 (배열 복사)
O(log n) — 로그: 재귀 호출 깊이 (이진 탐색)
O(n²) — 제곱: 2D 배열 (인접 행렬)

# 배열을 뒤집기 — 추가 배열 X
def reverse_in_place(arr):
    """공간 O(1) — 입력만 사용"""
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1
    return arr


arr = [1, 2, 3, 4, 5]
reverse_in_place(arr)
print(arr)  # [5, 4, 3, 2, 1]


# vs O(n) 공간 버전
def reverse_copy(arr):
    """공간 O(n) — 새 배열"""
    return arr[::-1]

# 중복 검사 — 해시셋
def has_duplicates(arr):
    """시간 O(n), 공간 O(n)"""
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False


# vs O(1) 공간 — 정렬 후 검사 (단, 시간 O(n log n))
def has_duplicates_sorted(arr):
    """시간 O(n log n), 공간 O(1)*"""
    arr.sort()  # 인플레이스 정렬 — 단, 입력 변경
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            return True
    return False
# *원본 보존하려면 arr.copy() = O(n) 공간

# 시간 O(n)이지만 공간 O(n) — 콜 스택
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)


# vs 시간 O(n), 공간 O(1) — 반복문
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


# 깊은 재귀는 메모리 폭주
import sys
print(sys.getsizeof(int))  # 28 bytes
# 재귀 깊이 1000 = 약 28KB 콜 스택
# 재귀 깊이 10만 = 2.8MB
# 재귀 깊이 1000만 = 280MB → OOM

# 메모이제이션 — 시간 줄이려고 공간 늘림

# Naive 피보나치: 시간 O(2^n), 공간 O(n) (스택)
def fib_naive(n):
    if n <= 2:
        return 1
    return fib_naive(n - 1) + fib_naive(n - 2)


# 메모: 시간 O(n), 공간 O(n) (캐시)
def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 2:
        return 1
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return cache[n]


# 반복: 시간 O(n), 공간 O(1)
def fib_iter(n):
    a, b = 1, 1
    for _ in range(n - 2):
        a, b = b, a + b
    return b


# 비교
import time

t0 = time.perf_counter()
fib_naive(35)
print(f"Naive: {(time.perf_counter() - t0)*1000:.0f}ms")  # ~3000ms

t0 = time.perf_counter()
fib_memo(35)
print(f"Memo: {(time.perf_counter() - t0)*1000:.3f}ms")  # ~0.05ms

t0 = time.perf_counter()
fib_iter(35)
print(f"Iter: {(time.perf_counter() - t0)*1000:.3f}ms")  # ~0.01ms

# 1억 개 정수의 합 — 메모리 효율

# ❌ 모든 데이터 메모리에 로드 — 공간 O(n)
def sum_loaded(filename):
    with open(filename) as f:
        nums = [int(line) for line in f]  # 1억개 = 4GB+
    return sum(nums)


# ✅ 스트리밍 — 공간 O(1)
def sum_streaming(filename):
    total = 0
    with open(filename) as f:
        for line in f:
            total += int(line)  # 한 줄씩만
    return total


# 더 좋게 — generator
def sum_generator(filename):
    with open(filename) as f:
        return sum(int(line) for line in f)

# Python sorted vs sort — 공간 차이
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]

sorted_arr = sorted(arr)  # O(n) 공간 — 새 배열
print(arr)         # 원본 보존
print(sorted_arr)  # 정렬된 새 배열

arr.sort()  # O(1) 공간 (Timsort는 O(log n) 스택) — 원본 변경
print(arr)


# 두 합 문제 — 시간/공간 트레이드오프
def two_sum_v1(arr, target):
    """시간 O(n²), 공간 O(1)"""
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return (i, j)
    return None


def two_sum_v2(arr, target):
    """시간 O(n), 공간 O(n)"""
    seen = {}
    for i, x in enumerate(arr):
        if target - x in seen:
            return (seen[target - x], i)
        seen[x] = i
    return None