[백엔드 기술면접] 공간복잡도
공간복잡도
입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양을 의미한다.
이는 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할경우도 포함하며 배열이든 맵이든 셋이든 요소들을 담을 공간이면 다 적용이 된다.
서론
int a[10000000]; // 전역변수
void f(){
int b[1004]; // 지역변수
}
int main(){
}
다음 코드에서 int형 배열 1000만짜리, 1004개짜리 1개를 선언을 했는데, 둘 다 포함해서 공간 복잡도를 계산합니다.
이 때 입력이 N이 들어오고 거기에 N개 짜리 int형 요소를 담아야 할 공간이 필요한다면 4N바이트의 공간이 필요하겠죠??
이를 빅오표기법으로 나타내면 O(N)이 됩니다.
본론
사실, 이러한 공간복잡도의 개념은 문제를 푸는데 잘 사용되지 않는다.
보통 문제를 풀 때 배열의 범위 등을 잡을 때는 2가지 방식을 사용하여 잡습니다.
- 최대범위
- 대부분의 문제의 최대범위를 기반으로 배열을 미리 만들곤 합니다.
- 다음 문제에서 N의 최대범위는 얼마일까? 무려 100만입니다.
입력
첫째 줄에 수의 개수 N(1<= 1,000,000) ~ 생략
int a[1000000]; -> 미리 배열을 만든다.
- 메모리 제한
다음과 같은 문제에서 메모리 제한은 512MB입니다. 그러면 계산을 해보면 512MB는 512,000,000바이트 입니다. 그러면 int a[128000000];을 선언할 수 있겠네요?
int가 4바이트니깐 나누기 4를 하면 나옴.
그렇다면 실제로 이 문제를 테스트를 해보면 2차원 배열이 필요하니 쪼개보면.. 적당히 10000*10000으로 해서 계산해봅시다.
이런 결과 값이 나오는데 실제로 하기가 힘들다. 1000만을 기준으로 문제를 풀어보자!!(정확한 것은 아니고 대강 감을 잡는 용도)
결론
문제를 풀 때는 최대범위나 메모리 제한을 고려하고, 이 때 메모리 제한 같은 경우는 잘 사용이 안되고 보통은 천만을 잡고 들어가면 된다.