알고리즘 문제 풀 때 시간,공간복잡도 및 Integer overflow 문제

시간복잡도

주어진 입력 N의 허용 시간복잡도

 

공간복잡도

• 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

예를 들어 크기 N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1)이 된다.
하지만 코딩테스트에서 대부분의 경우 공간복잡도의 문제보다는 시간복잡도 때문에 문제를 많이 틀린다.
그러므로 공간복잡도는 크게 신경쓰지 않아도 된다.

 

But!! 이거 하나만 기억해두자 
☞ 메모리 제한이 512MB일 때 1.2억개의 int를 사용할 수 있다는 것

 

 

Integer Overflow

 

Integer Overflow가 발생하는 경우

#include<iostream>
using namespace std;

int main(){
    int a = 2000000000 * 2;
    cout << a; // -294967296
}

약 21억정도 까지만 표현할 수 있으므로 40억이라는 값은 a에 저장이 안 된다.
하지만 -294967296 같은 이상한 값은 어떻게 해서 나오게 된 것일까?

 

☞ 이유 : 컴퓨터는 그냥 시킨대로만 계산을 하기 때문이다.

 

integer overflow를 막는 방법은 각 자리에 맞는 값을 가지게끔 연산을 시키면 된다. 하지만 실제로 코드를
짜 보면 integer overflow는 아주 빈번하고 찾기도 정말 힘들다.

 

 

실수를 이진수로 표현하는 방법 

3을 이진수로 나타내면 11(₂) 이다. 이렇게 정수를 이진수로 바꾸는 방식을 실수에도 적용하여 실수를 이진수로 바꿀 수있다.

 

실수의 이진수 표현

예를 들어 3.75를 이진수로 나타내고 싶다. 어떻게 해야 할까?

3.75  =  2  +   1   +   0.5   +  0.25  =  2^1 + 2^0 + 2^(-1) + 2^(-2) = 11.11(₂) 
위와 같이 바꿀 수 있다. 즉, 실수는 이진수로 바꿀 때 0.5, 0.25, 0.125. . . 등의 합으로 나타낸다.

 

이진수에서도 무한소수가 나타난다.
⅓ = 2^(-2) + 2^(-4) + 2^(-6). . . = 0.010101. . .(₂) 이런식으로 끝없이 이어지는 무한소수가 발생한다.

0.1도 0.5, 0.25, 0.125. . . 등을 아무리 조합해봐야 나오지 않기 때문에 무한소수로써 끝없이 이어진다.

 

 

실수가 저장되는 방식

 

우선 이걸 확인하고 가자.

3561.234 = 3.561234 x 10³ 로 바꿀 수 있듯이
11101.001(₂) = 1.1101001(₂) x 2⁴ 로 바꿀 수 있다.

 

실수는 float와 double에 담을 수 있다. float는 32비트, double은 64비트이다.

-6.75 = -1.1011(₂) x 2² 
위 실수를 저장해보자.

sign field

• 해당 수가 음수인지 양수인지 저장하는 필드 ( 음수면 1, 양수면 0 )

exponent field

• 과학적 표기법에서의 지수를 저장하는 필드 ( 2²가 뒤에 붙었으므로 이 필드에는 2가 저장됨)
• 지수값을 그대로 넣는 것이 아닌 지수값 2에 127을 더한 값을 여기에 저장한다.
  127을 더하는 이유는?  이렇게 해야 음수 지수승도 exponent 필드 안에 넣을 수 있기 때문 

fraction field

• 유효숫자 부분을 저장하는 필드
• -1.1011(₂) x 2²에서 유효숫자 부분은 1.1011인데 맨 앞 1은 뺀 1011이 여기에 저장된다.
  맨 왼쪽부터 2^(-1), 2^(-2) . . . 자리인 셈이라 필드에는 1011000. . . 000이 적힌다.
  ☞ 즉, 맨 왼쪽부터 비트를 채운다.

이런 식으로 실수를 저장하는 방식을 IEEE-754 format이라고 한다.

 

 

실수의 성질

1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.

#include<iostream>
using namespace std;

int main(){
    if(0.1 + 0.1 + 0.1 == 0.3){
    	cout << "true";
    }
    else{
    	cout << "no no";
    }
}

실행 결과 : no no 

 

true가 아닌 no no가 출력된 이유는?

• 유효숫자가 들어가는 fraction field는 유한하기 때문에 어쩔 수 없이 float는 앞 23bit, double은 앞 52bit까지만
  잘라서 저장할 수 밖에 없다. 0.1은 이진수로 나타내면 무한소수라서 애초에 오차가 있는 채로 저장이 됐고
  오차가 있는 상태로 3번 더하다 보니 오차가 더 커져서 위의 코드처럼 말도 안되는 일이 벌어지게 된 것이다.

float과 double의 fraction field의 유효숫자의 안전한 범위

float    : 유효숫자 6자리    =>  상대오차 10^(-6)까지 안전
double : 유효숫자 15자리  =>  상대오차 10^(-15)까지 안전

 

그렇기 때문에 실수 자료형이 필요하면 float 대신 double을 쓰자!!

 

2. double에 long long 범위의 정수를 함부로 담으면 안 된다.

- double은 유효숫자가 15자리인데 long long은 최대 19자리라서 10^18 + 1과 10^18을 구분 못하고
  같은 값이 저장된다. 
- int는 약 21억까지 저장하기 때문에 double에 담아도 오차가 발생하지 않는다.

 

3. 실수를 비교할 때는 등호를 사용하면 안 된다.
위에서 0.1 + 0.1 + 0.1 == 0.3의 결과가 이상하게 나오는 것에서 보면 알 수 있다.