# [07-02] 공간 복잡도 (Space Complexity)
공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 나타내는 척도입니다.
🎯 공간 복잡도란 무엇인가
공간 복잡도의 기본 개념
시간 복잡도가 "얼마나 빠른가"를 측정한다면, 공간 복잡도(Space Complexity)는 "얼마나 많은 메모리를 사용하는가"를 측정합니다.
실생활 비유:
여행 짐 싸기:
빠른 방법 (시간 중시):
- 옷을 모두 펼쳐서 보관
- 빨리 찾지만 공간 많이 차지
효율적인 방법 (공간 중시):
- 옷을 돌돌 말아서 보관
- 찾는데 시간 걸리지만 공간 절약
→ 시간 vs 공간 트레이드오프!또 다른 예시:
책상 위 작업:
큰 책상 (메모리 많음):
- 모든 자료를 펼쳐 놓고 작업
- 빠르지만 공간 많이 필요
작은 책상 (메모리 적음):
- 필요한 것만 꺼내서 작업
- 느리지만 공간 절약왜 공간 복잡도가 중요한가?
1. 메모리 제한
임베디드 시스템:
- 스마트워치: 512MB RAM
- IoT 센서: 64KB RAM
→ 메모리 효율이 생명!
모바일 앱:
- 메모리 많이 쓰면 강제 종료
- 배터리 소모 증가
서버:
- 동시 접속자 1만 명
- 각자 메모리 사용
→ 공간 복잡도가 비용!2. 실행 가능여부 판단
문제: 10억 개 데이터 처리
O(1) 공간: 가능!
O(n) 공간: 4GB 필요 (가능)
O(n²) 공간: 4,000,000GB 필요 (불가능!)
→ 시간은 되지만 공간이 안 되는 경우!3. 성능 영향
캐시 미스:
- 메모리 많이 쓰면 캐시 효율 떨어짐
- 실제 속도 저하
스와핑:
- 메모리 부족 시 디스크 사용
- 속도 100배 이상 느려짐공간 복잡도의 구성 요소
알고리즘이 사용하는 총 메모리는 다음과 같이 나뉩니다:
총 공간 = 고정 공간 + 가변 공간
1. 고정 공간 (Fixed Space):
- 입력 크기와 무관한 공간
- 코드, 상수, 변수 등
2. 가변 공간 (Variable Space):
- 입력 크기에 따라 변하는 공간
- 동적 할당, 재귀 스택 등
공간 복잡도 = 주로 가변 공간만 측정📊 공간 복잡도 분석
O(1) - 상수 공간
정의: 입력 크기와 무관하게 일정한 메모리 사용
def sum_array(arr):
"""
O(1) 공간
사용 메모리:
- total: 하나의 정수 (4바이트)
- i: 인덱스 (4바이트)
입력 크기와 무관!
"""
total = 0 # 상수 공간
for i in range(len(arr)):
total += arr[i]
return total
# arr 크기가 100이든 1,000,000이든
# 추가 메모리 사용량은 같음! = 입력이 커져도 메모리를 더 쓰지 않는다!특징:
장점:
- 메모리 효율 최고
- 대용량 데이터 처리 가능
예시:
- 반복문으로 최댓값 찾기
- 제자리 정렬 (버블, 삽입)
- 이진 탐색 (반복 버전)O(log n) - 로그 공간
정의: 입력이 절반씩 줄어들 때 필요한 공간
def binary_search_recursive(arr, target, left, right):
"""
O(log n) 공간 - 재귀 호출 스택
재귀 깊이: log n
각 호출마다 스택 프레임 생성
총 공간: O(log n)
"""
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
# 재귀 호출 → 스택 사용
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
# 호출 스택:
# binary_search(0, 1000)
# → binary_search(500, 1000)
# → binary_search(750, 1000)
# → ...
# 최대 log₂(1000) ≈ 10번 중첩특징:
발생 상황:
- 재귀적 이진 탐색
- 분할 정복 (병합 정렬의 재귀)
- 균형 이진 트리 탐색
주의:
- 반복문으로 바꾸면 O(1) 가능!O(n) - 선형 공간
정의: 입력 크기에 비례하는 메모리 사용
def copy_array(arr):
"""
O(n) 공간
새 배열 생성: n개 원소
"""
new_arr = []
for item in arr:
new_arr.append(item)
return new_arr
def fibonacci_memo(n):
"""
O(n) 공간 - 메모이제이션
memo 배열: n+1개 원소 저장
"""
memo = [0] * (n + 1)
memo[1] = 1
for i in range(2, n + 1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
def merge_sort(arr):
"""
O(n) 공간 - 병합 과정에서 임시 배열
분할: 공간 사용 없음
병합: 임시 배열 필요
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 병합 시 새 배열 생성 (O(n))
return merge(left, right)특징:
발생 상황:
- 배열 복사
- 동적 계획법 (DP 테이블)
- 해시 테이블
- 그래프 인접 리스트
일반적:
- 가장 흔한 공간 복잡도
- 대부분 허용 가능O(n²) - 제곱 공간
정의: 입력 크기의 제곱에 비례
def adjacency_matrix(n):
"""
O(n²) 공간 - 인접 행렬
n×n 2차원 배열
"""
matrix = [[0] * n for _ in range(n)]
return matrix
def floyd_warshall(graph): # floyd_warshall 은 그래프에서 '모든 정점 쌍 사이의 최단 경로'를 구하는 알고리즘
"""
O(n²) 공간 - 모든 쌍 최단 경로
dist[i][j]: i에서 j로의 최단 거리
n×n 배열
"""
n = len(graph)
dist = [[float('inf')] * n for _ in range(n)]
# 초기화 및 계산...
return dist
def all_pairs_distance(points): # all_pairs_distance 는 주어진 점(points)들 사이의 모든 거리 조합을 계산하는 함수
"""
O(n²) 공간 - 모든 점 쌍의 거리
n개 점 → n(n-1)/2 쌍
"""
n = len(points)
distances = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
distances[i][j] = distance(points[i], points[j])
return distances특징:
발생 상황:
- 2차원 DP 테이블
- 그래프 인접 행렬
- 모든 쌍 문제
문제:
- 메모리 많이 사용
- n=10,000이면 400MB
- n=100,000이면 40GB (불가능!)⚖️ 시간-공간 트레이드오프
트레이드오프란?
시간을 줄이려면 공간이 필요하고, 공간을 줄이려면 시간이 필요합니다.
예시 1: 피보나치 수열
# 방법 1: 순수 재귀 (공간 절약, 시간 낭비)
def fib_recursive(n):
"""
시간: O(2^n) - 매우 느림!
공간: O(n) - 재귀 스택만
"""
if n <= 1:
return n
return fib_recursive(n-1) + fib_recursive(n-2)
# 방법 2: 메모이제이션 (시간 절약, 공간 사용)
def fib_memo(n, memo={}):
"""
시간: O(n) - 빠름!
공간: O(n) - memo 딕셔너리
"""
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
# 방법 3: 반복 (시간 절약, 공간 최소)
def fib_iterative(n):
"""
시간: O(n) - 빠름!
공간: O(1) - 변수 2개만
최적!
"""
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
# 비교:
# n=40일 때
# 재귀: 수십 초, 40번 재귀
# 메모: 0.001초, 40개 저장
# 반복: 0.001초, 2개 변수만예시 2: 최단 경로
# 방법 1: 모든 경로 저장 (공간 많이)
def all_paths_bfs(graph, start):
"""
시간: O(V + E)
공간: O(V²) - 모든 경로 저장
"""
paths = {node: [] for node in graph}
# 모든 경로 기록...
# 방법 2: 거리만 저장 (공간 절약)
def shortest_distance_bfs(graph, start):
"""
시간: O(V + E)
공간: O(V) - 거리만 저장
경로는 필요 시 재구성
"""
distance = {node: float('inf') for node in graph}
# 거리만 기록...트레이드오프 선택 전략
상황별 선택:
메모리가 제한적:
→ 시간 희생, 공간 절약
→ 재계산, 스트리밍 처리
시간이 중요:
→ 메모리 사용, 시간 절약
→ 캐싱, 메모이제이션
균형 잡힌 접근:
→ 최적의 알고리즘 선택
→ 피보나치 반복 버전🔄 재귀의 공간 복잡도
재귀 호출 스택
재귀 함수는 호출 스택에 메모리를 사용합니다.
def factorial_recursive(n):
"""
공간 복잡도: O(n)
호출 스택:
factorial(5)
→ factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1)
최대 n개 호출이 스택에 쌓임
"""
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
def factorial_iterative(n):
"""
공간 복잡도: O(1)
반복문 사용 → 스택 사용 없음
"""
result = 1
for i in range(2, n + 1):
result *= i
return result
# 공간 비교:
# n=10000일 때
# 재귀: 10000번 스택 프레임 (스택 오버플로우(Stack Overflow)!)
# 반복: 변수 2개만재귀 깊이 문제
import sys
# Python 기본 재귀 호출의 횟수(깊이) 제한(Recursion Limit): 약 1000
print(sys.getrecursionlimit()) # 1000
# 깊은 재귀 시도
def deep_recursion(n):
if n == 0:
return 0
return deep_recursion(n - 1)
try:
deep_recursion(2000) # RecursionError!
except RecursionError:
print("스택 오버플로우!")
# 해결 방법 1: 재귀 깊이 증가 (비추천)
sys.setrecursionlimit(10000)
# 해결 방법 2: 반복문 사용 (추천)
def iterative_solution(n):
result = 0
for i in range(n):
result += i
return result꼬리 재귀 최적화 (Tail Call Optimization, TCO)
# 일반 재귀 (O(n) 공간)
def sum_recursive(n):
"""
호출 스택에 n개 쌓임
"""
if n == 0:
return 0
return n + sum_recursive(n - 1)
# 꼬리 재귀 (O(n) 공간, 이론상 O(1) 가능)
def sum_tail_recursive(n, acc=0):
"""
마지막에 재귀 호출만 * 메모지를 계속 새로 쓰는 게 아니라, 기존 메모지의 내용을 지우고 새로 쓰는 것과 같음
Python은 꼬리 재귀 최적화 X
→ 여전히 O(n) 공간
하지만 다른 언어(Scala, Scheme)에서는
O(1) 공간으로 최적화됨
"""
if n == 0:
return acc
return sum_tail_recursive(n - 1, acc + n)
# Python에서는 그냥 반복문 쓰기!
def sum_iterative(n):
"""
O(1) 공간
"""
acc = 0
for i in range(1, n + 1):
acc += i
return acc🎛️ 제자리 알고리즘
제자리 알고리즘이란?
In-Place Algorithm: 입력 외에 추가 공간을 거의 사용하지 않는 알고리즘
# 제자리 정렬 (O(1) 공간)
def bubble_sort_inplace(arr):
"""
추가 배열 없이 원본 수정
공간: O(1)
"""
n = len(arr)
for i in range(n - 1):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
# 제자리 교환
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 제자리가 아닌 정렬 (O(n) 공간)
def merge_sort(arr):
"""
병합 시 새 배열 생성
공간: O(n)
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 새 배열 생성!
return merge(left, right)제자리 알고리즘 예시
# 1. 배열 뒤집기
def reverse_inplace(arr):
"""
O(1) 공간 - 양 끝에서 교환
"""
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# 2. 중복 제거 (정렬된 배열)
def remove_duplicates_inplace(arr):
"""
O(1) 공간 - 투 포인터
"""
if not arr:
return 0
write = 1
for read in range(1, len(arr)):
if arr[read] != arr[read - 1]:
arr[write] = arr[read]
write += 1
return write # 새 길이
# 3. 0을 뒤로 이동
def move_zeros_inplace(arr):
"""
O(1) 공간
"""
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# 나머지를 0으로
while write < len(arr):
arr[write] = 0
write += 1💡 실무 팁
공간 복잡도 줄이기
# 나쁜 예: 불필요한 복사
def process_data_bad(data):
# 매번 복사 (O(n) 공간)
copied = data.copy()
result = []
for item in copied:
result.append(item * 2)
return result
# 좋은 예: 제자리 처리
def process_data_good(data):
# 제자리 수정 (O(1) 공간)
for i in range(len(data)):
data[i] *= 2
return data
# 또는 제너레이터 사용 (O(1) 공간)
def process_data_generator(data):
for item in data:
yield item * 2 # yield : 값을 반환하고 그 자리에 일시정지함
# 주로 대용량 텍스트 파일을 한 줄씩 읽거나, 끝이 없는 무한한 데이터를 다룰 때 필수적으로 사용메모리 프로파일링(Memory Profiling): 프로그램이 실행되는 동안 메모리를 어디서, 얼마나, 왜 사용하는지 정밀하게 분석하는 과정
import tracemalloc
# 메모리 사용량 측정
tracemalloc.start()
# 알고리즘 실행
data = [i for i in range(1000000)]
current, peak = tracemalloc.get_traced_memory()
print(f"현재: {current / 10**6:.2f}MB")
print(f"최대: {peak / 10**6:.2f}MB")
tracemalloc.stop()큰 파일 처리
# 나쁜 예: 전체 파일 메모리에 로드
def process_file_bad(filename):
# O(파일 크기) 공간
with open(filename) as f:
data = f.read() # 전체 로드!
# 처리...
# 좋은 예: 스트리밍 처리
def process_file_good(filename):
# O(1) 공간
with open(filename) as f:
for line in f: # 한 줄씩
# 처리...
pass🎯 핵심 정리
공간 복잡도의 본질
- 알고리즘이 사용하는 메모리 양
- 입력 크기에 따른 메모리 증가율
- 시간 복잡도와 함께 고려
주요 공간 복잡도
복잡도 예시
--------------------------------------------------
O(1) 변수 몇 개, 제자리 정렬
O(log n) 재귀 이진 탐색, 재귀 병합 정렬
O(n) 배열 복사, DP 테이블, 해시 테이블
O(n²) 2차원 배열, 인접 행렬시간-공간 트레이드오프
피보나치:
- 순수 재귀: 시간 O(2^n), 공간 O(n)
- 메모이제이션: 시간 O(n), 공간 O(n)
- 반복: 시간 O(n), 공간 O(1) ← 최적!재귀와 공간
재귀 호출:
- 호출 스택에 메모리 사용
- 깊이 n이면 O(n) 공간
- Python 최대 깊이: 약 1000
해결:
- 반복문으로 변환
- 꼬리 재귀 (Python 지원 X)제자리 알고리즘
In-Place:
- 입력 외 추가 공간 최소
- O(1) 공간
- 버블/삽입 정렬, 배열 뒤집기실무 선택 기준
메모리 제한적 (임베디드, IoT):
→ 공간 복잡도 우선
성능 중요 (서버, 앱):
→ 시간 복잡도 우선, 캐싱 활용
균형:
→ 최적 알고리즘 선택🔗 다음 글에서는
[07-03] 점근적 표기법 (Asymptotic Notation)
- Big-O의 수학적 정의: 상한을 나타내는 엄밀한 수학적 의미
- Big-Ω (오메가): 알고리즘의 하한, 최선의 경우
- Big-Θ (세타): 상한과 하한이 같을 때의 정확한 복잡도
- 증명 방법: 점근적 표기법의 수학적 증명 기법
이전 글: [07-01] 시간 복잡도
다음 글: [07-03] 점근적 표기법
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자