[바킹독의 실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

1. 시간 / 공간복잡도

 

- 시간복잡도(Time Complexity)

 

입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

 

- 빅오표기법(Big-O Notation)

 

주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

보통 시간복잡도를 표기할 때 빅오표기법을 이용

ex) O(N) : 5n+3, 2n+10logN, 10N

 

시간복잡도를 그래프로 나타내었을 때

 

출처: 바킹독님 블로그

 

우리가 유념해야 할 점!

무작정 코드를 짜지 않고, 문제를 제한 시간 내에 통과할 수 있는지 생각해봐야함

 

- 공간복잡도

 

코테 때 크게 신경쓰지 않아도 괜찮은 부분이긴 함!

512MB = 1.2억개의 int (int 하나가 4바이트니깐) 인 정도만 기억해도 좋음:)

 

2. 정수 자료형

 

 

short는 딱히 쓸 필요가 없음!

int 자료형이 속도나 메모리 활용도 면에서 가장 우수하지만 int 범위를 넘어가는 문제가 나온다면 long long을 활용해줘야함 (>> Integer Overflow 방지!)

 

 

- Integer Overflow 발생 예시

 

s가 128이 되는 순간 오버플로우 발생해 -128이 되어버림! char 형태를 int 형으로 바꿔주면 해결 가능

a가 10^9일때 2를 곱하면 int의 최대 범위를 넘어 오버플로우 발생함. 이를 방지하기 위해서는 long long으로 a의 자료형을 변경하거나, 7번째 줄에서 10ll or (long long)10으로 강제 형변환을 시키면 해결 가능!

 

3. 실수 자료형

 

- Floating point number(부동소수점)

 

실수를 2진수로 표현하는 방법! float와 double 둘의 변환 방식에 살짝 차이가 있음.

 

sign 필드는 해당 수의 부호를 판단하는 부분임. 1이면 음수, 0이면 양수를 의미

exponent field는 지수를 저장하는 필드로, float일때는 127를 더하고 double일 때는 1023(11칸)을 더해줌

fraction field의 경우 소수점 자리에 위치한 부분을 순차적으로 적어줌. 왼쪽자리부터 2^(-1), 2^(-2) ... 순으로 진행됨

 

 

- 실수의 특징 😎 기억합시다!

 

1) 실수의 저장/연산 과정에서는 반드시 오차가 발생함

 

아래 예시를 보자.

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

/***result***
no no...
*******/

위 예시를 본다면 당연히 true가 나와야 할 것 같지만, 실상 실행을 해보면 no no가 나오는 것을 볼 수 있음. 이는 실수형이 2진수로 변환이 되는 과정에서 오차가 발생하기 때문임.

유효숫자가 들어가는 fraction field 부분은 유한하기 때문에 2진수 기준으로 무한소수를 저장하려고 할 때 float는 23bit, double은 52bit만 잘라서 저장함. 예시의 0.1을 2진수로 나타내면 무한소수이기에 오차가 있는채로 저장이 되고, 결과적으로 no no가 출력된 것. 

 

추가적으로 float는 상대 오차 10^(-6)까지 안전하고, double은 10^(-15)까지 안전함(±10^(-15) 오차 범위 갖는다는 뜻)

 

float 대신 double을 쓰자. float는 메모리 이점이 있지만 별로임..

 

2) double에 long long 범위의 정수를 함부로 담으면 안됨

 

double은 유효숫자가 15자리이지만, long long은 최대 19자리이기 때문에 double에 long long 범위의 정수를 담을 경우 오차 발생 가능

 

3) 실수를 비교할 때는 등호를 사용하면 안됨

 

등호 대신에 범위로 표현하는 게 굿!

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)를 표현한 값. 10^9은 1e9*/
}

/***result***
same 2
******/