유클리드 호제법(Euclidean Algorithm)

1.최대공약수 (GCD, Greatest Common Divisor - 유클리드 호제법)

핵심 원리

두 수 $A$와 $B$가 있을 때($A > B$), $A$를 $B$로 나눈 나머지를 $R$이라고 합시다. "$A$와 $B$의 최대공약수는, $B$와 $R$의 최대공약수와 같다"는 것이 유클리드 호제법의 핵심입니다. 나머지($R$)가 0이 될 때까지 이 과정을 반복하면, 그때 나누는 수가 바로 최대공약수가 됩니다.

파이썬 구현 (반복문)

재귀함수 제한을 걱정할 필요가 없어서 가장 권장되는 구현 방식입니다.

pythondef gcd(a, b):
    # b가 0이 될 때까지 반복
    while b > 0:
        a, b = b, a % b  # a에는 b를 넣고, b에는 'a를 b로 나눈 나머지'를 넣음
    return a

print(gcd(48, 18))  

6

파이썬 구현 (재귀함수)

코드가 훨씬 짧아서 외워두고 쓰기 좋습니다.

pythondef gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

2. 최소공배수 (LCM, Least Common Multiple)

최소공배수는 방금 구한 최대공약수를 이용하면 단 1줄만에 구할 수 있습니다.

• 공식: 두 수 $A$와 $B$의 곱을 최대공약수로 나누면 최소공배수가 됩니다.
• $LCM = (A \times B) / GCD(A, B)$

pythondef lcm(a, b):
    # a * b를 앞서 만든 gcd(a,b)로 나눈 몫
    return (a * b) // gcd(a, b)

print(lcm(48, 18))  

144

3. 파이썬 내장 함수 (가장 추천)

알고리즘 원리를 이해하셨다면, 실전(코딩 테스트)에서는 굳이 직접 구현하지 마시고 파이썬의 math 라이브러리 를 쓰시는 것이 가장 빠르고 안전합니다.

pythonimport math

print(math.gcd(48, 18)) # 최대공약수 (GCD)  

6

pythonimport math

# 여러 숫자의 최대공약수도 한 번에 가능 (Python 3.9 이상)
print(math.gcd(48, 18, 24))  

6

pythonimport math

# 최소공배수 (LCM) (Python 3.9 이상)
print(math.lcm(48, 18))

144