백준 시간제한과 메모리제한
Updated:
시간 제한
-
1초 : 약 3~5억번의 연산 가능
-
시간복잡도는 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미한다. 시간복잡도를 구하는 이유는 시간초과 여부를 확인하기 위해서이다.
그래프를 보면 N이 커짐에 따라 시간복잡도의 차이가 수행시간에 아주 큰 영향을 주는 것을 알 수 있다. O(1)은 상수시간, O(lgN) 은 로그시간, O(N)은 선형시간, O(NlgN)이나 O(N^2)처럼 N의 곱셈의 형식으로 표현되는 건 다항시간, O(2^N)은 지수시간, O(N!)은 팩토리얼시간이다. N이 25 이하가 아니라면 지수시간은 시간초과를 통과하기 어렵다. N이 11 이하가 아니라면 팩토리얼도 시간초과를 통과하기 어렵다. N의 크기에 따른 시간복잡도를 표로 대략적으로 나타내면 아래와 같다.
-
알고리즘을 코드로 구현하기 전에 미리 시간복잡도를 알아내서 코드로 구현할 가치가 있는 코드인지를 확인하는 게 중요하다.
-
예시
n이 1000인 경우 시간복잡도를 구했는데 O(n^3)이 나왔다. (10억) -> 시간 초과 발생
n이 100인데 시간복잡도를 구했는데 O(n^4)가 나왔다. (1억) -> 통과할 것 같지만 이 경우도 시간 초과가 발생한다. 왜냐하면 O(n^4)는 시간복잡도이지 연산의 수가 아니기 때문이다. 여기서 말하는 연산은 어셈블리 단계에서 instruction 개수를 말한다.
시간복잡도가 1000만이 나온 경우에도 될까 말까 하다. 대회마다, 컴퓨터마다 또 다르기 때문에 확실하지 않다. 이런 경우에는 cout 대신 printf 쓰는 방식으로 바꾸면 되기도 한다(instruction 개수도 차이가 나고 출력함수끼리의 동기화 설정 때문에 느려지는 부분도 있다. cin 과 scanf도 마찬가지이다). 시간복잡도가 1000만이면 코드를 구현하는게 리스크일 수도 있다.
컴공에선 로그는 거의 밑이 2이기 때문에 시간복잡도 계산 시 log1000은 10, log2000은 11, log1000000은 20이다.
메모리 제한
-
공간복잡도는 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계를 의미한다.
-
N짜리 2차원배열은 O(N^2), 배열이 없다면 O(N)이라고 보면 된다.
-
보통 데이터 영역이 스택 영역보다 더 크기 때문에 큰 배열은 전역변수에 선언을 한다. 스택 영역에 큰 배열을 저장하는 경우 메모리 초과가 나는 경우가 있다.
-
메모리는 직접 계산해보면 된다. 512MB의 경우 1.2억개의 int가 들어간다. 보통 100MB 이상이 주어지면 메모리를 신경 쓰지 않아도 되는 수준이다. 하지만 2MB처럼 메모리가 적게 주어지는 경우 메모리 최적화를 해줘야 한다. 2MB를 int로 나누면 50만 정도 밖에 못쓰기 때문에 스택 내에 배열을 쓰는 것도 신경 써줘야 한다.
자료형
정수 자료형
- char : 1byte = 8bit
- short : 2byte (2^15-1 = 32727)
- int : 4 byte (2^31-1 = 약 2.1*10^9) // long long보단 연산 빠르지만 용량 적음
- long long : 8byte (2^63-1 = 약 9.2*10^18) // int보다 느리지만 용량 큼
실수 자료형
-
float : 4byte
-
double : 8byte
-
실수 자료형 특징 :
-
실수는 저장과 연산 과정에서 반드시 오차가 발생한다.
- float : 유효숫자 6자리
- double : 유효숫자 15자리
- 보통 실수 자료형을 쓸 일이 있으면 double이 좋다.
-
double에 long long 범위의 정수를 함부로 담으면 안된다(int는 가능하다).
- long long은 유효숫자가 19자리이기 때문에 유효숫자가 15자리인 double에 들어가면 값이 짤려서 들어간다.
-
실수를 비교할 때는 등호를 사용하면 안된다.
int main(void) { double a = 0.1 + 0.1 + 0.1; double b = 0.3; if(a==b) cout << "same 1\n"; if(abs(a-b) < 1e-12) cout << "same 2\n"; // 1e-12 == 10^-12 / 1e9 == 10^9 } /**** result **** same 2 *****************/
-
Leave a comment