입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관관계
주어직 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
문제에서 주어지는 시간 제한은 대부분 1초에서 5초.
👉🏻 입력의 범위를 보고 요구하는 시간복잡도가 어느정도인지 알 수 있다
- N ≤ 11 ⇒ O(N!)
- N ≤ 25 ⇒ O(2^N)
- N ≤ 100 ⇒ O(N^4)
- N ≤ 500 ⇒ O(N^3)
- N ≤ 3000 ⇒ O(N^2*lgN)
- N ≤ 5000 ⇒ O(N^2)
- N ≤ 1000000 ⇒ O(N*lgN)
- N ≤ 10000000 ⇒ O(N)
- 그이상 ⇒ O(lgN), O(1)
입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
512MB = 1.2억개의 int
512MB / 4Bytes = 1.2억
이걸 기억해두면 만약 떠올린 풀이가 크기가 5억인 배열을 필요로 할 때 해당 풀이는 주어진 메모리 제한을 만족하지 못하므로 틀린 풀이라는 것을 빠르게 깨닫고 다른 풀이를 고민할 수 있습니다. 실컷 다 짠 후에야 알아차리면 너무 억울합니다.
short 2 byte
int 4 byte
long long 8 byte
short는 딱히 쓸 일이 없고 정수를 표현할 때 주로 int나 long long을 쓰는데, int가 long long보다 연산 속도와 메모리 모두 우수하지만 80번째 피보나치 수를 구하는 문제와 같이 int 자료형이 표현할 수 있는 범위를 넘어서는 수를 저장해야 하면 반드시 long long 자료형을 사용해야 합니다.
Integer Overflow를 막는 방법은 아주 쉽습니다. 각 자료형의 범위에 맞는 값을 가지게끔 연산을 시키면 됩니다. 하지만 실제 코드를 짜다보면 Integer Overflow는 아주 빈번하게 일어나고, 또 찾기도 정말 힘듭니다.
void func1() {
for(char s = 0; s < 128; s++) { // s = 127 다음에 s는 -128이 된다.
cout << "hi";
}
}⇒ s = 127 다음에 s는 -128이 된다. 이를 해결하려면 s의 자료형을 int로 바꾸면 된다.
void func2() {
int r = 1;
for(int i = 1; i <= 50; i++) {
r = r * i % 61;
}
return r;
}⇒ ㄱㅊ
int func3() {
int a = 1;
int mod = 1000000007;
for(int i = 0; i < 10; i++) {
a = 10 * a % mod;
}
}⇒ a가 10^9 일때 문제가 된다. int 자료형의 범위를 벗어나기 때문이다.
앞으로도 머리로는 Integer Overflow를 익혔지만 분명 실제로 문제를 풀 때 이 실수를 여러 번 저지르게 될 것입니다. 왜 이걸 확신할 수 있냐면 당장 저도 잊을만하면 한 번씩 저지르기 때문입니다. 그래도 이 실수로 시간을 엄청 버리고 나면 그 다음엔 실수를 덜하게 될 것입니다.
좋은 코딩 습관은 아니긴 한데, 이런거 저런거 다 신경쓰기 싫다 하면 아예 int를 쓰지 않고 전부 long long을 쓰는 것도 하나의 방법이긴 합니다. 만약 문제에서 unsigned long long 범위를 넘어서는 수를 저장할 것을 요구한다면 string을 활용해서 저장해야 합니다. 그리고 그 수로 연산을 해야 하는 문제는 코딩테스트에 안나오는게 정상이긴 한데, 만에 하나 나왔다 치면 그냥 Python을 쓰는게 C++로 꾸역꾸역 구현하는 것 보다 훨씬 편합니다.
컴퓨터는 실수를 저장할 때 소수점 이하는 2의 음수 거듭제곱을 이용한다.
한편, 10진수의 모한소수와 같이 2진수에서도 무한 소수가 나타난다. ex) 1/3
10진수의 과학적표기법처럼 2진수도 이런식으로 나타낼 수 있당.
11101.001(2) = 1.1101001(2) × 2^4
실수를 나타낼 때, 칸은 sign-exponent-fraction field로 나뉜다.
-
sign field: 양수인지 음수인지 저장하는 필드
-
exponent field: 과학적 표기법에서의 지수를 저장하는 필드
-
음수 지수승을 표현하기 위해서 127을 더해 저장한다. (float. double은 11칸이므로 1023을 더한다.)
$$ -1.1011_{(2)}×2^2 $$ 의 exponent field는 127 + 2 = 129 이므로 10000001 이 저장된다.
-
-
fraction filed: 유효숫자 부분을 저장하는 필드
float과 double은 이 field들의 길이에 차이가 있는 것이다. float은 1, 8, 23 bit이고 double은 1, 11, 52 bit이다.
실수의 저장과 연산과정에서는 반드시 오차가 발생할 수 밖에 없다.
자. 그러면 float, double 이 자료형들이 어디까지 정확하게 표현할 수 있는지 보면 float은 유효숫자가 6자리(128의 이진수), double은 15자리(1024의 이진수)다.
이말은 곧
float은 상대 오차
$10^{-6}$ 까지 안전하고, double은$10^{-15}$ 까지 안전하다는 말. 여기서 상대옹차가$10^{-15}$ 까지 안전하다는 표현은, 참값이 1일때 1-$10^{-15}$ 부터 1+$10^{-15}$ 까지의 값을 가지는 것이 보장된다는 의미
float과 double의 오차 허용범위의 차이가 크기 때문에, 되도록이면 연산할 때 double을 사용하는 것이 정확도를 보장하는 방법이다.
강의하시는 분은 지금까지 메모리 문제든 뭐든, double 대신 float을 써야하는 상황은 겪어보지 못했다고 하니 되도록이면 float을 쓰자.
실수를 사용하는 문제는 절대오차/상대오차를 허용한다는 단서를 준다. 그런 표현이 없다면 모든 연산을 정수로 해결할 수 있다는 의미로 해석할수있다는 것을 알 수 있어야한다.
int는 최대 21억이라 double에 저장해도 오차 X.
그러나 longlong은 최대 19자리. double은 유효숫자 저장을 15자리까지밖에 하지 못하니 오차가 섞인 값이 저장될 수 있다.
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";
}예제를 실행해보면 a 와 b를 등호로 비교시 같지 않다는 결과가 나온다. 오차때문에 그런것인데, 두 실수가 같은지 알고싶을 때는 둘의 차가