최대공약수와 최소공배수 (GCD, LCM)

구현 코드 예시

def gcd(a, b):
    """유클리드 호제법 — 반복문 버전."""
    while b:
        a, b = b, a % b
    return a


def gcd_recursive(a, b):
    """재귀 버전. 한 줄이면 끝난다."""
    return a if b == 0 else gcd_recursive(b, a % b)


def lcm(a, b):
    return a // gcd(a, b) * b        # 나눗셈 먼저 — 오버플로 방지


# 여러 수의 GCD와 LCM은 두 개씩 접어 나가면 된다
from functools import reduce

def gcd_all(nums):
    return reduce(gcd, nums)

def lcm_all(nums):
    return reduce(lcm, nums)

파이썬은 표준 라이브러리가 이미 제공한다. 실전에서는 직접 구현하지 말고 이쪽을 쓰는 편이 안전하고 빠르다.

import math

math.gcd(48, 18)         # 6
math.lcm(24, 18)         # 72   (Python 3.9+)
math.gcd(12, 18, 24)     # 6    — 인자 여러 개 가능 (Python 3.9+)

어디에 쓰이는가

• 기약분수 만들기: 분자와 분모를 gcd로 나눈다. 분수 연산 문제의 마무리에 항상 등장한다.
• 주기가 겹치는 시점: 3일마다, 5일마다 오는 두 사건이 다시 같은 날 겹치는 것은 lcm(3, 5) = 15일 후다.
• 격자점 개수: 원점에서 (a, b)로 가는 선분 위의 격자점은 gcd(a, b) + 1개다.
• 비율 비교: 두 비율이 같은지 판단할 때 각각 기약분수로 만들어 비교한다.
• 여러 수를 같은 크기로 나누기: "가능한 큰 같은 크기로 나눠 담기" 유형이 곧 gcd다.

자주 하는 실수

• LCM에서 곱셈을 먼저 한다. a * b가 자료형 범위를 넘을 수 있다. 파이썬은 안전하지만 C++·자바로 옮길 때 바로 문제가 된다. 습관적으로 나눗셈을 먼저 쓴다.
• a와 b의 순서를 신경 쓴다. gcd(18, 48)도 정상 동작한다. 첫 단계에서 18 % 48 = 18이 되어 자동으로 자리가 바뀐다. 미리 정렬할 필요가 없다.
• 0을 처리하지 않는다. gcd(a, 0) = a가 정의상 맞고 위 코드도 그렇게 동작한다. 하지만 lcm(a, 0)은 0으로 나누기가 되어 터진다. 0이 들어올 수 있는 문제라면 따로 막아야 한다.
• 음수를 그대로 넣는다. 파이썬의 %는 음수에서 부호가 달라 결과가 이상해진다. abs()를 씌우고 시작한다.
• 소인수분해로 구현한다. 동작은 하지만 O(√n)이라 훨씬 느리고 코드도 길다. 호제법을 두고 돌아갈 이유가 없다.

면접에서 이렇게 물어본다

• 유클리드 호제법의 원리, 즉 gcd(a, b) = gcd(b, a % b)가 성립하는 이유를 설명해 보라.
• 호제법의 시간 복잡도가 로그인 이유는 무엇인가.
• 최소공배수를 최대공약수로 구하는 공식을 유도해 보라.
• LCM 계산에서 오버플로를 피하는 방법은 무엇인가.
• 세 개 이상의 수에 대한 GCD는 어떻게 구하는가.
• 소인수분해로 구하는 방법과 비교했을 때 호제법의 장점은 무엇인가.