[알고리즘] 모듈러 연산 part. 1

모듈러 연산?

모듈러 연산은 어느 하나의 값을 나눈 나머지를 구하는 연산이다.

두 정수 A와 B가 있다고 하자, A를 B로 나누었을 때 나머지는 C일 경우를 표현하면
A $mod$ B = C 로 표현할 수 있다.

---

모듈러 분배 법칙

앞에서 간단하게 모듈러 연산이 무엇이고 어떻게 표현을 하지는 알아봤지만 이러한 모듈러 연산은 어떻게 사용을 하지는 가장 궁금한 부분이다.

코딩 테스트 문제를 풀어본 경험은 있을 것이다. 코드를 다 작성하고 실행을 했을 때 타입의 크기를 넘어가는 오버플로우가 발생한 경우 때문에 실패를 했을 것이다.

이러한 오버플로우에 대비하여 모듈러 연산을 이용하면 해결이 가능하다.

예를 들어서 $123+456+789$의 10으로 나누었을 때 나머지를 구한다고 가정을 하자

보통은 더하기를 하고 나머지를 구할 것이다. 지금은 모든 수를 더했을 때의 값과 나누는 값이 간단해서 쉽게 계산이 가능하지만, 숫자의 크기가 커진다면 생각보다는 복잡할 수 있고, 선언한 타입의 값의 범위를 넘어가도 문제가 된다.

그래서 분배 법칙을 이용해서 각 숫자를 나누었을 때 나머지 값들을 합하고 그 수를 다시 나머지를 구하면 된다.

(123+456+789) $mod$ 10 = 8 $<=>$ 123 $mod$ 10 + 456 $mod$ 10 + 789 $mod$ 10 = 18 $mod$ 10 =8

$(a + b) mod$ c $=$ $($a $mod$ c + b $mod$ c $)$ $mod$ c
$(a - b) mod$ c $=$ $($a $mod$ c - b $mod$ c + c $)$ $mod$ c
$(a \times b) mod$ c $=$ $($a $mod$ c $\times$ b $mod$ c $)$ $mod$ c

---

간단한 사용 예제

programmers | Lv.2| 3 $\times$ $n$ 타일링 이 문제에 적용을 해보겠다.

간단하게 해당 문제는 특정한 조건에 맞는 경우의 수를 반환을 해주는 문제이다.

해당 문제의 제한사항을 주목을 하자.

제한사항

• 가로의 길이 $n$은 5,000 이하의 자연수이다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007로 나눈 나머지를 반환해라.

여기서 마지막 제한 사항이 중요하다. 지정한 크기를 넘을 때 나머지를 반환을 하라고 했다. 하지만 이를 계산하기 위해 경우의 수를 구하고 나머지를 구하는 방법 보다 앞에서 확인한 모듈러 분배 법칙을 이용하는 것이 좋다.

---

다음에는 모듈러의 역수와 페르마 소정리를 이용한 모듈러 역수 계산을 하는 방법에 대해서 확인을 할 것이다.