Ch.1 빅오와 복잡도 분석
공간 복잡도 — 메모리도 자원이다
빠르게 하려면 메모리를 써야 한다?
앞서 중복 탐지를 set으로 O(n)에 해결했습니다. 하지만 set은 데이터를 추가로 저장하므로 메모리를 더 씁니다. 시간을 아꼈지만 공간을 쓴 거죠.
시간과 공간, 둘 다 줄일 수는 없을까?
대부분의 알고리즘은 시간과 공간 사이에서 트레이드오프를 합니다. 이 균형을 아는 것이 면접의 핵심입니다.
핵심 개념
공간 복잡도
알고리즘이 사용하는 추가 메모리의 증가 패턴
트레이드오프
시간을 줄이려면 공간을 더 쓰고, 공간을 줄이려면 시간이 더 걸리는 관계
핵심 내용
시간 복잡도가 '얼마나 오래 걸리나'라면 공간 복잡도는 '메모리를 얼마나 쓰나'
공간 복잡도 측정 규칙: - 입력 데이터 자체는 세지 않음 - 알고리즘이 추가로 만든 변수/배열/해시맵만 측정 - Big-O와 동일한 표기법 사용
변수 몇 개만 쓰면 O(1) 새 배열을 만들면 O(n)
# 공간 O(1) — 변수만 사용
def sum_array(arr):
total = 0 # 변수 1개
for x in arr:
total += x
return total# 공간 O(n) — 새 배열 생성
def double_array(arr):
result = [] # 추가 배열
for x in arr:
result.append(x * 2)
return result중복 탐지 문제로 트레이드오프를 이해합시다
면접에서는 여러 접근법을 비교하고, 상황에 맞는 선택을 설명하면 고득점!
set을 활용한 중복 탐지의 공간 사용량을 추적합니다
seen에 최대 n개 원소가 들어갑니다. 따라서 공간 복잡도는 O(n)
재귀 함수도 콜 스택만큼 공간을 사용합니다
# 재귀: 공간 O(n) — 콜 스택
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
# factorial(5) → 스택에 5개 쌓임
# 5 → 4 → 3 → 2 → 1재귀 공간 복잡도: - 재귀 깊이 n → 공간 O(n) - 이진탐색 재귀 → 공간 O(log n) - Python 기본 재귀 제한: 1,000
for 루프 안에서 변수 하나만 갱신하는 알고리즘의 공간 복잡도는?
시간 O(n), 공간 O(n)인 알고리즘과 시간 O(n²), 공간 O(1)인 알고리즘. 메모리가 부족할 때 어느 쪽이 유리한가?
재귀 깊이가 n인 함수의 공간 복잡도를 채우세요: O(___)
재귀 깊이 n일 때 공간 복잡도: O(___)
공간의 달인
핵심 용어
공간 복잡도
알고리즘이 사용하는 추가 메모리의 증가 패턴
트레이드오프
시간 ↔ 공간, 하나를 줄이면 다른 하나가 늘어나는 관계
이중 for문
시간 O(n²) / 공간 O(1)
set 활용
시간 O(n) / 공간 O(n)
정렬 후 인접 비교
시간 O(n log n) / 공간 O(1)*
정리 노트
공간 복잡도 — 메모리도 자원이다
공간 복잡도 기본
- O(1) 공간
- 변수 몇 개만 사용 (상수 공간)
- O(n) 공간
- 새 배열/해시맵 생성 (선형 공간)
- 재귀
- 콜 스택 깊이만큼 공간 사용
트레이드오프
- 시간 ↓
- 보통 공간 ↑ (해시맵 캐싱 등)
- 공간 ↓
- 보통 시간 ↑ (in-place 알고리즘)
- 면접 전략
- 여러 접근법 비교 후 상황 설명
면접에서 '시간 vs 공간 트레이드오프가 있는데, 어떤 제약이 있나요?'라고 물어보면 감점 없이 가산점!
시각 자료
핵심 정리
- 1공간 복잡도 = 추가 메모리 사용량
- 2시간-공간 트레이드오프가 핵심
- 3재귀 깊이 = 콜 스택 공간
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작