이것이취업을위한코딩테스트다 - Chapter 01 코딩테스트 개요 2. 복잡도 - 공간 복잡도

  주제

복잡도는 알고리즘의 성능을 나타내는 척도이며, 공간 복잡도에 대해 알아보자.

  내용

공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 거처럼 빅오 표기법을 이용한다. 즉, 공간 복잡도 또한 O (Nlog), O(N^2) 등으로 표기한다. 다만, 앞서 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다. 

 

코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 정수형 자료형인 INT를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자.

- int a[1000]: 4KB

- int a[1000000]: 4MB

- int a[2000][2000]: 16MB

 

코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다. 다시 말해 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미이다. 파이썬에서는 int 자료형이 없지만, 파이썬에서도 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다는 점을 기억하자. 

만약 리스트의 크기가 1000만 단위 이상이라면 자신이 알고리즘을 잘못 설계한 것이 아닌지 고민해봐야 한다.