고양이 두 잔

알고리즘을 풀다가 최대공약수를 구해야 하는 문제가 나와, 별생각 없이 순진하게 아래와 같이 풀었다. import sys a, b = map(int, sys.stdin.readline().split()) x = max(a, b) y = min(a, b) while x % y != 0: z = x % y x = y y = z print(a * b // y) 유클리드 호제법을 사용해서 간단하게 풀었다고 생각하고 넘어갔는데.. 혹시나 해서 검색해보니 역시나 파이썬 math 라이브러리에는 최대공약수와 최소공배수를 구해주는 함수가 있었다! 그것도 유클리드 호제법을 이용해 최적화가 되어 있는! 적잖이 김이 빠지지만, 사용 방법은 아래와 같다. import math # 최대공약수 print(math.gcd(35, 65..

유클리드 호제법은 두 양의 정수, 혹은 다항식의 최대공약수를 구하는 알고리즘이다. 기원전 300년에 그리스의 수학자 유클리드에 의해 기술된 이 알고리즘은 인류 최초의 알고리즘이라는 호칭도 가지고 있다. 그 내용은 다음과 같다. 유클리드 호제법 두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r)이다. 이때 r = 0이라면, a, b의 최대공약수는 b가 된다. 쉽게 말하면 큰 숫자를 작은 숫자로 나누고, 그 나머지로 작은 숫자를 나누는 계산을 나머지가 0이 될 때까지 반복하는 것이다. 예를 들어 1096과 411의 최대공약수를 구한다고 해보자. 첫 계산은 다음과 같다..