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

시간 / 공간 복잡도

시간 복잡도(Time Complexity)

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

빅오 표기법(Big-O Notation)

• 주어진 식을 값이 가장 큰 대표 항만 남겨서 나타내는 방법
• 시간 복잡도를 표기할 때 빅오 표기법의 형태로 나타낸다.

 

시간 복잡도 그래프

N이 점점 커짐에 따라 시간 복잡도의 차이가 수행 시간에 아주 큰 영향을 주고 있음을 볼 수 있다.

풀이가 제한 시간 내에 문제를 통과할 수 있는지, 내 알고리즘의 시간 복잡도가 올바른지를 생각할 것!

 

 

공간 복잡도(Space Complexity)

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

코딩 테스트에서 공간 복잡도 보다는 시간 복잡도 때문에 문제를 많이 틀리게 되므로,

공간 복잡도 보다는 시간 복잡도에 신경 쓸 것.

메모리 제한이 512MB일 때 int 변수를 대략 1.2억 개 정도 선언할 수 있다는 것을 기억해 두면 좋다.

 

정수 자료형

정수를 표현할 때 주로 int나 long long을 사용한다.
int가 long long보다 연산 속와 메모리 모두 우수하지만, int 자료형이 표현할 수 있는 범위를 넘어서는 수를 저장해야 하면 반드시 long long을 사용해야 한다.

 

Integer Overflow

char은 8바이트로, -128~127을 표시할 수 있다.

s가 127이 된 후에 1을 더하게 되면 -128이 되어 무한 루프에 빠지게 된다.

s의 자료형을 int로 바꾸어 해결할 수 있다.

 

a가 10^9일 때 10이 곱해지는 순간 int의 최대 범위를 넘어서게 되어 Integer Overflow가 발생한다.

a의 자료형을 long long으로 바꾸거나, 7번 줄에서 10 대신 10ll 혹은 (long long)10으로 강제 형변환을 하여 해결할 수 있다.

 

실수 자료형

실수를 표기할 때, sign, exponent, fraction field로 나누어진다.

sign field는 해당 수가 음수인지 양수인지를 저장하는 필드이다.

exponent field는 과학적 표기법에서의 지수를 저장하는 필드이다.

fraction field는 유효 숫자 부분을 저장하는 필드이다.

 

실수의 성질

1. 실수의 저장과 연산 과정에서 반드시 오차가 발생할 수밖에 없다.
2. double에 long long 범위의 정수를 함부로 담으면 안 된다.
3. 실수를 비교할 때는 등호를 사용하면 안 된다.

 

 

출처: 바킹독님 블로그