나머지 연산

알고리즘 문제를 풀다보면 정수형으로 표현하기엔 너무 큰 값이 나올 때가 있다.

이럴 경우엔 크기를 줄이기 위해 특정 숫자로 나눈 나머지를 출력하라는 식으로 답을 요구하곤 한다.

 

이럴 때는 답을 다 구하고 나머지 연산을 수행하는 게 아니고

정답을 갱신할 때 마다 나머지 연산을 수행해 줘야 한다.

 

( A + B ) % M 은 ( ( A % M ) + ( B % M ) ) % M 과 같기 때문

이는 곱셈에서도 ( A X B ) % M 은 ( ( A % M ) X ( B % M ) ) % M 이와 같이 성립한다. 

 

다만 나누기의 경우엔 성립하지 않고 뺄셈의 경우엔 주의해야 하는 부분이 있다.

 

예를 들어 (6 - 5) % 3 은 1. 즉, 1 % 3은 1이 나오지만

(6%3 - 5%3) % 3 은 (0-2) % 3 이 되어버려서 -2 % 3이 된다.

 

이의 답은 프로그래밍 언어마다 다른데 파이썬은 1이 나오지만 

Java와 C와 C++은 -2가 나온다.

 

이런 경우를 방지하기 위해서 뺄셈의 경우

나머지를 구해 뺀 값에 나머지를 한번 더해주는 과정을 거친다.

 

a % c 는 0 이상이거나 c보다 작고

b % c 역시 0 이상이거나 c보다 작기 때문에

(a % c - b % c) 의 결과는 항상 -C 보다는 크고 C 보다는 작다.

 

따라서 ( a % c - b % c + c ) 는 항상 0보다 큰 값을 갖기 때문에 위와 같은 상태를 방지할 수 있고

이 상태에서 다시 C로 나머지 연산을 해주면 원하는 결과를 얻을 수 있다.