모듈러 연산

알고리즘 문제를 풀다가  큰 수를 거듭제곱하게되면 시간초과 문제에 봉착하게 되는 데 이때 모듈러 연산을 사용하면

오버플로우없이 빠르게 값을 구할 수 있다.

모듈러 연산이란

나눗셈을 표현하는 식으로 A/B를 계산했을 때 몫을 Q, 나머지를 R이라 한다면

A mod B = R로 표현할 수 있다. (=A 모듈로 B는 R과 같다)

모듈러 거듭제곱

A^B mod C = ( (A mod C)^B ) mod C

B의 값이 조금만 커져도 A^B의 값이 겁나게 커져서, A^B mod C를 시도하면 시간초과가 발생한다.

ex) 2^90 = 1,237,940,039,290,000,000,000,000,000

왜 빠른가?

분할 정복 알고리즘을 사용하여 거듭제곱을 계산해서이다.

p^n을 계산하는 대신 (p^n/2)*(p^n/2) 이런식으로 값을 분할하고 각 값에 mod C를 적용해서 나머지를 계산해주고

합쳐서 mod C를 다시 계산한다.

 

예시

Softeer. 바이러스 문제.

https://thegreengables.tistory.com/126

[Python] Softeer 바이러스

문제처럼 보통 % 1000000007 이런식으로 최대값을 지정해준다.

Python에서는 pow함수의 3번째 인자로 C값을 주면 모듈로 연산이 가능하다.

# (4 * 4 * 4) % 5와 같다
x = pow(4, 3, 5)

---

참고

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation

모듈로 거듭제곱법 (개념 이해하기) | 암호학이란? | Khan Academy

https://www.w3schools.com/python/ref_func_pow.asp

Python pow() Function