[알고리즘] 모듈러 연산(Modular arithmetic)

오늘은 코딩테스트를 풀며 알고리즘 공부를 하던 중 모듈러 연산이라는 신문물을 발견하게 되어 정리하고 넘어가보려한다. 모듈러 연산이란 뭘까?

모듈러 연산이란?

어떤 숫자를 일정한 값(모듈러스, modulus)으로 나누었을 때, 나머지를 구하는 연산

표현

ex. 숫자 a를 n으로 나눈 나머지
a mod n : 여기서 a는 피연산자이고, n은 나눌 수이며, 이 연산의 결과는 a를 n으로 나누었을때의 나머지이다.

예시

• 10 mod 3 = 1 (10을 3으로 나누면 나머지는 1)

• 15 mod 4 = 3 (15를 4로 나누면 나머지는 3)

• 7 mod 7 = 0 (7을 7로 나누면 나머지는 0)

• -5 mod 3 = 1 (-5를 3으로 나누면 몫이 -2이고, 나머지는 1)

• -10 mod 7 = 4 (-10을 7로 나누면 몫이 -2이고, 나머지는 4)

모듈러 연산은 mod n일때 항상 0 ~ n의 범위 안에서 결과값이 도출되게 하기 때문에, 반복되는 패턴을 만들거나, 숫자를 특정 범위 내로 제한해야 할 때 유용하게 사용할 수 있다.

예를 들어, 시계의 시간을 계산할 때 모듈러 연산을 사용할 수 있다. 24시간 이후에는 다시 0시간부터 시작되기 때문에 시간 mod 24와 같은 방식으로 계산하면 넘어가는 값들을 24시간 단위로 쉽게 변환할 수 있다.

모듈러 연산의 특징(Properties of modular arithmetic)

1. 합동의 성질

• 어떤 수 a에 n을 더하거나 빼더라도, (a + kn) mod n의 결과는 a mod n과 같다. (여기서 k는 정수)

ex. (7 + 3 x 5) mod 5 = 7 mod 5 = 2

2. 덧셈, 뺄셈, 곱셉

1. 덧셈: (a % n + b % n) % n = (a + b) % n
2. 뺄셈: (a % n - b % n) % n = (a - b) % n
3. 곱셈: (a % n * b % n) % n = (a * b) % n

ex. (8 + 15) mod 5 = 23 mod 5 = 3
ex. (8 - 5) mod 3 = 3 mod 3 = 0
ex. (4 x 7) mod 5 = 28 mod 5 = 3

3. 모듈러 지수 연산

지수가 큰 경우 직접 계산하면 숫자가 너무 커질 수 있기 때문에 모듈러 연산의 특징을 이용하여 해결해볼 수 있다.

예시