[Algorithm] 최대공약수(GCD), 최소공배수(LCM)

✔ 유클리드 최대공약수(GCD)

수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다.

• a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같습니다. 즉 gcd(a, b) = gcd(b, a%b)입니다.
• 어떤 수와 0의최대공약수는 자기 자신입니다. 즉, gcd(n, 0) = n입니다.

ex)

1. 60과 24의 최대공약수
   gcd(60, 24) = gcd(24, 60%24) = gcd(24, 12) = gcd(12, 24%12) = gcd(12, 0) = 12
2. 81과 27의 최대공약수
   gcd(81, 27) = gcd(27, 81%27) = gcd(27, 0) = gcd(27, 0) = 27

a와 b의 최대공약수를 구하기 위해서 (a, b)보다 좀 더 작은 숫자인 (b, a%b)의 최대공약수를 구하는 과정을 이용하는 전형적인 재귀호출 문제입니다. (좀 더 작은 값으로 자기 자신을 호출합니다)

재귀 호출이 무한히 반복되지않도록 하는데 필요한 종료 조건은 '어떤 수와 0의 최대공약수는 자기 자신'입니다.
즉, b가 0이면 재귀 호출을 멈추고 결과를 돌려줍니다.

✔ 최소공배수(LCM)

최소공배수는 최대공약수 gcd를 이용하는 방법이 있다. 최대공약수와 다음과 같은 관계가 성립한다.

$$ lcm(a, b) = \frac{\vert ab \vert}{gcd(a, b)} $$

• gcd, lcm 구하기

  def solve(n, m):
    _max, _min = max(n, m), min(n, m)
    while _min:
        _max, _min = _min, _max % _min
    gcd, lcm = _max, int(n * m / _max)
    return [gcd, lcm]

📌 Reference

• 최소공배수 : 최소공배수 나무 위키