모듈러 연산 <정의>
모듈러(Modular) 연산은 정수의 나눗셈에서 나머지(modulo)를 계산하는 연산을 말한다.
n을 모듈러 연산 할 경우 나올 수 있는 수의 범위는 (0~n-1)이며
모듈러 연산은 보통 알고리즘 문제에서 매우 유용하게 사용된다.
특히, 큰 수의 곱셈, 제곱, 나눗셈 등의 연산에서 overflow나 underflow를 방지하고, 연산 결과의 범위를 소수의 범위 내로 제한하여 정확한 결과를 얻을 수 있도록 한다.
<왜? 사용하는가>
알고리즘 문제에서 큰 숫자를 다루는 과정 속에서 overflow나 underflow를 방지 하기 위해서 사용한다.
Java에서 int 형은 4바이트(32비트) 크기의 부호 있는 정수형 타입으로, 대략 -2,147,483,648(-2^31)부터 2,147,483,647(2^31-1)까지의 범위를 표현 할 수 있다.
만약에 연산 중에 매우 큰 값을 다루어서 해당 범위를 벗어난다면 값이 이상하게 찍히는 것을 볼 수 있는데 이것이
overflow나 underflow이다.
이러한 문제를 해결 하기 위해 long 형을 사용해 표현 범위를 넓힐 수 도 있지만 그것 마저 한계가 있기 때문에 나온 해결책이 모듈러 연산을 사용하자! 이다.
<대표적인 사용 숫자>
- 10의 9승 7(1,000,000,007) 10억+7
- 10의 9승 9(1,000,000,009) 10억+9
<왜 이 두 수를 사용하는가?>
- int의 max 값에 가까우면서 덧셈 뺄셈 연산이 가능하기 때문이다.
public class ProfitableSchemes {
public static void main(String[] args) {
int mod = 1000000007;
int a = 2000000000%mod; // 20억
int b = 2000000000%mod; // 20억
System.out.println((a+b)%mod); // 999999979
long c = 1000000006;
long d = 1000000006;
System.out.println(c*d); // 1000000012000000036
}
}
정수의 최대 범위는 앞서 언급했다 싶이 -21억~21억 이다.
위에 두 숫자의 모듈러 연산 결과의 최대값을 각각 더한다 해도 21억을 넘지 않기 때문에
덧셈 뺄셈을 표현하기 좋다. 그 밖에도
두 연산의 곱셈도 long 범위로 허용이 가능하다.
1000*1000*1000 + 7
1000*1000*1000 + 9
역원: A mod C의 모듈러 역원은 A*B mod C = 1을 만족 하는 B
예시: 3%7 일 경우의 역원 -> (3*5) % 7 == 1 따라서 역원은 5
역원을 구한다면 나눗셈 대신 곱셈을 이용한 연산이 가능하므로, 계산 속도를 높일 수 있는데
소수는 확장 유클리드 알고리즘(Extended Euclidean Algorithm)을 사용하여 역원을 구하기 쉽기 때문이다.