[Modulo Operation/모듈로 연산] 알고리즘 문제에서 1,000,000,007의 의미는?

알고리즘 문제를 풀거나 코딩테스크를 응시하다보면 1,000,000,007로 나눈 나머지, 1,000,000,009로 나눈 나머지를 구하는 문제가 종종 보인다. 그렇다면 1,000,000,007가 가진 의미는 무엇일까?

 

◼ 모듈로 연산(Modulo Operation)이란?

• 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.
• 즉, 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다.

◼ 왜 나눌까? 왜 1,000,000,007 일까?

• int(정수형)의 경우 4바이트(32비트)로 -2,147,483,648 ~ 2,147,483,647의 범위를 가진다.
• 이것은 2e9(2*10^^9)의 근사치로 표현할 수 있고, 가끔 문제에서 계산하다 보면 저 범위 이상의 숫자가 나오면 overflow가 발생해버리게 된다.

➡ 만일 2e9에 근사한 값을 사용하면 overflow가 발생할 수 있다.(2e9 + 2e9 = 4e9)

그렇기 때문에 범위의 절반에 해당하는 값인 1e9(1*10^^9)에 가까운 값중 소수인 1,000,000,007 또는 1,000,000,009를 사용하는 것이다.

 

👉🏻결론: 알고리즘 문제에서 1,000,000,007로 나누는 이유

• 연산자 분배법칙에 의해 mod 결과 같은 값을 도출해 내기 위함
• int 범위의 절반에 해당하기 때문에 연산 과정에서 일어나는 overflow를 방지
• 소수를 사용하는 이유
  • 문제 풀이의 정확도를 더욱 높일 수 있음
  • 소수가 아닌 경우 약수의 크기에 따라 모듈러 연산 결과가 겹칠 수 있음

 

 

+ 지금까지 수많은 알고리즘 문제를 풀며 그냥 나누라니까 나누지 뭐...라며 스쳐갔던 과거가 부끄러워졌다.
나와 같이 작은 궁금증에서 시작해서 이 글을 보는 사람이 있다면 도움이 되었으면 좋겠다!