[TIL]기초 코드 작성 요령 1

개요

코딩 테스트를 위해서 기본적으로 알고 있어야하는 내용을 정리한다. 꼭 필요한 기초이지만 어려운 내용!!

 

시간 복잡도

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

컴퓨터는 1초에 3억 ~ 5억개의 연산을 처리할 수 있다.

연산이 단순한 연산(and, or, +, -)인지 복잡한 연산(*, /, 대입, 함수호출)인지에 따라 차이가 있을 수 있다.

시간 복잡도는 빅오표기법을 통해 계산한다.

빅오 표기법은 주어진 식을 값이 가장 큰 대표향만 남겨서 나타내는 법

• O(N) : 5n + 1, 10lgN + 10N
• O(N^2) : N^2 + 2n + 1
• O(1) : 4, 10, 100

빅오가 N이면 N번 연산한다고 생각한다.

 

공간 복잡도

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

코딩 테스트를 풀 때 많이 신경쓰지 않아도 되지만..

 

• 512MB = 1.2억개의 int 선언 가능

만 기억하자..!

 

정수 자료형

자료형	byte	최대값	최소값
char	1	127	-128
short	2	2^15 - 1	- 2^15
int	4	2^31 - 1	- 2^31
long long	8	2^63 - 1	- 2^63

 

Integer Overflow

자료형의 범위를 넘어가면 생기는 현상

int main(void) {
	int a = 2000000000 * 2; //20억 * 2
    cout << a;
}
//result -29424235

 

실수 자료형

자료형	byte	최대값	최소값
float	4	-	-
double	8	-	-

실수를 이진수로 나타내는 방법은

실수를 십진수로 표현하는 것과 비슷하다.

• 3561.234 = 3.561234 * 10^3
• 11101.001 = 1.1101001 * 2^4

여기서 1.1101001은 fraction, 2^4는 exponent에 저장된다.

정확히는 fraction에는 1. 부분은 제외한 1101001이 앞에서부터 저장된다.

정확히는 exponent에는 127 + 4가 저장된다.

 

실수는 오차가 생길 수 밖에 없다.

float은 10^6까지 표현가능하고 double은 10^15까지 표현가능하다.

따라서 float은 상대오차 10^6까지 안전하고 double은 10^15까지 안전하다.

무슨 뜻이지??? 

• 참값이 1이라고 할때 1- 10^6에서 1 + 10^6의 값을 가진다는게 보장된다.

따라서

• 오차가 훨씬 적은 double은 거의 무조건 사용한다.
• 문제 상의 오차 허용 단서를 보고 판단하자.

이외의 알아야할 점

1. double에 long long 범위의 정수를 함부로 담으면 안된다. -> int는 괜찮다.
2. 실수를 비교할 때는 등호를 사용하면 안된다. -> 대략 10^-12 이하면 동일하다고 처리 하는게 안전

if(abs(a - b) < 1e-12) cout << "same \n";