최대공약수와 최소공배수
가끔 문제에 나오는 것을 볼 수 있는데 이번에 프로그래머스_N개의 최소공배수문제를 풀면서 다른분들 풀이게 간단하게 해결된 최소공배수를 보고 알아보기 시작했다.
최대공약수를 매우 간단한식으로 구현할 수 있었는데 유클리드 호제법이라는 것을 활용해 구할 수 있었다.
유클리드 호제법 부터 알아보자.
유클리드 호제법
gcd(a,b) : a,b의 최대공약수
유클리드 호제법은 두 정수 a,b가 있을 때(a>b) 아래의 식이 성립한다는 것이다.
gcd(a,b) === gcd(b,a%b)
완벽하게는 아니고 간단하게 증명해서 이해해보자.
- A,B는 서로소이다.
- G:최대공약수 , r: 나머지 q: 몫
아래의 식을 차례차례 정리해가보겠습니다.
-
a = AG, b=BG
-
a= bq + r (b로 나누어지고 몫:q 나머지:r)
-
AG = BGq + r (위 식에 a = AG, b=BG 를 대입)
-
AG-BGq = r (위 식을 정리)
-
G(A-Bq) = r (r은 a,b의 최대공약수 G를 갖고있다.)
r = G(A-Bq) / b = GB 이기 때문에 r,b의 공약수는 G가 된다.
그럼 여기서 G가 최대공약수인 것을 알기 위해서는 (A-Bq)와 (B)가 서로소인 것을 확인해야합니다.
(A-Bq)와 (B)가 서로소가 아니라고 가정을 하고 진행해봅시다. (이 가정은 틀려야 되기 때문에 결론에 모순이 발생해야합니다.)
서로소가 아니기 때문에 공약수인 t를 갖게됩니다.
(A-Bq) = mt / B = nt
(A-Bq) = mt에 B = nt 를 대입해보면 A = mt+ntq 가됩니다.
즉, A = t(n+bq)로 t약수를 갖게됩니다. 어? 그럼 B=nt이므로 B 도 t라는 약수를 갖고 있습니다.
A,B는 서로소가 아니게 됩니다. 하지만 위에서 A,B는 서로소라고 했기 때문에 서로소가 아니라는 가정은 틀리게 됩니다.
즉, (A-Bq)와 (B)는 서로소입니다. 즉, r,b의 공약수인 G는 r,b의 최대 공약수 (gcd(b,r))이 되고 아래의 공식이 성립하게 됩니다.
두수 a>b인 정수 a,b에 대해 gcd(a,b) = gcd(b,a%b)
이제 위의 공식을 이용해서 최대공약수를 코드로 구현할 수 있습니다.
두수 x,y에 대해 x%y===0이라면 gcd(x,y)===y 를 이용해 나머지가 0일 때까지 반복해서 구하면 됩니다.
while문으로 구하기
- 코드에서 구현할 때는 a,b를 굳이 정렬해줄 필요가 없는게 만약 앞에 값이 더 작다면 첫번째 나머지 구할 때 a,b순서만 바뀌기 때문에 따로 정렬 작업은 필요하지 않습니다.
const gcd =(a,b) =>{
while(a%b!==0){
const mod = a%b
a=b
b=mod
}
return b
}재귀로 구하기
const gcd=(a,b)=>{
return a%b?gcd(b,a%b):b
}최소공배수
위에서 구현한 최대공약수를 이용해 최소공배수를 편하게 구현할 수 있습니다.
최소공배수 = 두 수의 곱 / 두 수의 최대공약수
const lcm=(a,b)=>{
return a*b/gcd(a,b)
}마무리
항상 그냥 나누기를 이용하는 최대공약수 함수를 만들어 문제를 해결다가 유클리드 호제법이라는 것을 알게 됐습니다.
사실 완벽하게 이해됐다..라기보다는 그냥 외워서 사용할 것 같습니다.
이분의 블로그를 보고 어느정도 이해하게 됐습니다. 혹시나 까먹을까 제가 이해하기 편한대로 작성한 글이니 이해가 잘 되지 않으시는 분들은 이 블로그에서 보시면 한결 쉽게 이해가실 겁니다!
참조
