[코테 개념 정리] Space Complexity : 공간 복잡도

지난 글에서는 Big-O 표기법과 시간 복잡도에 대해서 알아봤습니다.

오늘은 코딩 테스트 문제에서 시간 복잡도와 함께 자주 언급되는 공간 복잡도(Space Complexity)에 대해 정리해 보겠습니다.

 

공간 복잡도란? 

• 프로그램이 실행될 때 필요로 하는 메모리 사용량
• 입력 크기 n에 따라 메모리 사용량이 어떻게 변하는지 나타냄
• 시간 복잡도가 얼마나 오래 걸리냐라면, 공간 복잡도는 얼마나 많은 메모리를 쓰냐 라는 관점

 

공간 복잡도도 Big-O 표기법을 사용? 

• 시간 복잡도는 연산 횟수 증가율을 Big-O로 표현
• 공간 복잡도는 메모리 사용량 증가율을 Big-O로 표현
• 결국 입력 크기 n이 커질 때, 얼마나 많은 자원이 필요 해지는가를 같은 방식으로 표현

 

공간 복잡도 종류

종류	설명	예시 / 복잡도
Fixed Part (고정 공간)	프로그램 실행에 필요한 기본 메모리 (코드, 상수, 기본 자료형) 입력 크기와 상관없이 항상 일정	O(1)
Input Space (입력 공간)	입력 데이터를 저장하는 데 필요한 공간	배열 크기 n → O(n)
Auxiliary Space (보조 공간)	알고리즘 실행 중 추가로 사용하는 메모리	임시 배열, 재귀 호출 스택
Output Space (출력 공간)	결과를 저장하는 데 필요한 공간	출력 크기에 따라 달라짐

 

코드로 알아보기 

// JAVA

// O(1) - 상수 공간
int sumTwo(int a, int b) {
    int result = a + b; // 입력 크기와 무관
    return result;
}

// O(n) - 선형 공간
int[] copyArray(int[] arr) {
    int[] newArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

// O(n^2) - 2차원 배열
int[][] makeMatrix(int n) {
    return new int[n][n];
}

# Python

# O(1) - 상수 공간
def sum_two(a, b):
    result = a + b
    return result

# O(n) - 선형 공간
def copy_array(arr):
    new_arr = arr[:]  # 입력 크기만큼 새로운 배열 생성
    return new_arr

# O(n^2) - 2차원 배열
def make_matrix(n):
    matrix = [[0] * n for _ in range(n)]
    return matrix

 

 

공간 복잡도 최적화 방법

 

1. In-place 알고리즘 사용

• 새로운 배열/리스트를 만들지 않고, 기존 데이터를 제자리에서 수정

Ex. 배열 뒤집기

// Before: 새로운 배열 사용 → O(n) 공간
int[] reverseCopy(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        res[i] = arr[n - 1 - i];
    }
    return res;
}

// After: 제자리 뒤집기 → O(1) 공간
void reverseInPlace(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}

 

2. 데이터 구조 최소화

• 불필요한 자료구조를 만들지 말고, 꼭 필요한 자료만 저장

Ex. 중복 체크 (List -> Set)

// 리스트 사용 (비효율적, O(n^2))
boolean hasDuplicateList(int[] arr) {
    List<Integer> list = new ArrayList<>();
    for (int x : arr) {
        if (list.contains(x)) return true;
        list.add(x);
    }
    return false;
}

// 해시셋 사용 (효율적, O(n) 공간)
boolean hasDuplicateSet(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int x : arr) {
        if (!set.add(x)) return true;
    }
    return false;
}

방법	시간 복잡도	공간 복잡도	특징
List	O(n²) (삽입 n × 탐색 n)	O(n)	탐색 시 매번 선형 검색 필요
Set	O(n) (삽입+탐색 평균 O(1))	O(n)	중복 허용 X, 빠른 탐색 가능

 

3. 재귀 대신 반복 사용

• 재귀 호출은 스택 메모리를 계속 사용 → 반복문으로 바꿔 O(1) 공간

Ex. 피보나치 수열

// 재귀: O(n) 스택 공간
int fibRecursive(int n) {
    if (n <= 1) return n;
    return fibRecursive(n-1) + fibRecursive(n-2);
}

// 반복: O(1) 공간
int fibIter(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int tmp = a;
        a = b;
        b = tmp + b;
    }
    return a;
}

 

4. 동적 프로그래밍(DP) 최적화

• DP 테이블을 전체(n) 쓰지 않고, 필요한 부분만 유지

Ex. 피보나치 (DP 배열 → O(n), 최적화 → O(1))

// DP 배열: O(n) 공간
int fibDP(int n) {
    int[] dp = new int[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// DP 최적화: O(1) 공간
int fibDPOptimized(int n) {
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return n == 0 ? 0 : curr;
}

 

 

5. 스트리밍 / 슬라이딩 윈도우

• 데이터를 한 번에 다 저장하지 않고, 필요한 부분만 유지

Ex. 길이 k 부분 배열의 최대 합

// 슬라이딩 윈도우: O(1) 공간
int maxSubarraySum(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxSum = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i-k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

 

 

6. 메모리-시간 트레이드오프 고려

• 때로는 공간을 줄이면 시간이 늘어날 수 있음
• 코테에서는 보통 “시간 복잡도 최적화 > 공간 복잡도 최적화”이지만, 메모리 제한이 빡빡한 문제는 공간 절약이 필수

Ex. 구간 합 문제 

• 단순 합: O(1) 공간, O(n) 시간
• Prefix Sum: O(n) 공간, O(1) 시간

// Prefix Sum: O(n) 공간
long[] buildPrefix(int[] arr) {
    long[] P = new long[arr.length + 1];
    for (int i = 0; i < arr.length; i++) {
        P[i+1] = P[i] + arr[i];
    }
    return P;
}
long rangeSum(long[] P, int L, int R) {
    return P[R+1] - P[L];
}

 

 

실무에서 시간 복잡도, 공간 복잡도는 언제 사용되는가?

구분	대표 상황 / 기능 예시
시간 복잡도가 중요한 경우	대용량 데이터 처리 (로그 분석, 추천 시스템) 실시간 서비스 (검색 자동완성, 채팅 서버) 트래픽이 몰리는 구간 (결제, 이벤트 응모 API)
공간 복잡도가 중요한 경우	모바일/임베디드 환경 (메모리 제한 심한 장치) 대규모 캐시/버퍼 설계 (Redis, Kafka 큐 등) 그래프/트리 탐색 시 메모리 최적화 (DFS → O(h) 스택, BFS → O(n) 큐)