바킹독님의 실전알고리즘 배우기 1강 듣고 요약

바킹독의 실전 알고리즘 1강 링크

시간 복잡도

문제에 따른 허용 시간 복잡도 짐작하기

공간 복잡도

메모리의 크기가 512MB라면 1.2억개의 int 변수를 선언할 수 있다는 것 기억하기(int 1개가 4byte)

정수 자료형

char 자료형의 범위: -128~ 127(1byte=8bit)

int 자료형의 범위: 21억(4byte=32bit)

1번은 integer overflow로 127 이후-127이 되어 무한루프에 빠지고,
3번은 10^10이 100억이므로 21억을 넘어 integer overflow.
해결을 위해서는 long long을 사용한다.(900경)
unsinged long long은 1800경
이를 넘어서는 수는 string을 이용해 저장한다.(근데 그러면 python 쓰는게 더 쉽다)

실수 자료형

실수 자료형의 저장 원리


실수의 연산 과정에서 ‘반드시’ 오차가 발생한다.
따라서 오차를 최소화하기 위해 실수에는 float 대신 double 자료형을 쓰면 오차가 10^-15 이하인 것을 보장할 수 있다.
그리고 실수 자료형을 써야하는 문제의 경우에는 위처럼 절대/상대 오차를 허용한다는 단서를 준다.(단서를 안 줄 경우 정수 자료형으로 해결 가능)


double에 long long 자료형을 함부로 담으면 안된다.
double은 유효숫자가 15자리인데, long long은 19자리이기 때문이다.(int는 double에 담아도 된다)


실수가 같은지 비교하고자 한다면 위 코드처럼 오차가 1-e12 이하면 같다고 보면 된다.