[도구정리] 1000000007, 1000000009의 의미는?

문제의식

 

코딩테스트 문제를 풀다 보면 백준, 프로그래머스, 소프티어 등등 어떤 사이트인지에 관계없이 1000000007, 1000000009라는 숫자를 접해본 적이 있을 것이다.

대부분의 풀이가 % 1000000007 인 모듈러 연산을 진행하여 dp 혹은 반복문을 통해 해결해 나갔다.

 

물론, 모듈러 연산을 한다는 것에서 대충 감은 온다. 하지만 왜? 1000000007일까? 하필?

---

검증 및 결론

 

실제 소수인지부터 검사를 해보자.

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    static boolean[] isPrime;

    static void isPrime_fun(int n){
        isPrime = new boolean[n+1]; // N번째의 수 까지 받기위해 N+1까지 동적할당

        for(int i = 0; i < isPrime.length; i++){
            isPrime[i] = true; // boolean배열의 default값은 false이므로 true로 바꿔주기
        }

        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아니니깐 false

        for(int i = 2; i <= Math.sqrt(n); i++){ // 2부터 n의 제곱근까지의 모든 수를 확인
            if(isPrime[i]){ // 해당수가 소수라면, 해당수를 제외한 배수들을 모두 false 처리하기
                for(int j = i*i; j<= n; j += i){//그 이하의 수는 모두 검사했으므로 i*i부터 시작
                    isPrime[j] = false;
                }
            }
        }
    } // isPrime_fun 함수 종료

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 소수인지 판별할 숫자 input

        isPrime_fun(N);
        System.out.println(isPrime[N]);
    }

}

 

에라토스테네스의 체를 이용하여 판별해 보면 실제 소수인 것을 알 수 있다.

 

첫 번째 결론은 1000000007, 1000000009는 소수이다.

 

---

Int의 범위

 

Int의 범위는 -2147483648 ~ 2147483647이다. 이 범위의 절반정도인 1000000007, 1000000009를 사용하는 것이 편하기 때문이다.

 

int의 범위 안에 있는 가장 큰 소수를 사용하는 것이 아닌 절반 범위인 소수를 사용하는 이유가 뭘까?

우리가 소수를 통해 모듈러 연산을 하여 문제를 진행하는 것이 후에 연산에 있어 overflow를 방지하는 것에 도움이 되기 때문이다.

 

https://softeer.ai/practice/6284 문제를 생각해 보자. 

이 경우 최대 10^(8+8*6)이라는 무자비한 숫자가 나올 수 있다.

그럼 long의 범위도 초과하니 BigInteger을 도입하여 해결할까? 그러지 말자는 것이다.

문제에서 출력은 1000000007로 나눈 값을 하라고 한다. 

-> 애초에 mod값을 가지고 진행하자!

 

이 문제의 경우 계속 곱해나가는 p가 매우 클 수 있기 때문에 정답을 추적하는 값의 자료형을 long으로 사용했었다.

하지만 정답을  int로 추적한다면 어떻게 될까?

-> int 범위의 제일 큰 소수로 진행하는 경우 아주 조금의 덧셈, 곱하기에서 오버플로우가 발생할 가능성이 있다.

-> 따라서 절반 범위의 값 정도인 1000000007, 1000000009를 사용하여 차후의 연산 오류를 줄이고자 하는 것이다

 

두 번째 결론 int 범위와 이후의 연산을 위한 값 선정이다.

---

최종 결론

 

1. 나눈 값을 출력하라고 한다면 dp 혹은 반복문일 가능성이 있다.

2. 이 경우 나누어가며 정답을 추적하자.

3. 자료형에 대한 힌트가 될 수도 있다. 모듈러 연산 후에 남는 값에 대해서 더하거나 곱하는 값을 보고 자료형을 선정할 수 있다.

4. 다른 소수에 대해서도 동일한 규칙을 적용할 수 있다.