[Algorithm] 공간복잡도(Space Complexity) 평가

프로그램의 소요시간 뿐만 아니라, 사용되는 메모리도 중요하다. 컴퓨터의 메모리는 한정되어 있기 때문에, 동일한 프로그램이라면 차지하는 메모리가 적은 것이 더 좋다. 그렇기 때문에 시간복잡도 뿐만 아니라 공간복잡도도 중요하다.

공간복잡도도 시간복잡도와 동일하게 점근적 표기법을 사용한다. 간단한 예시를 통해 공간복잡도를 알아보자.

예시 코드의 공간복잡도 분석

def example(n):
    arr = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            arr[i][j] = 1

결국 공간복잡도는 '이 코드가 메모리를 얼마나 차지하고 있을까?'라는 의미이다. 자연스럽게 다른 코드보다 arr = [[0] * n for _ in range(n)] 부분에 눈이 갈 것이다. 실제로 다른 코드는 메모리를 많이 차지하지 않기 때문에, 공간복잡도는 O(n²)이라고 볼 수 있다.

앞에서 시간복잡도 문제를 풀어보았다면 공간복잡도는 비교적 쉽게 이해할 수 있을 것이다.

공간복잡도의 필요성

공간복잡도는 문제에서 메모리 제한이 주어지는 경우에 중요하다. 예를 들어, 메모리 제한이 80MB라고 주어진 경우가 있다.

보통 메모리를 계산하는 경우에는 C++을 기준으로 생각한다. C++에서는 int가 4 byte, char가 1 byte, double이 8 byte, short가 2 byte로 정해져 있다.

따라서 이 부분만 알고 있으면, int로 2천만 개가 대략 80MB라는 것을 이용하여 다음과 같이 쉽게 계산이 가능하다.

• int a[20000000] : 80MB
• int a[2000000] : 80MB / 10 = 8MB
• char a[20000000] : 80MB / 4 = 20MB
• double a[20000000] : 80MB * 2 = 160MB

따라서 사용하는 배열의 크기에 따라 대략 어느 정도의 메모리를 사용하는지를 미리 계산할 수 있어, 메모리 제한을 넘지 않는 코드인지를 확인해볼 수 있다.

다른 언어에서도 메모리 사용량을 계산하는 방법은 비슷하다. 각 언어에서 기본 자료형의 크기를 알고 있으면 된다. 몇 가지 예를 들어보자.

Python

Python에서는 객체의 크기를 sys.getsizeof 함수를 이용하여 측정할 수 있다.

import sys

x = 10
print(sys.getsizeof(x))  # 28 bytes

Java

Java에서는 int가 4 byte, char가 2 byte, double이 8 byte, boolean이 1 byte이다. 배열의 경우, 각 요소의 크기와 배열의 오버헤드를 고려해야 한다.

int[] arr = new int[20000000];

이 경우 int 배열이므로 4 * 20,000,000 = 80MB를 차지한다.

JavaScript

JavaScript에서는 메모리 관리가 자동으로 이루어지지만, 기본 자료형의 크기는 대략적으로 다음과 같다:

• Number: 8 byte
• Boolean: 4 byte
• String: 2 byte per character + object overhead

C#

C#에서도 자료형의 크기는 C++과 유사하다:

• int: 4 byte
• char: 2 byte
• double: 8 byte
• bool: 1 byte

배열의 크기도 유사하게 계산할 수 있다.

int[] arr = new int[20000000];

이 경우 int 배열이므로 4 * 20,000,000 = 80MB를 차지한다.

이처럼 각 언어에서 기본 자료형의 크기를 알고 있으면, 프로그램이 사용하는 메모리를 대략적으로 계산할 수 있다. 이를 통해 메모리 제한을 넘지 않도록 주의할 수 있다.