공간복잡도가 뭐임?

"입력 크기"에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 "양"을 의미한다.

정적변수 뿐만아니라 동적으로 재귀적인 함수로인해 공간을 계속해서 필요로할 경우도 포함됨.

배열이든 뭐든 공간 필요하면 다 포함됨.

ㅇㅎㅇㅎ.

팁 👍👍👍

문제의 최대 범위를 기반으로 잡는다.

그리고 위에서 처럼 메모리 제한을 참고를 한다.

512MB니까

1MB는 1024KB임 1KB는 1024Byte임

그러면 1024byte가 1024개가 있는거니까

1MB = 1,048,576byte임.

여기다가 * 512하면 512MB임.

설정하는 법❓

펜윅트리라는게 있는데 이게 탐색인데,

기존의 A라는 배열에서 탐색을 끝내고 B라는 같은 크기의 배열을 만드는 방법이다.

이분탐색은 그냥 A만 있으면 됨.

만약 배열의 크기가 1000만인 경우에

탐색을 한다고치면은 펜윅보다는 이분?(이진?)탐색을 사용해야함.