[Kotlin] 알고리즘 - 나머지 연산 분배 법칙

나머지 연산 (Modular Arithmetic)

어떠한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산

일반적으로 두 정수(A, B)를 나누면 몫(Q)과 나머지(R)가 구해진다.

A / B = Q 나머지 R

나머지 연산은 나눈 값에서 나머지만 구하는 연산으로, 모듈러 연산자를 사용하여 다음과 같이 표현한다.

A mod B = R

이때 A 모듈러 B는 R과 같다, 라고 말한다. (B는 모듈)

프로그래밍 언어에서는 %를 사용하여 A % B으로 표현한다.

시계로 이해하기

A를 1씩 증가시키며 B로 나누면 나머지 값이 0부터 B-1까지 반복된다.

이는 시계에서 시침이 돌아가는 과정와 유사하다. (1 mod 12 = 1, 2 mod 12 = 2, 11 mod 12 = 11, 12 mod 12 = 0, 13 mod 12 = 1)

1. 아날로그 시계는 원에 1부터 12까지 시간이 적혀있다. 여기서 12를 0으로 바꾸면 모듈(B)이 12인 원이 된다.
2. A를 3이라고 하면, 0에서 시작하여 3만큼 시침을 돌린다. (양수면 시계 방향, 음수면 반시계 방향)
3. 멈추는 지점에 위치한 숫자가 해가 된다. (3 mod 12 = 3)

• 음수 계산 예시: -3 mod 5 = -(3 mod 5) + 5 = -3 + 5 = 2

합동 (Congruent)

두 숫자 A와 B를 C로 각각 모듈러 연산을 했을 때 결과값이 같다면 A와 B는 모듈 C에 대한 합동 관계라고 한다.

A mod C = B mod C가 성립하면 합동 관계 A ≡ B mod C로 표현할 수 있다.

동치 관계

모듈로 연산을 통해 파이(원)를 동일한 크기를 가진 조각으로 나누는 개념

파이를 어떻게 조각들(동치류)로 분할할지 규정한다.

파이를 모듈 C로 나누었을 때 같은 조각(동치류)에 속하는 숫자들은 동치 관계를 갖는다.

한 조각 안에 있는 어떤 두 값의 차이는 C의 배수이다.

파이 조각들은 모듈 C에 대한 합동 관계를 가지며, 이것이 동치 관계를 형성한다.

특성

• 반사성 (Reflexivity): A가 A와 관계가 있다. A ≡ A mod C
• 대칭성 (Symmetry): A가 B와 관계가 있다면, B도 A와 관계가 있다. A ≡ B mod C 이면 B ≡ A mod C
• 추이성 (Transitivity): A가 B와 관계가 있고, B와 D가 관계가 있다면, A와 D도 관계가 있다. A ≡ B mod C 이고 B = D mod C 이면 A ≡ D mod C

분배 법칙

덧셈 또는 뺄셈과 나머지 연산 사이의 관계를 설명하는 수학적 법칙

두 숫자 A와 B를 C로 나누었을 때 몫과 나머지를 표현하면 다음과 같다.

A = Q1 * C + R1
B = Q2 * C + R2

덧셈/뺄셈/곱셈 분배 법칙 성질

(A ± B) mod C = (A mod C ± B mod C) mod C
(A × B) mod C = (A mod C × B mod C) mod C

• 증명

LHS = 식의 좌변
RHS = 식의 우변

LHS = (A ± B) mod C
= (C(Q1 ± Q2) ± R1 ± R2) mod C    // 나머지 연산이므로 몫은 0
= (R1 ± R2) mod C

RHS = (A mod C ± B mod C) mod C
= (R1 ± R2) mod C

LHS = RHS = (R1 ± R2) mod C

거듭제곱 성질

A^B mod C = ((A mod C)^B) mod C

• B 값에 따라 오버플로우가 발생할 수 있어 분할 정복을 사용해야 한다.

Reference

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

https://gosamy.tistory.com/75

https://dev-min.tistory.com/1

https://developer-mac.tistory.com/84

https://codingram.tistory.com/26

https://velog.io/@yyeonggg/모듈러-연산Modular-Arithmetic

https://velog.io/@gidskql6671/나머지Modulo-연산-분배법칙

https://gliver.tistory.com/5

https://www.crocus.co.kr/1231

https://sskl660.tistory.com/75

https://velog.io/@sw801733/나머지-연산-분배법칙-모듈러-연산

[Kotlin] 알고리즘 - 재귀(Recursive) - Dico

알고리즘 재귀(Recursive)를 코틀린으로 설명

dico.me

[Kotlin] 알고리즘 - 동적 계획법(DP, Dynamic Programming) - Dico

알고리즘 동적계획법 개념 정리

dico.me