파이썬 알고리즘 공부 - 최대공약수, 최소공배수 구하기

최대공약수, 최소공배수 구하는 것은 심심하면 나오는 과제입니다

처음 이 문제를 접했을 때는 최소공배수, 최대공약수가 뭐였는지도 기억이 안났던게 기억이 나네요 크흠..

그래서 이번 글은 파이썬으로 최대공약수, 최소공배수를 구현해봅니다

 

먼저 최대공약수입니다

최대공약수는 소인수분해를 이용해서 구하는 방법도 있습니다.

뭐 예를 들어 60과 48이 있다고 가정하면

60 = 2^2 * 3 * 4

48 = 2^4 * 3

이니까 공통된 수 중 지수가 작은 것을 골라내면 2^2 * 3 = 12가 최대공약수가 됩니다.

근데 이 방법 말고 유클리드 호제법을 사용하면 더 쉽게 구현할 수 있습니다

 

 

유클리드 호제법은 위의 설명에도 나와있지만, 192와 72가 있으면 큰 숫자를 작은 숫자로 나누어 나머지를 구합니다. 192 % 72 하면 48이 나오죠. 이제 그럼 72와 48을 나눠줍니다. 24가 나오죠. 48과 24를 나눠줍니다. 0이 나옵니다. 이렇게 되면 24가 최대공약수입니다! 이렇게 구하는 것이 유클리드 호제법입니다.

그래서 위 코드는 유클리드 호제법을 이용해서 최대공약수를 구하는 방법입니다.

a, b 두 개의 숫자가 들어오는데 만약 b 값이 크면 자리를 바꿔줍니다. 

그리고 b가 0보다 클 때까지 반복문을 진행하면서 현재 b 값은 c에 임시로 저장하고, b = a % b로 값이 바뀌게 됩니다.

그리고 a는 아까 갖고 있던 b의 값(c에 임의로 두었던)을 할당해주면 됩니다

그리고 재귀호출로 푸는 방법도 있습니다

 

 

마찬가지로 b가 더 크면 자리를 바꿔줍니다. 그리고 b의 값이 0이 되면 a를 return 해줍니다. 

그리고 평상시에는 재귀를 이용해서 함수를 다시 호출하는데 인자로 b와 a%b의 값을 넘겨줍니다

이렇게 해서 최대공약수를 구할 수 있습니다

 

다음은 최소공배수입니다.

최소공배수는 배수 중에서 공통된 작은 배수를 구하는 것입니다

이것도 소인수분해를 이용할 수 있는데요

예를 들어 60과 48이 있으면 

60 = 2^2 * 3 * 5

48 = 2^4 * 3

여기서 공통된 수 중 지수가 큰 것과 그리고 공통되지 않는 것들도 다 내려옵니다.

즉, 2^4 * 3 * 5 = 240이 최소공배수가 됩니다.

즉 최소공배수는 공통된 가장 작은 배수인데요

x = ab

y = bc 라는 값이 있다고 가정하면

최대공약수는 b입니다. 아까 위에서 설명한 소인수분해를 가지고 하면 되죠

그럼 최대공배수는?? abc가 되겠죠

여기서 x와 y를 곱하면 xy = ab^2c가 됩니다. 그리고 b를 나눠주면 xy / b = abc 가 됩니다.

즉, x와 y를 곱한 것에다가 최대공약수를 나눠주면 되는 것이죠!

 

 

그래서 최소공배수를 구하기 위해 최대공약수를 구하는 함수를 하나 만들고요

 

 

최소공배수는 a와 b 두 개의 숫자를 받으면 a * b // gcd(a, b)가 되겠습니다