모듈러 연산 - 나머지 분배 법칙

알고리즘을 풀다보면 답을 출력할 때 ~수를 10,007로 나눈 나머지를 출력한다.처럼 어떠한 수로 나눈 나머지를 출력해야할 때가 있습니다. 이는 계산 결과가 너무 커지는 것을 방지하기 위함입니다.

이때 마지막에서만 해당 수로 나눠주면 메모리초과가 발생합니다 😭 따라서 계산 중간중간 미리 나머지 계산을 해두어 수가 너무 커지는 것을 방지해야합니다.

오늘은 어떤 원리로 나머지가 계산되는지 모듈러 연산의 나머지 분배 법칙에 대해 공부했습니다 😊

---

모듈러 연산

• 모듈러 연산 (Modular Arithmetic): 정수인 주어진 수를 특정 값으로 나눈 나머지를 구하는 연산
  -> 큰 숫자의 연산을 간단하게 할 수 있고, 계산의 오버플로우를 방지하기 때문에 알고리즘 효율성 올라감
  => a % b 표기법 사용 (a = 나눠지는 수, b = 나누는 수)

덧셈의 나머지 분배 법칙

(a + b) % c = ((a % c) + (b % c)) % c

ex) (7 + 9) % 5 = 1⠀ ↔️⠀ ((7 % 5) + (9 % 5)) % 5 = (2 + 4) % 5 = 1

뺄셈의 나머지 분배 법칙

(a - b) % c = ((a % c) - (b % c) + c) % c

=> (a % c) - (b % c)가 음수가 되지 않도록 뒤에 c를 더해줍니다 !

ex) (7 - 9) % 5 = 3⠀ ↔️⠀ ((7 % 5) - (9 % 5) + 5) % 5 = ((2 - 4) + 5) % 5 = 3

곱셈의 나머지 분배 법칙

(a * b) % c = ((a % c) * (b % c)) % c

ex) (7 * 9) % 5 = 3⠀ ↔️⠀ ((7 % 5) * (9 % 5)) % 5 = (2 * 4) % 5 = 3

멱승의 나머지 분배 법칙

(a ^ b) % c = ((a % c) ^ b) % c

ex) (7 ^ 9) % 5 = 40353607 % 5 = 2⠀ ↔️⠀ ((7 % 5) ^ 9) % 5 = 2 ^ 9 % 5 = 512 % 5 = 2