[Algorithm] 모듈러 연산

모듈러 연산에 대하여

: 거창한 제목이지만, 사실 내가 모듈러 연산에 대해서 깊게 팔 자신은 없는 것 같다. 인터넷을 통해서 몇분이긴하지만.. 살펴봤지만 수학적인 개념(유클리드 호제법과 같은)인데, 블로그 내용만으로 내가 학습하기에는 약간 한계가 있는 것 같아서, 일단 오늘은 모듈러 연산을 코딩테스트에서 활용할 수 있는 수준에서 이해 및 정리하고자 한다.

알아둬야할 모듈러 연산의 분배법칙 (+,-, *)

(A + B) % C = ((A % C) + (B % C)) % C
(A - B) % C = ((A % C) - (B % C)) % C
(A * B) % C = ((A % C) * (B % C)) % C
	

: 위의 분배법칙이 왜 성립하는지는 수학적인 증명이 필요한데, 그 부분에 대해서는 좀더 공부를 한뒤에 정리를 해야겠다(물론 직접 숫자를 대입해서 해보면 맞지만,,, 이걸 수학적 증명이라 하지는 않으니까..ㅎㅎ).

관련 문제 풀어보기

: n의 m승을 10007로 나누는 간단한 문제지만 야속하게도(?) m의 범위를 어머아마한 숫자까지 뒀다..ㅎㅎ 따라서 일반적인 방법으로 풀면 n을 m승하는 동안 시간초과가 날 것이다(또한, 저렇게 큰 숫자를 담을수도 없거니와). 따라서 여기서는 모듈로 연산 그중에서도 곱셈의 분배법칙을 사용해서 풀어야한다.

1) (A*B)%C = ((A%C) * (B%C))  % C 를 이용해보자
2) 예를 들어, 251,000,000 을 계산해야한다고 할 때, 위의 식을 이용하려면?
3) 어차피 우리가 구하려는 것은 10007로 나눈 나머지이기에 (2550,000*2550,000) % 10007을 구한다고 생각해보자(251,000,000 이걸 두수의 곱으로 표현한 것)
4) 모듈러 연산을 이용하면 
(2550,000*2550,000) % 10007 = ((2550,000 % 10007)*(2550,000 % 10007)) % 10007 이 성립한다.
5) 따라서, 이를 재귀함수로 만들어볼 수 있다.
6) 재귀함수가 하는 일 정의 : input으로 받은 수(n, m을 이용하여 nm로 표현되는 수)를 이등분하여 두수의 곱으로 표현하고, 그 두수의 곱(input으로 받은수)에 10007을 나눈 값을 리턴하는 함수
7) 기저조건 : 만약 m이 1이면 n을 리턴한다
8) 이렇게 하면 모듈러 연산을 이용하면서 큰 수를 쪼개면서 연산을 수행하기 때문에 공간복잡도(큰수를 담을)와 시간복잡도(10007씩 나누면서 연산을 하기 때문에 훨씬 빠름)를 해결할 수 있다.

풀이 코드

마치며..

: 모듈러 연산은 위에 경우처럼 숫자가 너무 큰 수에 대하여 나머지 연산을 해야하는 경우나 연산의 수가 너무 커지는 경우 등에 사용하면 좋을 것 같다.