바킹독 0x01강 요약 : 기초 코드 작성 요령 1
<시간, 공간복잡도>
시간복잡도 : 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계
빅오표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
- 상수시간인 O(1)이 가장 좋고 그 다음으로는 로그시간 O(logN), 선형시간 O(N), 다항시간 O(NlogN), 다항시간 O(N^2), 지수시간 O(2^N), 팩토리얼 O(N!) 순으로 시간복잡도가 커짐
공간복잡도 : 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
* 메모리 제한이 512MB일 때 int 변수를 대략 1.2억 개 정도 선언할 수 있음을 알아두기
(int는 4바이트)
<정수 자료형>
char 자료형은 1바이트(=8비트)
4가지 정수 자료형
- char (1바이트) 최댓값은 128
- short (2바이트) 최댓값은 32767, 많이 안 씀
- int (4바이트) 최댓값은 2.1 * 10^9 (약 21억), 연산속도와 메모리 우수
- longlong (8바이트) 최댓값은 9.2 * 10^18, 하지만 범위가 넓을 땐 longlong 쓰기
<Integer Overflow>
결과는 다르게 나왔지만 컴퓨터는 명령받은 대로 이진수 계산을 한 거임
오버플로우를 막는 방법 = 각 자료형의 범위에 맞는 값을 가지게끔 코드 짜기
만약 문제에서 unsigned longlong 범위를 넘어서는 수를 저장할 것을 요구한다면 string을 사용해서 저장해야하지만 꾸역꾸역 C/C++로 짜는 것보다는 파이썬으로 구현하는 게 훨씬 나음
<실수 자료형>
- float (4바이트)
- double (8바이트)
* 실수의 성질!!
1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수밖에 없음
float은 오차 10^-6까지 안전(유효숫자 6), double은 오차 10^-15까지 안전(유효숫자 15)
이 말은 즉슨, 참값이 1이라고 할 때 1 - 10^(-15)에서 1 + 10^(-15) 사이의 값을 가진다는 뜻
두 자료형의 차이가 굉장히 크므로 실수 자료형이 필요하면 꼭 float 대신 double을 써야함
2. double에 longlong 범위의 정수를 함부로 담으면 안됨
double에 longlong 범위의 정수를 담으면 오차가 섞인 값이 저장될 수 있음
double은 유효숫자가 15자리인데 longlong은 유효숫자가 최대 19자리니까 double은 10^18 + 1과 10^18를 구분할 수가 없어서 같은 값이 저장
다만, int는 최대 21억이므로 double에 담아도 오차가 생기지 않음
3. 실수를 비교할 때는 등호를 사용하면 안 됨
참고로 1e-12는 10^(-12)와 같은 말