[알고리즘] 나누기 연산의 분배 법칙

코딩 테스트에서 정답의 나머지 값을 요구하는 경우가 종종 있다.

 

이 문제에는 자료형의 표현 범위를 넘지 않게 유도하고 나머지 연산의 원리를 알고 있는지 묻는 의도가 담겨 있다.

---

나머지 연산은 나눗셈을 제외하고 덧셈, 뺄셈, 곱셉의 분배 법칙이 성립된다.

예시 값: A = 20, B = 6, C = 3

 

● 덧셈의 분배 법칙 성립 → (A+B) % C == (A%C + B%C) % C

(20+6) % 3 = 26 % 3 = 2 (20 % 3 + 6 % 3)  % 3 = (2+0) % 3 = 2

 

●  뺄셈의 분배 법칙 성립 → (A-B) % C == (A%C - B%C) % C

(20-6) % 3 = 14 % 3 = 2 (20 % 3 - 6 % 3)  % 3 = (2-0) % 3 = 2

 

●  곱셈의 분배 법칙 성립 → (A*B) % C == (A%C * B%C) % C

(20*6) % 3 = 120 % 3 = 0 (20 % 3 * 6 % 3)  % 3 = (2*0) % 3 = 0

---

나머지 연산 분배 법칙 예시

1부터 50까지 곱한 값을 10007로 나눈 나머지를 구하는 문제를 해결해 보자

long answer = 1;

for (int i = 0 ; i <= 50; i++){
	answer = answer * i;
}

System.out.printlin(answer%10007);

# 실행결과
-6828

위 예시는 곱셈 과정에서 이미 long 자료형의 표현 범위를 초과하여 잘못된 값이 나오는 경우이다.

 

long answer = 1;

for (int i = 0 ; i <= 50; i++){
	answer = (answer * i)%10007; // 곱셈을 수행할 때 마다 나머지 연산을 수행
}

System.out.printlin(answer%10007);

# 실행 결과
3235

이와 같이 곱셈을 실행할 때마다 나머지 연산을 함께 수행하도록 코드를 수정하면, 결과값이 정상으로 출력되는 것을 확인할 수 있다.

 

일반적으로 문제에 '결과값을 ~으로 나눈 나머지를 출력하세요'라는 문제가 나오면, 정답을 구한 후 마지막에 나머지 연산을 한번만 적용하는 방법은 위험할 수 있다.

---

내용 출처

Do it! 알고리즘 코딩 테스트: 자바 편 | 김종관