공간복잡도

---

• 입력 크기에 대해 어떤 알고리즘이 실행되는데 필요한 메모리 공간의 양

• 정적변수 뿐만 아니라 동적으로 재귀함수로 인해 공간을 계속 필요로 할 때도 포함이고 배열이든 맵이든 셋이든 공간이면 다 !!

ex. 입력이 N, 자료형이 int
-> 4N => O(N)

but,

문제를 푸는데는 잘 사용되지 않는다.
배열의 범위 등을 잡을 때는 2가지 방법을 기반으로 잡는다.

1. 최대범위

1 < N < 1000000000

-> int N[1000000000] 이런식으로 선언해놓기

2. 메모리 제한

512MB

-> 512,000,000 바이트

-> int a[128000000] 선언 가능

근데 메모리제한은 맨날 계산하기 좀 힘드니까

"1000만까진 ㄱㅊ" 이라고 생각하기

-> 메모리가 천만까지 필요하다? 로직에 뭔가 이상이 있는 건 아닌지..