시간 제한 vs 메모리 제한

알고리즘 문제에서는 항상 이 2가지 제한이 걸려있고 그 제한내에 문제를 해결하는 것이 중요하다.

즉 알고리즘을 짤 때 이 2가지 제한에 대한 감을 미리 잡는것이 중요하다. 

1. 시간 제한

시간 제한에서는 연산을 10^8번 정도 해야 1초가 걸린다는 사실을 알고 있으면 된다. 연산을 몇 번 실행하게 될지 어림짐작으로 계산하여 시간제한을 잘 지킬 수 있는지 미리 생각하고 그에 맞게 여러 생각을 해보는 것이 중요하다. 그 연산을 실행하게 될 때 시간복잡도를 O(n)에대한식)으로 계산해보고 이를 이용하여 시간을 예측해보는것도 좋은 방법이다.

예를 들어 O(n^2)이면 n이 10^4보다 작아야 되겠다 하며 생각하는거고

O(n^3) -> n<500

O(n^4) -> n<100

처럼 대강의 계산을 해보며 감을 잡는 것이 중요하다.

참고로 for문 안에 아무것도 없으면 컴파일에서 자동으로 그 for문은 건너뛰고 실행하기 때문에 그 for문에서는 시간을 사용하지 않는다.

이러한 계산을 나중에 포스팅할 정렬의 여러가지 종류에 대해서 직접 계산해보았다. 참고.

2. 메모리제한

메모리 제한에서는 내가 얼마나 메모리를 사용하는지에 대한 문제인데 이미 정리했던것처럼 int나 longlong이나 char등 각 변수형에 따른 차지하는 메모리를 먼저 알아야 한다. 또한 단위는 다음과 같이 호환된다.

1byte=8bit/1024byte=1kb/1024kb=1mb

이것을 이용하여 계산해보면 만약 문제에서 80mb제한을 걸었다면

그말인 즉슨 80*1000*1000 byte인셈인데 int하나당 4 byte임을 알고 있으니 그말은 2*10^7개의 int형 메모리를 사용할수있다는 이야기이다. 즉 int로 정의하는게 2*10&7개 쓰면 메모리 제한을 다쓰는 셈이다. 앞으로 문제를 풀 때 이정도까지는 알고 푼다면 더욱 좋을 것이다.

이 메모리관련하여 더 알아두면 좋을 점이 있는데 프로그램에서 메모리를 할당해주는 공간이 크게 3가지가 있다. 스택(Stack)영역, 힙(Heap)역역 그리고 데이터(Data)영역 이다.

프로그램이 실행될 때마다 메인 메모리에 할당이 되는데 위의 3가지에 따라 어떤것들이 할당되는지 다르다.

- 데이터영역

main밖에서 정의된 전역변수들이 할당되는 곳

-스택영역

정의된 함수나 main함수 내부에서 사용하는 변수들이 할당되는 곳(지역변수, 매개변수)

스택영역의 메모리는 컴파일 타임에 크기를 미리 결정하여 메모리를 할당해놓는다

-힙영역

malloc을 사용할 때 처럼 필요에 의해 동적으로 메모리를 할당할 때 사용하는 메모리 할당 위치

힙영역의 메모리는 런 타임에 크기를 결정하여 메모리를 할당한다

즉 할당해야 할 메모리의 크기를 프로그램이 실행되는 동안 결정해야 하는 경우 유용하게 사용되는 할당 공간이다.