공간복잡도

공간복잡도는 "입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양"을 가리킵니다.

이는 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함하여 배열이든 맵이든 셋이든 요소들을 담을 공간이면 모두 적용됩니다.

 

다음 코드에서 int형 배열 1000만 개 1개, 1004개 1개를 선언했습니다. 둘 다 포함해서 공간복잡도를 계산합니다.

 

int a[10000000];
void f()
{
	int b[1004];
}

int main()
{
	return 0;
}

예를 들어 입력이 N이 들어오고 거기에 따라 N개 int형 요소를 담아야 할 공간이 필요하다면 4N바이트의 공간이 필요합니다.

이를 빅오표기법으로 나타내면 O(N)이 됩니다. 상수는 버립니다.

int a[N];

 

사실 이러한 공간복잡도의 개념은 "문제"를 푸는데 잘 사용되지 않습니다.

 

보통 문제를 풀 때 배열의 범위 등을 잡을 땐 두 가지 방법을 기반으로 잡습니다.

 

1. 최대범위

하지만 대부분은 문제의 최대범위를 기반으로 배열을 미리 만들곤 합니다.

예시로 코테 문제에서 N의 최대 범위는 백만입니다. 

그럼 보통 다음과 같이 선언합니다.

int a[1000000];

 

2. 메모리 제한

에시로 메모리 제한은 512MB인 경우, int a[128000000] 을 선언할 수 있는걸까요?

심지어 이차원 배열이 필요한 경우 실제로 작동은 하지만 메모리를 꽤 많이 잡아먹습니다. 

 

1번과 2번의 경우 1000만까지는 괜찮지만 그 이상이라면 내 로직이 맞는지 다시 한번 생각해봐야 합니다.

일반적으로 코딩 테스트에서 천만이라는 조건이 주어진다면 다른 알고리즘을 적용해볼까? 하고 생각할 수 있는 기준으로 잡을 것을 권장합니다.