실수 연산 피하기

문제를 풀다보면 실수 연산을 해야 할 때가 있습니다. 하지만 실수 연산에는 실수 오차가 생겨 결과가 부정확 해질 수 있으며 정수 연산에 비하여 연산 횟수가 많음으로 가능하다면 피하는 것이 좋습니다.

1. double 대신 long long 쓰기
long long 는 -2^62 부터 2^62 - 1까지의 정수들을 저장 할 수 있는 타입입니다. 만약 계산과정이 모두 long long 범위 안에 있고 정수 연산만 필요한 경우 long long을 쓰는 것이 좋습니다.

2. 제곱근 비교
소수인지 판별하기 위하여 흔히 n을 2부터 sqrt(n)까지 나눠봅니다. 비교하는 양변이 모두 양수이므로 제곱하여 정수 연산만으로 i가 sqrt(n)보다 작거나 같은지 비교 할 수 있습니다.

for(int i=2; i<=sqrt(n); i++)

for(int i=2; i*i<=n; i++)

3. 분수 비교
A, B, C, D 모두 정수이고 A/B > C/D 인지를 판별하고자 한다면 다음과 같이 쓸 수 있습니다.

if(1.0*A/B > 1.0*C/D) 

if(A*D > C*B) 

4. 분수의 올림값 계산하기
A, B가 정수고 A/B의 올림값을 계산하고자 할 때 다음과 같이 쓸 수 있습니다.

int C = ceil(1.0*A/B)

int C = (A+B-1)/B