문제 풀이에서 1000000007, 1000000009으로 나누는 이유가 뭐지? (feat.모듈로 연산)

문제 풀이에서 1000000007, 1000000009으로 나누는 이유가 뭐지? (feat.모듈로 연산)

가끔 알고리즘 풀다보면 뭐 숫자를 몇으로 나눈 나머지를 써라~~ 이런 것들이 보인다.
아니 이거 왜씀? 하기도 하고, 결과에 나누라해서 진짜 결과에다가 나누면 제대로 안나온다... 이거 뭘까??

Integer, Long

int형식은 32비트로 표현되고 표현할 수 있는 범위는 -2147483648 ~ 2147483647 이다.
long형식은 64비트로 표현되고 표현할 수 있는 범위는 -9.22337204e18 ~ 9.22337204e18이다.

이게 가끔 문제에서 계산하다보면 저 이상의 숫자가 나오면 overflow가 나와버리는 것이다.

연산자 분배법칙

모듈러 연산은 주로 암호 알고리즘에서 사용된다.
일단 연산자 분배법칙에 대해 먼저 이야기하자면

(A+B)%M = ((A%M) + (B%M)) % M
(A*B)%M = ((A%M) * (B%M)) % M
(A-B)%M = ((A%M) - (B%M)) % M

요렇게 된다.
예를 들어서

(13+5)%8 = ((13%8) + (5%8)) % 8 -> 2

이렇게 된다.

그래서 이 분배법칙을 사용해서 어차피 같은 결과가 나오는데, 이를 작게 하기 위해 써주는 것이다.

왜 근데 1000000007, 1000000009이지...?

아까 위에서 본 int는 -2147483648 ~ 2147483647 의 범위를 가진다.
근데 이거를 또 맨날 나머지 연산을 하면 int의 표현을 최대한 활용하는게 힘들 것이다.
그래서 최대한 int의 max에 가깝도록 쓰는데, 그 중에서도 절반에 해당하는 소수값인(진짜 max에 가까우면 연산 도중에 overflow발생 가능!!) 1000000007 혹은 1000000009를 사용하는 것이다.

소수는 두가지 장점을 갖는데

• 연산의 정확도가 높다.
• 해당 모듈러 곱셈의 역을 구하는 것이 쉽다.

결론

알고리즘 풀이에서 1000000007, 1000000009등으로 나누는 이유는

• 연산자 분배법칙에 의해 mod 결과 같은 값을 도출해낸다.
• int의 max의 절반에 해당하기 때문에 stackoverflow 방지 가능
  • int의 범위를 최대한 활용하기 위해 max의 절반에 최대한 가까운 숫자들 사용
• 두 값은 소수이다.
  • 연산의 결과가 더 정확하다.
  • 역산을 구하기 쉬움