자료형 범위
int / 4바이트 / –2,147,483,648 ~ 2,147,483,647(20억)
=> 1,000,000,000까지의 수 범위를 담을 수 있음.
long long / 8바이트 / –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
=> 1,000,000,000,000,000,000까지의 수 범위를 담을 수 있음
=> 보통 합을 답는 변수는 long long으로 선언할 것.
그 밖에 실수형
float / 4 / -3.4 10^38 ~ 3.4 10^38
double / 8 / -1.7 10^308 ~ 1.7 10^308
코테 시간복잡도
source: https://dkanxmstmdgml.tistory.com/12
(시간 제한 1초)
- N의 범위가 500인 경우 -> 시간 복잡도 O(N^3)인 알고리즘 필요
- N의 범위가 2,000인 경우 -> 시간 복잡도 O(N^2) ""
- N의 범위가 100,000인 경우 -> 시간 복잡도 O(NlogN) ""
- N의 범위가 10,000,000인 경우 -> 시간 복잡도 O(N) ""
source: 이것이 코딩 테스트다 / 나동빈 / 한빛미디어
시간 복잡도 vs 공간 복잡도
(코딩 테스트 문제 조건 예시)
'시간 제한 1초, 메모리 제한 128MB'
-> 시간 제한은 시간 복잡도를 고려하라는 의미
-> 메모리 제한은 공간 복잡도를 고려하라는 의미
- 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미. 달리 표현하자면 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미. 달리 표현하자면 알고리즘을 위해 필요한 메모리의 양
보통 시간 복잡도와 공간 복잡도는 일종의 Trade-off 관계이다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도(시간 복잡도)를 줄일 수 있다. 대표적으로 다이내믹 프로그래밍의 '메모제이션(memozation)' 기법을 들 수 있다.
int arr[1000]; // 4KB int arr[1000000]; // 4MB int arr[2000][2000]; // 16MB코딩 테스트에서 보통 메모리 사용량을 128~512MB 정도로 제한. 데이터 갯수가 1,000만(10,000,000) 단위를 넘어가면 알고리즘 설계가 잘못된 것이 아닌지 의심 필요
