[JAVA]STUDY/자료구조 & 알고리즘

[JAVA]모듈러 연산

개념 모듈러 연산이란 한 숫자를 다른 숫자로 나누었을 때 생기는 나머지를 구하는 연산이다. 코딩에서는 "%" 기호를 사용한다. ex) 5 % 3 = 2 쉬운 개념이지만, 모듈러 연산에는 생소할 수도 있는 몇 가지 성질이 있다. 위 식이 성립한다는 것인데, 간단하게 증명을 해 보겠다. 증명은 다 같은 원리로 진행되기 때문에, 첫 번째 성질만 증명하겠다. 증명 A를 C로 나누었을 때의 몫을 Qa, 나머지를 Ra라 하고, B를 C로 나누었을 때의 몫을 Qb, 나머지를 Rb라 하면 아래와 같이 식을 세울 수 있다. 위 식을 정리하면 아래와 같고, Ra는 A를 C로 나눈 나머지, Rb는 B를 C로 나눈 나머지 이므로, 아래와 같이 표현 가능하다. 따라서 첫 번째 성질이 성립한다는 것을 알 수 있다. 예시 코드 백..