[Algorithm] 모듈러 연산(나머지 연산)

알고리즘 문제를 풀다보면 특정 값을 나눈 나머지를 리턴 또는 출력하라는 문제를 종종 볼 수 있다.

 

이렇게 주어지는 이유는

알고리즘 문제를 푸는 과정에서 결과 값이 매우 커서 오버플로우가 발생하기 떄문에 문제에서 친절하게 자료형 범위 내에서 계산이 되라고 모듈러 연산을 요구한다.

 

그런데 모듈러 연산을 요구하는 경우 단순히 결과 값에만 모듈러 연산을 수행하면 이미 결과 값은 너무 커져버려서 오버플로우가 발생한 경우이기 때문에 연산 과정 도중에 모듈러 연산을 적용해야 한다.

 

그렇다면 모듈러 연산을 적용하기 위해선 모듈러 연산 분배 법칙에 대해 알고있어야 한다.

모듈러 연산은 각 피연산자에 모듈러 연산을 적용 후에 계산한 결과에 대해 다시 한번 모듈러 연산을 적용하면 된다.

뺄셈에선 음수가 나오는 것을 방지하기 위해 모듈러 연산을 하는 수를 더해주며

나눗셈은 모듈러 연산 분배 법칙이 성립하지 않는다.

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p