시스매

알고리즘 메모리 사용 설명서 공간 복잡도 완벽 정복

21 min read

2025-08-24 13:28

알고리즘 메모리 사용 설명서 공간 복잡도 완벽 정복

코드를 작성하고 프로그램을 실행할 때, 우리는 종종 ‘얼마나 빠른가’에만 집중하곤 합니다. 하지만 ‘얼마나 많은 메모리를 사용하는가’ 역시 그에 못지않게, 때로는 더 중요할 수 있습니다. 특히 제한된 메모리 환경(임베디드 시스템, 모바일 기기)이나 수십억 개의 데이터를 처리해야 하는 빅데이터 환경에서는 메모리 사용량이 프로그램의 성패를 좌우하기도 합니다.

이때 등장하는 개념이 바로 **공간 복잡도(Space Complexity)**입니다. 공간 복잡도는 알고리즘이 문제를 해결하기 위해 얼마나 많은 메모리 공간을 필요로 하는지를 나타내는 척도입니다. 단순히 ‘메모리를 많이 쓴다’가 아니라, 입력 데이터의 크기가 커짐에 따라 메모리 사용량이 어떻게 변하는지를 분석하는 것이 핵심입니다.

이 핸드북에서는 공간 복잡도의 개념이 왜 필요한지부터 시작하여, 어떻게 계산하고 분석하는지, 그리고 시간 복잡도와의 관계는 무엇인지까지, 공간 복잡도의 모든 것을 깊이 있게 탐험해 보겠습니다.

1. 공간 복잡도는 왜 만들어졌을까? (탄생 배경)

컴퓨터 과학의 초기, 컴퓨터의 메모리는 지금과는 비교할 수 없을 정도로 작고 비쌌습니다. 1960년대 아폴로 우주선에 탑재된 컴퓨터의 RAM은 고작 4KB였습니다. 이런 환경에서 프로그래머들은 단 1바이트의 메모리라도 아끼기 위해 필사적인 노력을 기울여야 했습니다. 알고리즘이 아무리 빨라도 주어진 메모리 안에 들어가지 않으면 무용지물이었기 때문입니다.

이러한 물리적 제약은 알고리즘의 효율성을 평가하는 새로운 기준을 요구했습니다. 실행 시간뿐만 아니라, ‘메모리 공간’이라는 자원을 얼마나 효율적으로 사용하는지가 중요한 평가 지표가 된 것입니다. 이것이 공간 복잡도 개념이 탄생하게 된 직접적인 배경입니다.

시간이 흘러 메모리 가격이 저렴해지고 용량이 기하급수적으로 늘어났지만, 공간 복잡도의 중요성은 사라지지 않았습니다. 오히려 그 형태를 바꾸어 더욱 중요해졌습니다.

  • 빅데이터 시대의 도래: 페타바이트(PB)를 넘어 엑사바이트(EB) 단위의 데이터를 처리하는 시대가 열렸습니다. 아무리 메모리가 커져도, 처리해야 할 데이터의 크기가 그보다 더 빠르게 증가한다면 메모리 부족 문제는 언제든 발생할 수 있습니다.

  • 다양한 컴퓨팅 환경: 고성능 서버뿐만 아니라 스마트폰, 웨어러블 기기, IoT 센서 등 메모리가 제한적인 환경에서 동작하는 프로그램이 늘어났습니다. 이런 환경에서는 공간 효율성이 곧 성능과 직결됩니다.

  • 동시성 프로그래밍: 여러 작업을 동시에 처리할 때, 각 작업이 사용하는 메모리의 총합은 시스템 전체에 큰 부담을 줄 수 있습니다. 공간 복잡도를 이해하고 최적화하는 것은 안정적인 동시성 시스템을 구축하는 데 필수적입니다.

결론적으로 공간 복잡도는 **‘한정된 자원인 메모리를 얼마나 효율적으로 사용하여 문제를 해결하는가’**라는 근본적인 질문에 답하기 위해 만들어졌습니다. 이는 단순히 메모리를 아끼는 것을 넘어, 알고리즘의 확장성과 안정성을 보장하는 핵심적인 개념입니다.

2. 공간 복잡도의 구조: 무엇으로 이루어져 있나?

알고리즘이 사용하는 총 메모리 공간은 크게 두 가지 부분으로 나눌 수 있습니다. 공간 복잡도를 분석할 때는 이 두 부분을 모두 고려해야 합니다.

총 공간 = 고정 공간 (Fixed Space) + 가변 공간 (Variable Space)

2.1. 고정 공간 (Fixed Space Component)

고정 공간은 입력 데이터의 크기와 상관없이 항상 일정한 크기를 차지하는 메모리 공간을 의미합니다. 코드 자체의 크기, 상수, 단순 변수 등이 여기에 해당합니다.

  • 코드 저장 공간: 우리가 작성한 프로그램 코드(명령어)가 저장되는 공간입니다.

  • 단순 변수 및 상수: int a = 10;, const double PI = 3.14; 와 같이 입력값의 크기와 무관하게 선언되는 변수나 상수가 차지하는 공간입니다.

  • 함수 호출 정보: 함수가 호출될 때 생성되는 스택 프레임에 저장되는 복귀 주소 등도 고정 공간으로 볼 수 있습니다.

예를 들어, 두 숫자를 더하는 간단한 함수를 생각해 봅시다.

function add(a, b) {
  let result = a + b; // 'result'라는 변수 공간
  return result;
}

이 함수에서 a, b, result라는 3개의 변수를 위한 공간이 필요합니다. 입력값 a와 b가 10이든 10억이든, 이 함수가 필요로 하는 변수의 개수는 3개로 동일합니다. 따라서 이 함수의 고정 공간은 일정하다고 말할 수 있습니다.

2.2. 가변 공간 (Variable Space Component)

가변 공간은 알고리즘이 실행되는 동안 입력 데이터의 크기에 비례하여 동적으로 변하는 메모리 공간입니다. 공간 복잡도 분석의 핵심은 바로 이 가변 공간을 파악하는 것입니다.

  • 동적 할당 메모리: new, malloc 등을 통해 동적으로 할당되는 메모리 공간입니다.

  • 자료 구조: 입력 데이터의 크기에 따라 크기가 변하는 배열, 리스트, 해시 테이블 등의 자료 구조가 차지하는 공간입니다.

  • 재귀 호출 스택: 재귀 함수가 자기 자신을 호출할 때마다 스택에 새로운 정보(매개변수, 지역 변수 등)가 쌓입니다. 재귀의 깊이가 입력값 n에 비례한다면, 스택 공간 역시 n에 비례하여 증가합니다.

예를 들어, 크기가 n인 배열의 모든 요소를 합산하는 함수를 보겠습니다.

function sumArray(arr) { // 입력: 크기가 n인 배열 arr
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

이 함수는 입력으로 크기 n인 배열 arr을 받습니다. 함수 내부에서는 sum과 i라는 두 개의 변수만 추가로 사용합니다. arr의 크기가 10이든 100만이든, sum과 i를 위한 공간은 변하지 않습니다. 하지만 알고리즘은 arr 자체를 저장할 공간이 필요합니다. 따라서 이 함수의 공간 복잡도는 입력 배열의 크기 n에 직접적으로 의존합니다.

3. 공간 복잡도 사용법 (계산과 표기)

공간 복잡도는 시간 복잡도와 마찬가지로 점근적 표기법(Asymptotic Notation), 특히 빅오(Big-O) 표기법을 사용하여 나타냅니다. 빅오 표기법은 입력 데이터의 크기 n이 무한히 커질 때, 메모리 사용량이 어떤 형태로 증가하는지를 나타냅니다.

3.1. 빅오(Big-O) 표기법

빅오 표기법은 알고리즘의 성능을 간결하게 표현하는 방법입니다. 공간 복잡도에서는 ‘입력 크기 n에 대한 메모리 사용량의 상한선’을 의미합니다.

빅오 표기명칭설명예시
O(1)상수 공간 (Constant Space)입력 n의 크기와 상관없이 일정한 메모리만 사용두 변수 교환, 단순 사칙연산
O(log n)로그 공간 (Logarithmic Space)입력 n이 커져도 메모리 사용량은 매우 완만하게 증가이진 탐색 (재귀 구현 시)
O(n)선형 공간 (Linear Space)입력 n의 크기와 정비례하여 메모리 사용량 증가크기 n인 배열 생성, for 루프
O(n²)이차 공간 (Quadratic Space)입력 n의 제곱에 비례하여 메모리 사용량 증가n x n 크기의 2차원 배열 생성
O(2ⁿ)지수 공간 (Exponential Space)입력 n이 조금만 커져도 메모리 사용량이 폭발적으로 증가특정 조합 문제의 재귀적 풀이

3.2. 공간 복잡도 계산 예시

실제 코드 예시를 통해 공간 복잡도를 계산해 보겠습니다.

예시 1: O(1) - 상수 공간

function swap(a, b) {
  let temp = a;
  a = b;
  b = temp;
}

  • a, b, temp 세 개의 변수만 사용합니다.

  • 입력값 a, b의 크기가 어떻든 필요한 변수의 개수는 3개로 고정됩니다.

  • 공간 복잡도: O(1)

예시 2: O(n) - 선형 공간

function createArray(n) {
  let newArr = [];
  for (let i = 0; i < n; i++) {
    newArr.push(i);
  }
  return newArr;
}

  • 입력값 n에 따라 크기가 n인 배열 newArr을 생성합니다.

  • n이 10이면 10개의 요소를, n이 1,000이면 1,000개의 요소를 저장할 공간이 필요합니다.

  • 메모리 사용량이 n에 정비례합니다.

  • 공간 복잡도: O(n)

예시 3: 재귀 함수의 공간 복잡도

재귀 함수는 함수 호출 스택(Call Stack) 때문에 공간 복잡도 분석이 조금 더 까다롭습니다.

// 팩토리얼 계산 (재귀)
function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

  • factorial(5)를 호출하면, 내부적으로 factorial(4), factorial(3), factorial(2), factorial(1)이 차례로 호출됩니다.

  • 각 함수 호출마다 매개변수 n과 반환 주소 등을 저장하기 위한 스택 프레임이 메모리에 쌓입니다.

  • n이 5일 때 5개의 스택 프레임이, n일 때는 n개의 스택 프레임이 쌓입니다.

  • 따라서 스택의 깊이가 n에 비례하므로, **공간 복잡도는 O(n)**이 됩니다.

반면, 반복문으로 구현한 팩토리얼은 어떨까요?

// 팩토리얼 계산 (반복문)
function factorial_iter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

  • 이 함수는 result와 i라는 두 개의 변수만 사용합니다. n의 크기와 상관없이 필요한 변수의 수는 일정합니다.

  • 공간 복잡도: O(1)

  • 이처럼 동일한 기능을 하는 알고리즘이라도 구현 방식에 따라 공간 복잡도가 달라질 수 있습니다.

4. 심화: 시간 복잡도와의 관계 (Trade-off)

알고리즘의 효율성을 논할 때 시간 복잡도와 공간 복잡도는 떼려야 뗄 수 없는 관계입니다. 종종 이 둘은 **상충 관계(Trade-off)**에 있습니다. 즉, 시간을 절약하기 위해 공간을 더 사용하거나, 공간을 절약하기 위해 시간을 더 사용하는 선택의 상황에 놓이게 됩니다.

4.1. 공간을 희생하여 시간을 얻는 경우

대표적인 예는 메모이제이션(Memoization) 또는 캐싱(Caching) 기법입니다. 계산 결과를 메모리에 저장해두고, 동일한 계산이 필요할 때 다시 계산하는 대신 저장된 값을 가져와 사용하는 방식입니다.

피보나치 수열 예시

// 일반 재귀: 시간 복잡도 O(2ⁿ), 공간 복잡도 O(n)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // 동일한 계산이 반복됨
}

// 메모이제이션 적용: 시간 복잡도 O(n), 공간 복잡도 O(n)
let memo = {}; // 계산 결과를 저장할 객체 (공간 추가 사용)
function fib_memo(n) {
  if (n in memo) return memo[n]; // 이미 계산했으면 바로 반환
  if (n <= 1) return n;
  
  memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
  return memo[n];
}

fib_memo 함수는 계산 결과를 저장하기 위해 memo라는 추가적인 저장 공간(해시 테이블)을 사용합니다. 이로 인해 공간 복잡도는 O(n)으로 동일하지만, 중복 계산을 피하게 되어 시간 복잡도가 O(2ⁿ)에서 O(n)으로 획기적으로 개선됩니다. 이는 공간을 사용하여 시간을 구매한 대표적인 사례입니다.

4.2. 시간을 희생하여 공간을 얻는 경우

입력 데이터를 변형하지 않고 제자리에서(in-place) 정렬하는 알고리즘들이 좋은 예입니다.

정렬 알고리즘 예시

  • 합병 정렬 (Merge Sort): 데이터를 나누고 정렬한 뒤 다시 합치는 과정에서 추가적인 배열(임시 공간)이 필요합니다. 따라서 **공간 복잡도가 O(n)**입니다. 하지만 안정적이고 빠른 성능(O(n log n))을 보장합니다.
  • 힙 정렬 (Heap Sort): 주어진 배열 내부에서 데이터의 위치를 바꾸는 것만으로 정렬을 수행합니다. 별도의 추가 배열이 거의 필요 없으므로 **공간 복잡도가 O(1)**입니다. 시간 복잡도는 O(n log n)으로 합병 정렬과 같지만, 실제 실행 시간은 약간 더 걸릴 수 있습니다.

만약 메모리가 극도로 제한된 환경이라면, 약간의 시간 손해를 감수하더라도 공간 복잡도가 O(1)인 힙 정렬을 선택하는 것이 현명한 결정일 수 있습니다. 이는 시간을 사용하여 공간을 구매한 사례입니다.

이처럼 시간과 공간의 상충 관계를 이해하는 것은, 주어진 문제와 환경에 가장 적합한 알고리즘을 선택하는 데 매우 중요합니다.

5. 결론: 현명한 개발자의 메모리 사용법

공간 복잡도는 단순히 ‘메모리 사용량’을 나타내는 숫자가 아닙니다. 그것은 우리가 작성한 코드가 얼마나 효율적이고 확장 가능한지를 보여주는 중요한 지표입니다.

  • 문제의 본질을 파악하라: 알고리즘을 설계하기 전에 입력 데이터의 규모와 시스템의 메모리 제약을 먼저 파악해야 합니다.
  • 자료 구조를 현명하게 선택하라: 같은 문제라도 어떤 자료 구조를 사용하느냐에 따라 공간 효율성이 크게 달라질 수 있습니다.
  • Trade-off를 인지하라: 시간과 공간은 항상 거래 관계에 있음을 기억하고, 현재 상황에서 무엇이 더 중요한 가치인지 판단해야 합니다.
  • 코드를 측정하고 프로파일링하라: 이론적인 분석도 중요하지만, 실제 코드의 메모리 사용량을 측정하고 병목 현상을 찾아내는 실용적인 접근이 필요합니다.

메모리가 풍부해진 현대에도 공간 복잡도에 대한 이해는 여전히 중요합니다. 효율적인 메모리 사용은 더 빠르고, 더 안정적이며, 더 많은 데이터를 처리할 수 있는 강력한 프로그램을 만드는 밑거름이 될 것입니다. 이 핸드북이 여러분의 코드를 한 단계 더 발전시키는 데 도움이 되기를 바랍니다.

레퍼런스(References)

공간 복잡도

그래프 뷰

백링크