백준 2609번 (Python): 최대공약수와 최소공배수

백준 2609번 바로가기

우선 이 문제는 최대공약수와 최소공배수를 구하는 문제로 사칙연산과 약간의 수학적 지식(?)을 활용해 풀 수 있는 문제이다. 나는 곧 소개할 유클리드 호제법을 적용해서 문제 풀이를 하였는데 오답이 나왔다. 알고 보니 사소한 차이때문에 틀렸던 것이었다. 그래서 이번 글에선 백준 2609번을 소개하며 유클리드 호제법이란 무엇이고 왜 알고리즘을 적용했는데도 틀렸는지에 대해 정리해보았다.

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법 (Euclidean Algorithm)이란 두 정수 $a, b$의 최대공약수(GCD, Greatest Common Divisor)를 빠르게 구하는 방법으로 큰 수를 작은 수로 나눈 나머지를 이용하면 최대공약수를 구하는 문제를 점점 더 작은 수로 바꿀 수 있다.

유클리드 호제법의 원리는?

정수 $a,b(a≥b)$에 대해 다음이 항상 성립한다:

$gcd⁡(a,b) = gcd(b,\ a \mod\ b)$

• 여기서 $a  \ mod \b$는 $a$를 $b$로 나눈 나머지이다.
• 즉, 두 수의 최대공약수는 "작은 수와 나머지"의 최대공약수와 동일하다.
• 이 과정을 나머지가 0이 될 때까지 반복하면, 마지막에 남은 수가 최대공약수이다.

예시:

$gcd⁡(252,105)$를 구해봅시다.

1) $252÷105=2$, 나머지 $42$
→ $gcd⁡(252,105) = gcd⁡(105,42)$

2) $105÷42=2$, 나머지 $21$
→ $gcd⁡(105,42) = gcd⁡(42,21)$

3) $42÷21=2$, 나머지 $0$
→ 최대공약수는 21

유클리드로 풀었는데 왜 오답이었을까?

아래는 나의 오답 코드와 다른 사람들의 풀이를 보고 고친 정답 코드이다.
유클리드 호제법으로 잘 풀었다고 생각했던 내 코드는 무엇이 문제인지 오답처리가 됐고 고민 끝에 정답을 봐도 단번에 이해가 안됐었다.

# 오답

a, b = map(int, input().split())

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b / gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

# 정답

a, b = map(int, input().split())

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

위 두 코드의 차이점은 딱 1가지다.
일반 나눗셈(/) 연산자를 사용하였는가, 몫을 구하는 나눗셈(//)을 사용하였는가.

"일반 나눗셈(/)"과 "몫을 구하는 나눗셈(//)"의 차이점

파이썬에서는 네 가지의 나눗셈 연산자가 있다:

• / : 일반 나눗셈 → 항상 float
• // : 몫을 구하는 나눗셈 → 항상 int
• % : 나머지를 구하는 나눗셈
  → 입력이 둘 다 int이면 결과도 int, 하나라도 float면 float
• divmod(): 나눗셈의 몫과 나머지(튜플 형식)
  → 나눗셈 결과의 '몫'과 '나머지'를 한번에 가져옴

그 중 오늘 비교해 보려고 하는 것은 일반 나눗셈(/)과 몫을 구하는 나눗셈(//)이다.
아래 예시를 통해 일반 나눗셈은 출력값이 실수이고 몫을 구하는 나눗셈의 출력값은 정수로 출력되는 차이점을 확인할 수 있다.

# 예시
print(6 / 3)   # 2.0 (float)
print(6 // 3)  # 2   (int)

그래서 왜 "일반 나눗셈(/)" 이 틀렸을까?

만약 LCM 공식을 그대로 /로 구현하면:

def lcm(a, b):
    return a * b / gcd(a, b)

출력은 정수 값이 아니라 float이 된다.

예를 들어, lcm(24, 18)은 72.0가 나오게 되는데 수학적으로는 맞지만, 프로그래밍에서의 72.0와 72는 다르게 취급되기 때문에 오답 처리가 되는 것이다. 그래서 위의 사진처럼 예제 출력이 정수일 땐 정수로 출력되도록 //를 사용해야 한다!

더 쉬운 방법, "math" 모듈 사용하기

그런데 위에서 고민했던 것들이 무색하게 최대공약수/최소공배수를 구할 수 있는 내장 함수가 있다. 바로 math 모듈의 gcd(), lcm() 매서드를 사용하여 짧은 코드로도 구현할 수 있다.

import math

a, b = map(int, input().split())

print(math.gcd(a, b))
print(math.lcm(a, b))