모듈러 연산(Modular Arithmetic)

코딩 문제 풀다가 계속 만나는 %연산

 => 큰 수를 다룰 때 오버플로우를 방지하거나, 값을 일정 범위 안에 유지하기 위해 사용함!

== 이걸  모듈러 연산(Modular Arithmetic) 이라고 한다!

1. 모듈러 연산?

모듈러 연산은 나머지를 구하는 연산 (=수학에서 나눗셈의 나머지)

예를 들어,

7 % 3 = 1  // 7을 3으로 나누면 나머지가 1

즉,   "어떤 수를 특정 값으로 나눈 뒤 나머지만 남기는 것"을 말함.

 

2. 사용 이유/목적

(1) 큰 수를 다룰 때

팩토리얼 같은 걸 계산하면 수가 엄청 커짐.

ex) 20!(20팩토리얼)은 2,432,902,008,176,640,000

컴퓨터가 이런 큰 수를 다루면 자료형 범위를 초과해서 오류가 나므로

이를 방지하고자 중간중간에 %를 씌워서 수를 작게 유지하는 방식 사용함.

const int MOD = 1000000007;

long long result = 1;
for (int i = 1; i <= 20; i++) {
    result = (result * i) % MOD;
}
cout << result;

 

(2) 값을 일정 범위 안에 유지하고 싶을 때

예를 들어, 시계가 12시간 단위로 돌아간다고 해보자.

지금 시간이 10시인데, 5시간 후는 몇 시일까?
10 + 5 = 15, 하지만 시계는 12를 넘어가면 다시 1로 돌아가야 함.
이때 15 % 12 = 3 → 3시가 된다.

 

3. 모듈러 연산의 핵심 성질

모듈러 연산은 덧셈, 뺄셈, 곱셈에서 안전하게 분배할 수 있음.
이게 알고리즘 문제에서 정말 많이 쓰이는 핵심!!!!

 

1) 덧셈

( a + b) mod m = ((a mod m) + (b mod m)) mod m

(5 + 9) % 7 = 14 % 7 = 0
(5 % 7 + 9 % 7) % 7 = (5 + 2) % 7 = 0

 

 

2) 곱셈

( a × b ) mod m = (( a mod m ) × ( b mod m )) mod m 

(5 * 9) % 7 = 45 % 7 = 3
(5 % 7 * 9 % 7) % 7 = (5 * 2) % 7 = 3

덧셈/곱셈은 OK → 값이 커져도 MOD 안에서 계산 가능

 

3) 뺄셈 

( a − b ) mod m = (( a mod m ) − ( b mod m ) + m ) mod m

음수가 되지 않게 +m 해주기!

(5 - 9) % 7 = -4 % 7 → 이걸 양수로 바꿔야 함
(-4 + 7) % 7 = 3

 

 

4) 나눗셈 ********

나눗셈은 조금 까다로워 주의가 필요함!

덧셈, 뺄셈, 곱셈은 쉽게 처리할 수 있지만, 나눗셈(/)은 그냥 쓰면 안 됨

예를 들어 10 / 4는 수학적으로는 2.5지만,
모듈러 연산에서는 **정확한 역원(곱했을 때 1이 되는 값)**을 찾아서 곱해줘야 해.

이때 자주 쓰이는 개념이 페르마의 소정리와 모듈러 역원임

 

4. 실제 예시: 큰 수의 조합 구하기

조합 공식 : nCr = n! / r! (n−r)!

근데 n!은 너무 커서 그냥 계산하면 바로 터져버림
그래서 팩토리얼을 미리 mod로 나눈 값을 저장해두고, 나눗셈 대신 역원을 곱해서 해결한다.

5. 정리 

조합 공식 : nCr = n! / r! (n−r)!

근데 n!은 너무 커서

연산	안전하게 모듈러 적용 가능?	비고
덧셈	✅ 가능	그대로 % 적용
뺄셈	✅ 가능	음수 방지를 위해 +m 필요
곱셈	✅ 가능	그대로 % 적용
나눗셈	❌ 불가능	역원 필요

 

• 모듈러 연산은 큰 수를 안전하게 다루기 위해 꼭 필요하다.
• 덧셈, 뺄셈, 곱셈은 자유롭게 % 적용 가능.
• 나눗셈은 조심! → 역원 개념이 필요하다.
• % 연산은 시계와 비슷하다고 생각하면 이해가 쉽다.

---

6. 나눗셈을 왜 그냥 나누면 안되는가에 대한 추가 정리 

예시

• a=3
• b=5
• M=7

원래 나눗셈: 3 / 5 (정수 나눗셈 불가!)

=> MOD 상황에서 처리하려면?

** 잘못된 방법

(3 mod 7) / (5 mod 7) = 3 / 5 = 0 (정수 나눗셈 → 틀림)

 

** 올바른 방법: 역원을 곱하기

MOD에서 나눗셈은 곱셈의 역원을 곱하는 것으로 처리

a / b mod  M = { a × b ^ (−1)} mod  M

b^(-1)이 b의 모듈러 역원.

 

 

b × b ^ (−1) mod  M = 1

---

그럼 이걸 어떻게 해야하는가??

• 곱셈 역원을 pow(거듭제곱)으로 구해야 함
• cut이 소수이므로 **페르마의 소정리(Fermat's Little Theorem)**를 사용해 쉽게 역원을 구할 수 있음!
• 페르마의 소정리는 나중에 다시 추가로 공부하기!