알고리즘-수학
나머지 연산
hy1as
2023. 3. 13. 17:24
이번 포스트에서는 나머지 연산 ( Modular arithmetic )에 대해서 알아보겠습니다.
1. 나머지 연산 ( Modular arithmetic )이란?
양의 정수 제수 $ b $(Divider)와 임의의 정수 피제수 $ a $(Dividend)에 대해, $ a = bq + r $을 만족시키는 유일한 정수 $ q $와 $ 0 <= r < b $가 존재합니다. 이때 $ r $를 나머지 (Remainder)라고 하며 이를 구하는 연산을 나머지 연산 (Modular arithmetic) 이라고 합니다. 일반적으로 프로그래밍 언어에서는 '%' 로 구현되어 있습니다.
const r = a % b
2. 나머지 연산의 분배 법칙
나머지 연산의 아래와 같은 식 (분배 법칙)이 성립합니다.
* $ (A+B)\,mod\,M = ((A\,mod\,M) + (B\,mod\,M))\,mod\,M $
* $ (A*B)\,mod\,M = ((A\,mod\,M) * (B\,mod\,M))\,mod\,M $
* $ (A-B)\,mod\,M = ((A\,mod\,M) - (B\,mod\,M)+M)\,mod\,M $
뺄셈의 경우 $ (A\,mod\,M) - (B\,mod\,M) $ 값이 음수 값이 나올 수 있습니다.
그렇다면 다른 연산들과 같이 계산하게 된다면 음수에 대한 나머지 연산을 하게 되는데요.
프로그래밍 언어마다 음수에 대한 나머지 연산을 다르게 처리하기 때문에 같은 연산에 대해 일관된 답을 얻기 어렵습니다.
때문에 $ M $ 을 한 번 더해줌으로써 올바른 계산 결과를 얻을 수 있습니다.
마치며
알고리즘 문제 풀이 시 "~를 x로 나눈 나머지를 출력하라" 와 같은 문장이 제시될 때가 있습니다.
이유는 컴퓨터가 저장 할 수 있는 자료형의 범위가 제한되어 있기 때문에 만약 결과 값이 해당 범위를 넘어서게 되면 연산 결과를 나눈 나머지를 제출할 것을 요구합니다.
이 때는 단순 결과 값뿐만 아니라 문제 진행 도중에도 나머지 연산이 필요한 경우가 다수입니다.
그러니 알고리즘 문제 풀이를 준비하시는 분들은 해당 포스트 내용을 꼭 기억하도록 합시다.
감사합니다.
출처