반응형
나머지연산
-
나머지 연산Knowledge/Math 2019. 9. 5. 20:54
알고리즘 문제를 풀다보면 정수형으로 표현하기엔 너무 큰 값이 나올 때가 있다. 이럴 경우엔 크기를 줄이기 위해 특정 숫자로 나눈 나머지를 출력하라는 식으로 답을 요구하곤 한다. 이럴 때는 답을 다 구하고 나머지 연산을 수행하는 게 아니고 정답을 갱신할 때 마다 나머지 연산을 수행해 줘야 한다. ( 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..