바킹독 알고리즘 0x01강 기초 코드 작성 요령 1 요약본

시간, 공간 복잡도

먼저 시간 복잡도라 함은, 컴퓨터가 연산을 하는데 걸리는 대략적인 시간. 정확한 시간을 구하기 힘들기 때문에, Big O notation 을 이용하여 n 에 비례한다. lg n 에 비례한다. 등 그 식에서 가장 큰 값을 가지는 항에 비례한 시간이 걸린다고 생각. 

n 의 크기에 따른 허용 시간복잡도. 절대적인 것은 아니나, 이 정도 시간대로 처리하는 것이 유리하다는 느낌은 가지고 있어야 함. 

중요! 문제를 풀 때, 무턱대고 풀 게 아니라, 제한 시간내에 풀 수 있는 풀이인가? 를 생각해야 함.

다음으로 공간복잡도라 함은, 연산하는데 필요한 메모리 공간의 크기. 코테에서는 고려할 필요가 거의 없고, 메모리 제한이 512 MB 일 때 int 변수를 약 1.2억개 선언할 수 있다는 것을 알아두면 좋다고 함.

 

정수 자료형 (type) -> char 가 문자를 담는 자료형이라고알고 있었는데, 정수를 담는 자료형이라고 소개해서 혼란스러움..

여기서 알면 넘나 꿀인 부분은, signed 에서 나는 MSB 가 0이면 양수 1이면 음수라고 배우고 2's complement 이용해서 양수로 바꾼 다음에 - 부호 붙여주었는데, 그냥 -2^7 이라고 계산하면 더하기로 끝낼 수 있음..

디논설과 컴퓨터구조에서 주구장창 외웠었던,, floating point number 표기법.. 외우자. float 은 1 8 23 double 1 11 52 

exponent 는 지수를, fraction 은 유효숫자를 저장한다.

실수 자료형에서 꼭 기억해야 하는 실수의 특징!

1. 실수의 저장/연산 과정에서 반드시(100%) 오차가 발생한다.

0.0125 + ... 해서 0.1 을 만들 건데, 그 셋을 더해서 0.25 + ... 을 한 0.3 과 정확히 같은 수를 만들지는 못할 것. 다만, float 의 경우 그 오차가 +- 10^-6 범위 안이라는 거고 double 은 오차가 +-10^-15 범위 안이라는 것. double 을 쓰는 것이 좋다. 그리고 실수 자료형은 오차가 필연적으로 있으므로, 실수 자료형이 필요한 경우 문제에서

이런 워딩을 준다.

2. double 에 long long 범위의 정수를 담으면 안된다. int 는 최대가 21억이라 담는 것 가능.

3. 실수 비교시에는 등호를 사용하면 안된다.

1e-12 가 의미하는 게 10^-12. 1e9 가 10^9. 문데에서 주어지는 절대/상대 오차의 차수에 맞추어, 두 수의 차가 그 이하이면 같다고 정의해야 함. 즉 == 대신 - 를 사용해서 비교해야 함.