알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동식을 만족하는 유일한 해를 구할 수 있게 해주는 강력한 정리이다.$$x \equiv 1\; \mathrm{(mod \; 3)},\\ x \equiv 2 \; \mathrm{(mod \; 5)},\\ x \equiv 3 \; \mathrm{(mod \; 7)}$$합동식들의 $a \equiv b \mod m$의 형태에서, 모든 m들은 서로 서로소 관계여야 한다.또한 각 합동식에서 x의 계수가 1이 아닌 경우가 있는데, 그런 경우에는 확장된 유클리드 알고리즘(EEA)를 사용해서 곱셈 역원을 구해서 양변에 곱해준 후 CRT를 적용한다.중..

확장된 유클리드 호제법이란?2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기  유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.호제법(互除法)이라는 단어가 따로 있는것은 아니고, 서로(互) 나누기(除nivr4y.tistory.com유클리드 호제법이 두 정수 $a$, $b$의 최대공약수 $gcd(a,b)$를 구하는 방법이였다면 확장된 유클리드 호제법은 두 양의 정수 $a$,$b$가 있을때 베주 항등식이라 불리는 아래의 식에서 $u,v$의 값을 찾아내는 효율적인 방법이라고 할 수 있다.$$ \displaystyle{\di..

조합의 정의조합(Combination) : 서로 다른 n개의 원소에서 r(단, 0를 중복 없이, 순서를 고려하지 않고 선택하는 것.중요한 것은 순열과 같이 선택해서 나열하는 것이 아닌, 선택하기만 하기 때문에 순서는 중요하지 않다는 것이다. (1,2,3,4,5)에서 (2,3)을 뽑는 것과 (3,2)를 뽑는 것을 같은 것으로 본다는 말이다. n개 중에서 r개를 뽑는 조합을 다음과 같이 표현할 수 있다.$$ _nC_r = \binom{n}{r} $$조합을 다룰때 빠질 수 없는 순열은 다음과 같이 표현할 수 있다.$$ {}_n{\rm P}_r $$순열과 조합 $$ {}_n{\rm P}_r = \frac{n!}{(n-1)!} $$ $$ _nC_r = \frac{n!}{(n-r)!r!} $$순열과 조합을 구하는 ..

유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.호제법(互除法)이라는 단어가 따로 있는것은 아니고, 서로(互) 나누기(除) 때문에 붙여진 이름이다. 유클리드 호제법의 정의는 다음과 같다.자연수 a, b에 대해서 a를 b로 나눈나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 즉,  gcd(a, b)=gcd(b,r) 이라고 나타낼 수 있다.영어로 유클리드 호제법은 Euclidean algorithm 이다. 말 그대로 알고리즘이기 때문에, 유클리드 호제법을 한번만 사용해서는 큰 의미가 없고,, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 ..

일반적으로 python을 사용할때 올림을 구현해야할 일이 있으면 math 모듈을 import 해서 사용하지만, 간단한 방법으로 구현할 수 있다.올림a = 7b = 4result = -(-a//b)print(result) # 2위와 같이 음수에서의 나눗셈의 성질을 이용하면 따로 math 모듈을 사용하지 않아도 올림을 구현할 수 있다. 나눗셈에서는 나머지가 항상 양수여야하기 때문에 이렇게 연산이 진행된다.내림a = 7b = 4result = a/bprint(int(result)) # 1내림은 많이 사용하는 int()를 사용하면 된다. int 함수는 float 형을 변환할 때 정수 부분만 취하기 때문에, 나머지 소수 부분은 버려버린다.반올림print(round(1.5)) # 2print(round(2.5)) ..