Like Goseungduk

모듈러 연산 모듈러 연산은 간단히 말하면 나머지를 구하는 연산이라고 볼 수 있다. 위 식에서 a는 피제수, b는 제수, c는 나머지 이다. 예를 들면, 26 mod 5 = 1 이 될 수 있을 것이다. 이해 되었다면 이제 모듈러 연산의 여러 특징을 정리하려 한다. 1. 합동 모듈러 연산에서 26 mod 5 나 36 mod 5 는 모두 똑같이 1로 같다. 이를 합동 이라는 개념으로 부를 수 있으며 표현은 이와 같이 한다. 1 ≡ 6 ≡ 26 ≡ 36 mod 5 = 1 2. 성질 모듈러 연산에는 아래와 같이 좌변의 덧셈과 곱셈에 대해 분해할 수 있는 성질이 있다. [1] (a + b) ≡ ((a mod n) + (b mod n)) mod n [2] (a * b) ≡ ((a mod n) * (b mod n)) ..

1. 유클리드 알고리즘 유클리드 알고리즘은 최대 공약수의 두 가지 성질에 기반한 두 수의 최대공약수 추출 알고리즘이다. gcd(a,0) = a 두 수 중에서 한 쪽이 0이라면 두 수의 최대공약수는 다른 한 쪽 수이다. gcd(a,b) = gcd(b,r) ( ※ r은 a를 b로 나눈 나머지이다. ) 위와 같은 성질을 통해 나온 유클리드 알고리즘은 다음과 같다. gcd(a,b) = gcd(b,r) = ... = gcd(r,0) = r 이에 대한 것은 예제로 알아보자. ex) gcd(48,15) = gcd(15,3) = gcd(3,0) = 3 이런 식으로 48과 15의 최대공약수를 구할 수 있다. 파이썬으로 유클리드 알고리즘을 짜보자. def gcd(a,b): if(b==0): return a return g..