😄 개요
알고리즘 문제들을 풀다보면 경우의 수를 찾는 DP문제, 큰 수 구하기 등 여러 부분에서 해의 값을 어떤 큰 소수로 나눈 나머지 로 구해달라는 상황을 마주할 수 있습니다.
대부분 이런 경우에서는 답을 구해놓고 모듈러 연산을 하는 것이 아닌, 해를 구해가는 과정 중간 중간에 모듈러 연산을 처리하는 것을 볼 수 있습니다.
하지만 해를 구해가는 과정에 나눗셈이 들어가게 되면 마음대로 모듈러 연산을 할 수 없습니다.
이럴 때는 어떻게 해야 할까요?
🪡 이론
모듈러 연산
정수를 어떤 주어진 수에 대한 나머지에 대하여 정의하는 것을 모듈러 연산이라고 하죠.
해를 구하는 중간 중간에 모듈러 연산을 처리해도 답이 같은 이유는
정수를 합하고 곱하고 뺄 때, 모듈러 연산을 전에 처리하는 것과 후에 처리하는 것이 같기 때문입니다.
합, 차, 곱에서 모듈러 연산
합, 차, 곱에서 모듈러 연산을 전에 처리하는 것과 후에 처리하는 것이 같다는 것을 파이썬 코드로 살펴보면 다음과 같습니다.
a = 13
b = 17
p = 11
## 합
(a + b) % p == ((a % p) + (b % p)) % p # True
## 차
(a - b) % p == ((a % p) - (b % p)) % p # True
## 곱
(a * b) % p == ((a % p) * (b % p)) % p # Truea와 b를 연산하고 모듈러 취하는 것과, 모듈러 취하고 난 후 연산 하는 것이 값이 같다는 것을 확인할 수 있습니다.
나눗셈에서 모듈러 연산
그렇다면 나눗셈은 어떨까요?
a = 13
b = 17
p = 11
## 나눗셈
(a / b) % p == ((a % p) / (b % p)) % p # False나눗셈은 성립하지 않는 다는 것을 확인할 수 있습니다.
모듈러에서 나눗셈을 하려면 다른 방식이 필요합니다.
항등원과 역원
기본적인 개념은 나눗셈을 곱셈으로 치환하여 생각하는 것입니다. 이를 위해서는 항등원과 역원의 개념을 알아야 합니다.
먼저 항등원에 대해 알아보겠습니다.
항등원은 어떠한 연산에 대해 값에 연산을 해도 동일한 값이 나오는 숫자입니다.
값 (연산) 항등원 = 값이 성립한다는 뜻이죠.
예를 들어보겠습니다.
덧셈 연산에 대한 항등원은
A + 항등원 = A
을 만족하는 값이므로 0입니다.
곱셈 연산에 대한 항등원은
A * 항등원 = A
을 만족하는 값이므로 1입니다.이 개념을 가지고 역원에 대해 알아보겠습니다.
역원은, 연산해서 항등원이 나오는 수인데요, 예를 들어보겠습니다.
3의 덧셈 연산에 대한 역원은
3에 덧셈 연산을 해서 0(덧셈 연산에서 항등원)이 나오는 수이므로
-3입니다.
2의 곱셈 연산에 대한 역원은
2에 곱셈 연산을 해서 1(곱셈 연산에서 항등원)이 나오는 수이므로
0.5입니다.여기서부터 핵심입니다.
a를 b로 나눈다는 것은 a에 (곱셈에 대한 b의 역원)을 곱하는 것과 같습니다.
간단하게 증명해보겠습니다.
b * (곱셈에 대한 b의 역원) = 1
이 성립합니다.
양변에 b를 나누면
(곱셈에 대한 b의 역원) = 1 / b
가 성립합니다.
a / b 를 a * 1 / b 로 생각하고,
1 / b 는 (곱셈에 대한 b의 역원)와 같으므로,
a / b 는 a * (곱셈에 대한 b의 역원)와 같습니다.사실 생각해보면, 당연한 말입니다. 5로 나눈다는 것은 1 / 5 (곱셈에 대한 5의 역원)를 곱한다는 것과 같은 말이니까요.
여기서 문제는, 모듈러 연산에서 곱셈에 대한 값의 역원을 구하는 일입니다.
일반적인 곱셈에서의 역원을 구할 때 처럼 역수를 취하면, 결국 나누는 것과 같으므로, 다른 방식으로 역원을 구할 필요가 있습니다.
페르마의 소정리
그렇다면, 모듈러 연산에서 곱셈에 대한 값의 역원을 구해보겠습니다.
이를 위해서는 페르마의 소정리를 알고 가야합니다.
이중에서
a = 13 #p의 배수가 아닌 수
p = 11 #소수
## 페르마의 소정리
(a ** (p - 1)) % p == 1 # True이 식을 꼭 알고 가야합니다.
- p는 임의의 소수이고, a는 p의 배수가 아닌 수라고 가정하겠습니다.
- a에 p-1 거듭제곱을 한 후 p에 대해 모듈러 연산을 하면 1이 나옵니다.
1은 곱셈에서 항등원 이므로, 다음과 같이 역원을 유도해낼 수 있습니다.
(a * (a의 역원)) % p == 1 ...(1)
페르마의 소정리에 의하면,
(a ** (p - 1)) % p == 1 이므로,
a의 p - 1 거듭제곱에서 a를 하나 꺼냅니다.
그러면 다음과 같은 식이 성립합니다.
(a * a ** (p - 2)) % p == 1 ...(2)
(1)과 (2)에 의해,
a의 역원은 a ** (p - 2)라는 것을 알 수 있습니다.- 모듈러 연산에서 곱의 역원은 a의 p - 2 거듭제곱입니다.
모듈러 연산에서 나눗셈 대체하기
위의 식들을 합치면 나눗셈에서 모듈러 연산을 다음과 같이 변환할 수 있습니다.
a = 26
b = 13
p = 11
## 나눗셈
(a / b) % p == ((a % p) * ((b ** (p - 2)) % p)) % p # True위 식이 성립하려면, a 가 b로 나누어 떨어져야 합니다. 우변은 곱과 모듈러 연산으로만 이루어져 있을테니 결과가 정수일테고, 따라서 좌변도 정수여야 위 식이 성립하겠죠.
🧵 적용
이 방식의 핵심은 페르마의 소정리를 이용해 나눗셈을 곱셈으로 치환하는 것입니다. 나눗셈에서는 중간 중간에 모듈러 연산시 결과가 달라지지만, 곱셈에서는 같으니까요.
나눗셈의 결과가 정수임을 알지만, 값들이 너무 커서 한번에 연산이 불가능할 때, 페르마의 소정리를 이용해 나눗셈을 곱셈으로 대체하고, 계산 중간 중간에 모듈러 연산을 처리하며 계산량을 줄이는 방식입니다.
자세한 적용 예시는 다음에 문제풀이로 돌아오도록 하겠습니다😊
