🍖 모듈러 연산이란?
% 나누기 연산을 모듈러 연산이라고 한다.
print(10 % 3) # 3
print((10 + 3) % 3) # 1
print((10 % 3 + 3 % 3) % 3) # 1모듈러 연산한 나머지는 중간에 모듈러 연산을 하며 구해도 최종적으로 같은 결과가 나온다.
# 덧셈
(a + b) % c == (a%c + b%c) % c
# 곱셈
(a * b) % c == (a%c * b%c) % c나누기는 수학적으로 되지만 코딩할 땐 안된다. 안된다고 생각하자!
=> 페르마 소정리는 나누기도 처리할 수 있다.(a^p % p == a)
🍗 모듈러 연산을 사용하는 이유
파이썬이 아닌 다른 언어는 정수에 큰 제약이 있다.
파이썬도 기본적으로 수가 21억*21억*2보다 커지면 계산과정이 느려진다.
정수를 계속 작은 상태에서만 연산하기 위해 사용한다. 시간 복잡도를 대폭으로 줄일 수 있다.
그리고 이런 경우는 문제 자체가 결과를 1000000007로 나눈 나머지를 구하라!라는 식으로 출제된다.
passionate developer