[알고리즘] 03. 공간복잡도란 무엇인가?

[알고리즘] 03. 공간복잡도란 무엇인가?

지난 글에서는 시간복잡도와 Big-O에 대해 정리했습니다. 이번 글에서는 알고리즘을 분석할 때 시간복잡도와 함께 자주 등장하는 공간복잡도에 대해 알아보겠습니다.

시간복잡도가 코드가 얼마나 오래 걸리는지를 보는 기준이라면, 공간복잡도는 코드가 실행될 때 메모리를 얼마나 사용하는지를 보는 기준입니다.

공간복잡도는 알고리즘이 실행되는 동안 필요한 메모리의 양을 표현하는 개념입니다.

---

1. 공간복잡도가 필요한 이유

알고리즘 문제를 풀 때는 보통 실행 시간만 생각하기 쉽습니다. 하지만 프로그램은 실행되는 동안 메모리도 함께 사용합니다.

예를 들어 배열을 만들거나, 리스트에 값을 저장하거나, 방문 여부를 체크하기 위해 boolean 배열을 만드는 것도 모두 메모리를 사용하는 작업입니다.

• 배열 생성
• 리스트 생성
• 해시맵 사용
• 방문 배열 사용
• 재귀 호출로 인한 스택 사용

입력 크기가 작을 때는 크게 문제가 되지 않지만, 입력 크기가 커질수록 메모리 사용량도 중요한 기준이 됩니다.

---

2. 시간복잡도와 공간복잡도의 차이

시간복잡도와 공간복잡도는 모두 알고리즘의 효율을 분석하는 기준입니다. 하지만 바라보는 대상이 다릅니다.

구분	의미	관심 대상
시간복잡도	실행 횟수가 얼마나 증가하는가	속도
공간복잡도	메모리 사용량이 얼마나 증가하는가	메모리

쉽게 말하면 시간복잡도는 얼마나 빠른가를 보고, 공간복잡도는 얼마나 많은 공간을 쓰는가를 봅니다.

알고리즘은 빠르기만 해도 안 되고, 메모리를 너무 많이 사용해도 문제가 될 수 있습니다.

---

3. O(1) 공간복잡도

공간복잡도 O(1)은 입력 크기와 상관없이 추가로 사용하는 메모리가 거의 일정한 경우입니다.

int a = 10;
int b = 20;

int sum = a + b;

System.out.println(sum);

위 코드는 변수 몇 개만 사용합니다. 입력 데이터가 커지는 상황이 아니기 때문에 메모리 사용량은 거의 일정합니다.

이런 경우 공간복잡도는 O(1)입니다.

---

4. O(N) 공간복잡도

공간복잡도 O(N)은 입력 크기 N에 비례해서 메모리 사용량이 증가하는 경우입니다. 배열이나 리스트를 새로 만들 때 자주 등장합니다.

int n = 5;
int[] numbers = new int[n];

for (int i = 0; i < n; i++) {
    numbers[i] = i + 1;
}

위 코드는 n개의 값을 저장할 수 있는 배열을 만듭니다. n이 5면 5칸, n이 100이면 100칸이 필요합니다.

입력 크기에 따라 필요한 공간도 함께 증가하므로 공간복잡도는 O(N)입니다.

---

5. O(N²) 공간복잡도

공간복잡도 O(N²)은 2차원 배열처럼 N × N 크기의 공간을 사용하는 경우입니다.

int n = 5;
int[][] board = new int[n][n];

위 코드는 n행 n열의 2차원 배열을 생성합니다. n이 5라면 25칸이 필요하고, n이 100이라면 10,000칸이 필요합니다.

N	N × N 공간
10	100칸
100	10,000칸
1,000	1,000,000칸

2차원 배열은 그래프, 지도, 게임판, 격자 탐색 문제에서 자주 사용됩니다. 하지만 입력 크기가 커질수록 메모리 사용량도 빠르게 증가하기 때문에 주의해야 합니다.

---

6. 추가 공간이란 무엇인가?

공간복잡도를 볼 때는 보통 추가로 사용하는 공간을 중요하게 봅니다.

예를 들어 이미 주어진 배열을 그대로 사용하면서 합계만 구한다면 추가 메모리는 거의 필요하지 않습니다.

int[] arr = {1, 2, 3, 4, 5};

int sum = 0;

for (int i = 0; i < arr.length; i++) {
    sum += arr[i];
}

System.out.println(sum);

위 코드는 배열을 새로 만들지 않고, sum 변수 하나만 추가로 사용합니다. 따라서 추가 공간 기준으로 보면 공간복잡도는 O(1)입니다.

반대로 기존 배열을 복사해서 새로운 배열을 만든다면 추가 공간이 필요합니다.

int[] arr = {1, 2, 3, 4, 5};
int[] copy = new int[arr.length];

for (int i = 0; i < arr.length; i++) {
    copy[i] = arr[i];
}

이 경우 arr의 길이만큼 copy 배열을 새로 만들기 때문에 추가 공간복잡도는 O(N)입니다.

---

7. 재귀 함수와 공간복잡도

공간복잡도에서 놓치기 쉬운 부분이 바로 재귀 호출입니다. 재귀 함수는 자기 자신을 다시 호출하는 구조입니다.

재귀 호출이 발생하면 호출 정보가 메모리의 스택 영역에 쌓입니다. 그래서 배열을 만들지 않았더라도 재귀 깊이에 따라 메모리를 사용할 수 있습니다.

public static void countDown(int n) {
    if (n == 0) {
        return;
    }

    System.out.println(n);
    countDown(n - 1);
}

위 함수는 n이 0이 될 때까지 자기 자신을 계속 호출합니다. n번 호출이 쌓일 수 있으므로 공간복잡도는 O(N)으로 볼 수 있습니다.

재귀는 코드가 짧아 보이더라도 호출 스택이라는 메모리를 사용합니다.

---

8. 공간복잡도 줄이기 예시

공간복잡도를 줄이려면 불필요한 배열이나 리스트를 만들지 않는 것이 중요합니다.

예를 들어 1부터 n까지의 합을 구한다고 생각해보겠습니다.

먼저 배열에 값을 저장한 뒤 합계를 구하는 방식입니다.

int n = 5;
int[] numbers = new int[n];

for (int i = 0; i < n; i++) {
    numbers[i] = i + 1;
}

int sum = 0;

for (int i = 0; i < n; i++) {
    sum += numbers[i];
}

System.out.println(sum);

이 방식은 numbers 배열을 만들기 때문에 공간복잡도는 O(N)입니다.

하지만 꼭 배열에 저장할 필요가 없다면 바로 더할 수 있습니다.

int n = 5;
int sum = 0;

for (int i = 1; i <= n; i++) {
    sum += i;
}

System.out.println(sum);

이 방식은 sum과 i 정도의 변수만 사용합니다. 따라서 공간복잡도는 O(1)입니다.

결과는 같지만 사용하는 메모리는 달라질 수 있습니다. 이런 차이를 보는 것이 공간복잡도입니다.

---

9. 알고리즘 문제에서 공간복잡도 보는 법

알고리즘 문제에서는 시간 제한과 함께 메모리 제한도 주어지는 경우가 많습니다. 그래서 문제를 풀 때는 아래 내용을 확인하는 습관이 좋습니다.

• 배열을 몇 개 만드는가?
• 2차원 배열이 필요한가?
• 해시맵이나 리스트에 데이터를 전부 저장하는가?
• 재귀 호출 깊이가 너무 깊지는 않은가?
• 입력 데이터를 꼭 모두 저장해야 하는가?

특히 N이 매우 큰 문제에서는 모든 값을 저장하는 방식보다, 필요한 값만 계산하면서 처리하는 방식이 더 적합할 수 있습니다.

---

10. 정리

이번 글에서는 공간복잡도에 대해 정리했습니다.

• 공간복잡도는 알고리즘이 사용하는 메모리 양을 표현하는 개념이다.
• O(1)은 입력 크기와 상관없이 추가 메모리가 거의 일정한 경우이다.
• O(N)은 입력 크기만큼 배열이나 리스트를 사용하는 경우이다.
• O(N²)은 2차원 배열처럼 N × N 공간을 사용하는 경우이다.
• 재귀 함수는 호출 스택 때문에 메모리를 사용할 수 있다.
• 불필요한 저장 공간을 줄이면 공간복잡도를 개선할 수 있다.

공간복잡도는 시간복잡도보다 덜 강조되는 것처럼 보이지만, 실제로는 알고리즘을 안정적으로 통과시키기 위해 꼭 필요한 개념입니다.

빠른 코드도 중요하지만, 메모리를 적절히 사용하는 코드도 좋은 코드입니다.

---

다음 글 예고

다음 글에서는 입력 크기별 알고리즘 선택법에 대해 알아보겠습니다.

문제의 입력 제한을 보고 어떤 시간복잡도의 풀이가 가능한지 판단하는 방법을 정리해보겠습니다.