raekim   2년 전

정답이 아주 클 수 있는 문제라 특정 정수로 모듈러 연산을 한 값을 출력하라는 문제를 풀고 있습니다.

다른 사람의 정답 코드를 읽었는데, 모듈러 연산 과정을 함수로 뺐더라구요. 내용은 이랬습니다.

(x % mod+ mod) % mod
정수 x를  정수 mod로 모듈러 연산 하는 과정입니다.
여기서 왜 그냥 x%mod 로 끝나지 않고 mod를 또 더해서 다시 mod로 모듈러 연산을 하는 것인지 궁금합니다..
제가 수학적으로 모듈러 연산에 대한 이해가 부족해서 충분한 보충설명 해주신다면 정말 감사하겠습니다 !

chogahui05   2년 전

어떤 문제에서 그렇게 연산했는지는 잘 모르겠군요..

x>=0인 경우 사실 x%mod라고만 출력해도 굳이 상관은 없습니다.

그런데 (x%mod + mod)%mod를 생각해 봅시다.

x%mod = r (단 0<=r<mod)라고 해 봅시다. 거기에 mod를 더해봤자. 사실상 나머지는 r이거든요. 왜냐면

r+mod를 mod로 나누면 Q는 1일 거고, 나머지는 r일 거니까요. 그래서 굳이 상관은 없는데..

문제는 이런 경우가 있어요. 예를 들어 13에서 5를 뺀 값을 6을 나눈 나머지를 구한다고 해 봅시다.

13이라는 결과값을 단순히 13으로 저장하지 않고, 13%6으로 저장했다고 한다면 1이 나오겠네요.

그런데. (1-5)%6을 하면 어떤 결과가 나올까요? c에서는 -4가 나와요. 이건 원하는 결과값이 아니죠.

그런데 (1+6-5)%6을 하면 제대로 나와요. 나머지가 2로 나와요.


보통 나머지 연산에서 어떠한 결과값 (res)에 mod를 더하고 거기에, mod를 나눈 값을 결과값으로 취하는 이유는

res<0인 경우 때문에 그래요. 그런 경우가 종종 있고요..

댓글을 작성하려면 로그인해야 합니다.