알고리즘
-
[알고리즘/파이썬] 유클리드 호제법 - 최대공배수(GCD), 최소공배수(LCM)를 구해보자알고리즘 2022. 12. 16. 19:22
유클리드 호제법이란? 두 자연수의 최대공약수를 구하는 알고리즘으로 유클리드라는 사람에 의해 발견되어 그 이름을 땄다. 호제법은 서로 나누는 방법이라는 뜻으로 두 수가 서로 나누며 원하는 값을 얻는 방법을 말한다. 두 자연수의 최대공약수를 구함으로써 자연스럽게 최소공배수도 구할 수 있다. 참고로, 최대공약수 GCD는 Greatest Common Divisor의 약자이고 최소공배수 LCM은 Least Common Multiple의 약자이다. 사전적 정의 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반..