#3 1,000,000,007로 나누기

[백준 저지 11401번]
자연수 N과 정수 K가 주어졌을 때, 이항 계수를 구하고
그 수를 1,000,000,007 로 나눈 나머지를 구하시오

왜 알고리즘 문제에서는 1,000,000,007(1e9+7)로 나눈 나머지를 구하라고 할까요?

아무생각없이 ctrl c + v 하고 문제 풀은 사람 있나요?!

~~저요!!!!!~~

어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로,

나머지 연산(mod)이라고 한다.

Why 나눠야 할까?

python에서 쓰는 int 정수형의 경우 4바이트(32비트)로

-2^31에서 2^31-1까지 표현이 가능하다.

(-2,147,483,648 ~ 2,147,483,647)

이는 2e9로 근사할 수 있다.

하지만 이보다 훨씬 큰 값의 결과를 나타내고,

체크하기 위해서 모듈러 연산을 사용하는 것이다.

또한 계산해야할 수가 커지면 매 연산 시간이

그 자릿수에 비례하기 때문에 점점 오래 걸린다.

Why 1e9+7 일까?

물론 약 2e9의 값을 사용할 수도 있다. 하지만...!

덧셈 연산에서 2e9(2^31)에 근사하는 값들을 쓴다면

2e9+2e9 = 4e9가 되어 오버플로우가 발생한다.

그렇기에 1e9(2^30)에 근사하는 값을 가져야 하는데

결국 1e9에 가까운 값 중에 소수인 1e9+7을 사용하게 되었다.

Why 소수 일까?

소수를 쓰게 되면 문제 풀이의 정확도를 더욱 높일 수 있게 된다.

소수가 아니면 약수의 크기에 따라 모듈러 연산 결과가 겹칠 수 있기 때문이다.

또한, 이 수는 모양이 단순하여 암기가 편하다는 장점도 있다!

1,234,567,891

(이것도 역시 놀랍게도 소수다!!!)

1,000,000,009(소수) 로 나눈 나머지를 구하라고 하기도 한다.

- 출처 -