Algorithm
복잡도 (Complexity) (3) - 공간복잡도
공대생안씨
2023. 7. 19. 21:36
공간복잡도란 쉽게 말해 소스코드에서 메모리를 사용하는 양이라고 할 수 있다. 공간복잡도 또한 시간복잡도와 마찬가지로 빅오 표기법을 사용하여 표기한다. 즉 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만 단위 이상이라면 알고리즘을 잘못 서례한 것은 아닌지 확인해 봐야한다는 것이다.