백준의 카잉달력을 풀면서 배운 최소공배수와 최대공약수를 구하는 방법에 대해서 설명해보고자 한다.
먼저
카잉달력의 문제는 위와 같으며 먼저 풀어보면 문제에서 어떤 방식으로 활용되는지 알 수 있다.
먼저 약수가 무엇인지 알아보자
약수란 a,b가 정수이고 a가 0이 아닐 때, a가 b의 약수라는 말은 곧 b= a*k라는 말과 같다. (여기서 k는 정수이다.)
이걸 우리는 a|b라고 표현한다. 예를 들어 7|14, 3|9
여기서 하나더 짚고 가야할 부분은 그렇다면 0의 약수는 무엇인가? 라는 것이다.
즉 x|0이 존재할까 이 말은 0=x*k (k는 정수에 속한다)이 성립되는 x가 존재할까 라는 물음과 같다. 이렇게 보면 0의 약수는 모든 정수이다. 왜냐하면 k=0일 때 x에는 모든 정수가 올 수 있기 때문이다.
자 이제 유클리드 호제법이 무엇인지 살펴보자
유클리드 호제법
유클리드 호제법은 유클리드가 만든 세계 최초의 공식이라고 한다.
기본 아이디어는 이와 같이 시작된다.
gcd(A,B) =gcd(B,r)
(A>B, A≠B, 0<=r<B)
이게 무슨 말인 처음부터 이상한 말 gcd가 등장해서 어려울 수 있지만 하나씩 살펴보자
gcd는 greatest common division 즉 나눠지는 공통적인 수 중에 가장 큰수를 그냥 영어로 그 앞글자만 딴 것이다.
A = pxB+r 로 표현하자 즉 B로 나눴을 때 p는 몫이고 r은 나머지이다.
이제 우리가 증명할 명제는
gcd(A,B)=g일 때 gcd(B,r)=g라는 것을 증명해야 한다.
✔️ gcd(A,B)=g라는 것은
A = gxa
B = gxb
(a와 b는 서로소, 즉 gcd(a,b)=1)
여기서 서로소란
1을 제외하고는 공통 인수가 없다는 것이다.
다시 돌아와서
✔️ A = pxB+r에 A = gxa ,B = gxb 이걸 대입해보자
그러면
gxa = pxgxb+r
r만 남게 옮기면
r =gxa -pxgxb
r = gx(a-pxb)
r = gxr'가 된다 (r'=a-pxb라고 가정한다)
즉 g|r g가 r의 약수라는 것이다.
그러면
✔️gcd(B,r)=g임을 보여줘야 한다. 즉 B와 r의 최대공약수가 g가 진짜 맞는지 확인해야한다.
B=gxb
r=gxr'
즉 둘다 g가 약수이다,
g가 최대공약수가 되려면
b와 r'는 서로소여야 한다.
gcd(b,r')=1이 성립되어야 한다.
이를 귀류법을 사용해서 증명한다.
귀류법이란
어떤 주장에 대해 그 함의하는 내용을 따라가다보면 이치에 닿지 않는 내용 또는 결론에 이르게 된다는 것을 보여서 그 주장이 잘못된 것임을 보이는 것
✔️즉 우리는 gcd(b,r')=ɑ(ɑ≠1)를 증명할 것이다.
이는 b와 r'가 서로소가 아닌 것을 증명하는 것이다.
b=ɑxb1
r'=ɑxr1
A = pxB +r
gxa = pxgxb + gxr'
gxa = pxgxɑxb1 + gxɑxr1
gxa = gxɑ(pxb1 + r1)
이는 A가 gxɑ로 나눠지고
B도 gxɑ로 나눠지기 때문에
처음 gdc(A,B) =g라는 것에 모순이 된다. 따라서
ɑ는 1이다!!.
예시
gcd(12345,123) = gcd(123,45) = gcd(45,33)= gcd(33,12)=gcd(12,9)=gcd(9,3)=gcd(3,0)=3
앞서 배웠듯이 0은 모든 정수로 나눠진다!
이제 카잉달력을 풀어보자 다음 게시글은 카잉달력에 대해서 정리해보려고 한다.
그렇다면 최소공배수는?
gcd(A,B)=g라고 할 때
A = gxa
B = gxb
이다.
최소공배수는 gxaxb이기 때문에
AxB / gcd(A,B)가 최대공배수가 된다.
이는 (gxa) x (gxb) /g 이기 때문이다.
java 코드
static int gcd(int A, int B){
if(B==0) return A;
return gcd(B,A%B);
}