[코딩 테스트] 공간 복잡도

공간 복잡도란?

→ 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

 

ex) N짜리 2차원 배열이 필요하면 O(N^2), 따로 배열이 필요없으면 O(1)임.

 

문제 풀 때 기억하면 좋은 것

512MB = 1.2억 개의 int이다.

(메모리 제한이 512MB일 때, int변수를 대략 1.2억 개 정도 선언할 수 있음→ int 1개가 4바이트인 것을 이용해서 계산 가능)