[02강] 나머지(모듈러, modulo) 연산

---

안녕하세요 Gliver 입니다.

이번 글에서는 나머지(모듈러, modulo) 연산에 대해 알아보겠습니다.

 

목차

1. 나머지(모듈러, modulo) 연산의 의미
2. 나머지(모듈러, modulo) 연산의 특징
3. 실제 문제에서 나머지(모듈러, modulo) 연산

 

 

나머지(모듈러, modulo) 연산의 의미

모듈러 연산이란 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산입니다.

 

예를 들어, 두 정수 A, B에 대해서 A를 B로 나누어 나머지가 C가 나왔다면 "A mod B = C" 또는 "A % B = C"라고 표현할 수 있습니다.

C는 A를 B로 나누었을 때의 나머지에 해당하므로, "0 ≤ C ≤ B-1"을 만족

 

 

 

나머지(모듈러, modulo) 연산의 특징

이러한 나머지(모듈러, modulo) 연산의 특징은 크게 다음과 같이 3가지가 있습니다.여기서 A, B, C는 정수임.

특징 1 : 합 분해	(A+B) mod C = (A mod C + B mod C) mod C
특징 2 : 뺄셈 분해	(A-B) mod C = (A mod C - B mod C) mod C
특징 3 : 곱 분해	(A*B) mod C = ((A mod C) * (B mod C)) mod C

(합 분해, 뺄셈 분해, 곱 분해는 이해를 돕기 위해 제가 지어낸 명칭입니다.)

 

특징 1의 경우, "A와 B를 더한 후에 모듈러 연산을 수행한 값"과 "A, B 각각에 대해 모듈러 연산을 수행하고 더한 값"이 같다는 의미입니다.

실제로는 "A mod C + B mod C ＞ C-1"인 경우를 고려해서 모듈러 연산을 한 번 더 해줌.

 

특징 2와 3도 특징 1과 비슷한 메커니즘이므로 설명은 생략하겠습니다.

 

 

 

실제 문제에서 나머지(모듈러, modulo) 연산

실제 문제에서, 위에서 배운 모듈러 연산의 의미 또는 모듈러 연산의 특징 에 관해서 나올 수 있습니다.

 

모듈러 연산의 의미

실제 문제에서 모듈러 연산의 의미를 이용하는 경우는 대부분 원형적인 성질을 나타낼 때 쓰입니다.

문제로 예를 들어 설명하겠습니다.

[문제]
색의 원소 R, G, B가 있고, "R → G → B → R → G → ... " 순서로 성질이 바뀌는 문제가 있다고 해봅시다.

이 경우에, 원소의 종류는 3개이므로, 모듈러 연산은 3으로 하고 R, G, B를 각각 숫자 0, 1, 2에 대응시킵니다.

그러면, 모듈러 연산을 해서 0이 나오면 R, 모듈러 연산을 해서 1이 나오면 G, 모듈러 연산을 해서 2가 나오면 B에 대응시켜 문제를 해석할 수 있습니다.

 

이해가 안 되시는 분들은 "더보기"를 참고해 주시기 바랍니다.

 

예를 들어, "R → G → B → R → G"의 경우에 "0 → 1 → 2 → 3 → 4"로 대응이 되고, "0 → 1 → 2 → 3 → 4"이 "R → G → B → R → G"을 의미하는지는 다음과 같이 알 수 있습니다.

ㆍ0 mod 3 = 0 → 모듈러 연산을 해서 0이므로 R
ㆍ1 mod 3 = 1 → 모듈러 연산을 해서 1이므로 G
ㆍ2 mod 3 = 2 → 모듈러 연산을 해서 2이므로 B
ㆍ3 mod 3 = 0 → 모듈러 연산을 해서 0이므로 R
ㆍ4 mod 3 = 1 → 모듈러 연산을 해서 1이므로 G

따라서, "0 → 1 →> 2 → 3 → 4"은 "R → G → B → R → G"를 의미

 

이와 같이, 원소가 원형으로 반복되는 원형 배열로 해석할 수 있는 경우에 모듈러 연산을 활용할 수 있습니다.

선형 배열에서 배열의 끝을 배열의 처음과 연결시켜줘야 하는 경우 원형 배열로 상황을 인지하는 게 포인트

 

모듈러 연산의 특징

실제 문제에서 모듈러 연산의 특징을 이용하는 경우는 문제의 지문에 "답을 10000007로 나눈 나머지를 구하시오." 또는 "답을 M으로 나눈 나머지를 구하시오."라는 문구가 나오는 경우에 이용할 수 있습니다.

 

예를 들어, 답이 int 자료형을 벗어나는 $10^{1000}$인 경우에,이를 정답으로 제출하는 것은 불가능할 것입니다.
int 자료형은 약 -21억에서 21억까지 표현 가능

 

하지만, $10^{1000} \ mod \ 10000007$ 와 같은 형태는 int 자료형으로 표현할 수 있습니다. 

$A = 10^{1000} \ mod \ 10000007$라고 하면, $0 ≤ A < 10000007$을 만족하기 때문에 이는 int 자료형으로 표현할 수 있음.

 

따라서, 문제의 답을 구하는 과정에서 $mod \ 10000007$을 시행해 주면서 답을 구해 나가면 int 자료형으로 표현이 되고,

최종적으로 $10^{1000} \ mod \ 10000007$와 같은 값을 구할 수 있습니다.

 

이와 같이, 문제에서 '답을 ☆으로 나눈 나머지를 구하시오'가 나오는 경우에 모듈러 연산을 활용할 수 있습니다.

 

[관련 문제]
백준 : 2×n 타일링 (11726번)
백준 : 곱셈 (1629번)

 

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차 : https://gliver.tistory.com/7