알고리즘 공간 복잡도 (Space Complexity)

 

---

알고리즘 공간 복잡도란? 기초 개념부터 예시까지 쉽게 정리

코딩 문제를 풀다 보면 '시간 복잡도는 O(n), 공간 복잡도는 O(1)' 같은 문장을 자주 보게 됩니다. 대부분 시간 복잡도에는 익숙하지만, 공간 복잡도(Space Complexity)는 상대적으로 생소하게 느껴지는 분들이 많습니다. 오늘은 알고리즘의 공간 복잡도 개념부터 계산법, 예시, 효율화 전략까지 초보자도 이해하기 쉬운 방식으로 정리해보겠습니다.

---

공간 복잡도란 무엇인가?

공간 복잡도(Space Complexity)란, 알고리즘이 문제를 해결하는 데 사용하는 메모리 양을 의미합니다. 프로그램을 실행할 때는 단순히 코드를 실행하는 시간뿐만 아니라, 데이터를 저장하고 처리하기 위한 메모리 공간도 중요합니다.

• 예를 들어, 두 수를 더하는 간단한 코드에는 두 변수와 하나의 결과값만 필요하므로 공간 복잡도는 매우 낮습니다.
• 반면 수천 개의 데이터를 저장하거나 재귀 호출이 많이 발생하는 알고리즘은 메모리를 많이 사용하게 됩니다.

이처럼 공간 자원을 얼마나 효율적으로 사용하는지 판단하는 기준이 바로 공간 복잡도입니다.

---

공간 복잡도 계산 요소

공간 복잡도는 주로 다음과 같은 요소들로 구성됩니다.

1. 입력 공간 (Input Space)
   사용자가 제공하는 입력값 자체가 차지하는 공간입니다. 입력이 많아질수록 자연스럽게 증가합니다.
2. 고정 공간 (Fixed Part)
   변수 선언, 상수, 포인터, 정수형 등 프로그램 실행을 위해 고정적으로 사용되는 공간입니다. 일반적으로 입력 크기에 관계없이 일정합니다.
3. 가변 공간 (Variable Part)
   배열, 동적 할당, 재귀 호출 등 실행 중 생성되는 임시 변수들이 차지하는 공간입니다. 이 부분이 알고리즘 성능에 큰 영향을 미칩니다.

---

공간 복잡도의 표기법 – Big-O 표기

공간 복잡도도 빅오(Big-O) 표기법을 사용합니다. 이는 가장 빠르게 증가하는 항만 남겨 단순화한 표현입니다.

• O(1) : 입력 크기와 관계없이 일정한 공간만 사용하는 경우
• O(n) : 입력의 크기에 비례하여 메모리를 사용하는 경우
• O(n²) : 2차원 배열이나 중첩 반복문으로 공간이 증가하는 경우

---

공간 복잡도 예제 – 쉽게 이해하기

예제 1: O(1) 공간 복잡도

def sum_two_numbers(a, b):
    return a + b

• 입력값 두 개, 출력값 하나만 사용 → 고정된 메모리 사용
• 공간 복잡도: O(1)

예제 2: O(n) 공간 복잡도

def create_list(n):
    result = []
    for i in range(n):
        result.append(i)
    return result

• 길이가 n인 리스트 생성 → 입력 크기에 따라 공간 증가
• 공간 복잡도: O(n)

예제 3: 재귀 함수와 공간 복잡도

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

• 함수 호출 스택이 n번 쌓임 → 스택 메모리 사용
• 공간 복잡도: O(n)

---

시간 복잡도 vs 공간 복잡도

많은 사람들이 시간 복잡도에만 집중하지만, 공간 복잡도도 무시할 수 없는 요소입니다. 특히 다음과 같은 상황에서는 공간 복잡도가 중요한 역할을 합니다.

• 메모리가 제한된 환경 (예: 임베디드 시스템, 모바일)
• 대용량 데이터를 처리하는 빅데이터 환경
• 다수의 알고리즘 중 메모리 사용량이 성능의 핵심일 때

간혹 시간 복잡도는 O(n)이지만 공간 복잡도는 O(1)인 알고리즘과, 그 반대인 경우도 있어 상황에 맞는 트레이드오프가 필요합니다.

---

공간 복잡도 줄이는 전략

공간 복잡도를 낮추는 것은 더 나은 성능의 알고리즘을 설계하는 데 핵심입니다. 다음과 같은 방법들이 많이 사용됩니다.

✔️ 1. In-place 알고리즘 사용

데이터를 추가 공간 없이 기존 공간 내에서 처리하는 방법입니다.
예: 리스트 뒤집기, 정렬 등에서 추가 배열 없이 처리

✔️ 2. 재귀 대신 반복문 사용

재귀 함수는 호출마다 스택 공간을 사용하므로, 반복문으로 바꾸면 공간을 절약할 수 있습니다.

✔️ 3. 불필요한 변수 제거

임시 변수, 복사된 리스트 등을 줄이면 메모리를 절약할 수 있습니다.

✔️ 4. Generator 사용 (Python)

리스트가 아닌 제너레이터로 데이터를 처리하면 메모리 효율성이 매우 높아집니다.

def generator_example(n):
    for i in range(n):
        yield i

---

실무와 코딩 테스트에서의 공간 복잡도

실무에서는 공간 복잡도가 문제가 되는 경우가 의외로 많습니다.

• 대량의 로그 데이터를 처리하거나,
• 이미지 및 동영상 처리 시 대용량 행렬 연산,
• 머신러닝의 모델 파라미터 저장 등

한편, 코딩 테스트에서는 다음과 같은 유형의 문제가 공간 복잡도를 평가하기도 합니다.

• 제한된 메모리 내에서 문제 해결
• 배열을 복사하지 않고 in-place로 처리 요구
• 재귀 스택 제한을 고려한 풀이 등

---

 

공간 복잡도는 시간 복잡도와 함께 알고리즘을 이해하고 최적화하는 데 매우 중요한 기준입니다.
문제를 풀 때는 단순히 ‘빠르게 동작한다’는 기준뿐만 아니라, 메모리 자원을 얼마나 적절히 사용하고 있는지도 꼭 고려해야 합니다.

특히 요즘처럼 모바일, IoT, AI, 대규모 처리 환경이 확산되는 시대에는 공간 효율성의 중요성이 더욱 커지고 있습니다. 오늘 배운 공간 복잡도의 기초 개념을 바탕으로, 앞으로는 시간과 공간을 모두 고려한 효율적인 알고리즘 설계를 해보시길 바랍니다.