복잡도 (Complexity) (3) - 공간복잡도

공간복잡도란 쉽게 말해 소스코드에서 메모리를 사용하는 양이라고 할 수 있다. 공간복잡도 또한 시간복잡도와 마찬가지로 빅오 표기법을 사용하여 표기한다. 즉 O(N), O(log N)등과 같이 표기하는 것이다. 코딩 테스트에서 아래와 같은 문제 조건을 볼 수 있는데 이는 시간복잡도와 공간복잡도에 제한을 두기 위해서이다.

'시간 제한 1초, 메모리 제한 128MB'

C언어에서 기본자료형의 메모리 크기는 아래와 같다.

자료형	키워드	메모리 크기
문자형	char	1 Bytes
정수형	short	2 Bytes
	int	4 Bytes
	long	4 Bytes
부호없는 문자형	unsigned char	1 Bytes
부호없는 정수형	unsigned short	2 Bytes
	unsigned int	4 Bytes
	unsigned long	4 Bytes
부동 소수형	float	4 Bytes
	double	8 Bytes

코딩 테스트에서 대부분 문제 해결을 위해 리스트(배열)을 사용하게 되는데 위의 표를 참고하여 공간복잡도를 계산한 예시를 나열한다.

• int a[1000] : 4KB
• int a[1000000] : 4MB
• int a[2000][2000] : 16MB

코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB로 제한한다. 파이썬에서는 위와 같은 int 자료형은 없지만 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다는 점을 기억해야 한다. 만약 작성한 소스코드에서 리스트의 크기가 1,000만 단위 이상이라면 알고리즘을 잘못 서례한 것은 아닌지 확인해 봐야한다는 것이다.