[Algorithm] 유클리드 호제법 : 최대공약수, 최소공배수, 방정식의 해 구하기 - Python

문지은·2023년 6월 22일

algorithm python

Algorithm with Python

목록 보기

13/19

유클리드 호제법(Euclidean algorithm)

2개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

알고리즘

큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
단계 2를 반복하다가 나머지가 0이 되는 순간의 작은 수가 최대공약수이다.

그림으로 이해하기

270과 192의 최대공약수를 유클리드 호제법으로 찾아보자.

위에서 설명한 알고리즘대로 연산을 수행하면 270과 192의 최대 공약수는 6이 된다.

코드 작성하기

위에서 설명한 알고리즘을 Python 코드로 작성하면 다음과 같다.

# 최대공약수 구하기
def gcd(a, b):
    # b가 0이면 a가 최대 공약수
    if b == 0:
        return a
    else:
        #  a를 b로 나눈 나머지를 구하여 재귀호출
        return gcd(b, a % b)

a, b = map(int, input().split())  # 두 수 입력, a > b
result = gcd(a, b)

print(result)

math 모듈의 gcd 함수를 사용하면 최대공약수를 바로 구할 수도 있다.

from math import gcd

a, b = map(int, input().split())  # 두 수 입력
result = gcd(a, b)

print(result)

응용 1 - 최소 공배수 구하기

두 수의 최소 공배수(LCM; Least Common Multiple)가 두 수의 곱을 두 수의 최대공약수로 나눈 값임을 이용하면 유클리드 호제법을 이용하여 최소공배수를 구할 수 있다.

# 최대공약수 구하기
def gcd(a, b):
    # b가 0이면 a가 최대 공약수
    if b == 0:
        return a
    else:
        #  a를 b로 나눈 나머지를 구하여 재귀호출
        return gcd(b, a % b)
    
a, b = map(int, input().split())  # 두 수 입력, a > b

lcm = a * b // gcd(a, b)
print(lcm)

최대 공약수와 마찬가지로 math 모듈의 gcd 함수를 사용할 수도 있다.

from math import gcd

a, b = map(int, input().split())  # 두 수 입력

lcm = a * b // gcd(a, b)
print(lcm)

파이썬 3.9버전에는 최소공배수를 바로 구할 수 있는 lcm 함수도 추가되었다.

from math import lcm

a, b = map(int, input().split())  # 두 수 입력
result = lcm(a, b)

print(result)

응용 2 - 방정식의 해 구하기

알고리즘

해를 구하고자 하는 방정식이 ax + by = c(a, b, c, x, y 는 정수) 와 같을 때 방정식의 해 x, y 를 구하는 알고리즘은 다음과 같다.

유클리드 호제법을 이용하여 나머지가 0이 될 때 까지의 몫, 나머지를 저장한다.
반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y', y = x' - y' * q를 역계산한다.
➝ x'는 이전 x, y'는 이전 y를 의미하고 q는 현재 몫을 의미한다.
➝ 처음 시작하는 x, y는 이전 값이 없으므로 x', y'를 각각 1, 0으로 지정하여 역계산을 진행한다.
이렇게 재귀 방식으로 알아낸 최종 x, y는 ax + by = gcd(a, b)를 만족한다.
c / gcd(a, b) = K를 가정하면 최초 방정식의 해는 Kx, Ky가 된다.
➝ 만약 c가 최대공약수의 배수가 아니라면 방정식의 해를 구할 수 없다.

예시를 통해 이해하기

5x + 9y = 2 일 때 만족하는 정수 x, y를 구해보자.

STEP 0

조건을 정리하면 다음과 같다.

STEP 1

유클리드 호제법을 반복 실행하며 몫, 나머지를 저장한다.
반복은 나머지가 0이 되면 중단한다.

STEP 2

반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y', y = x' - y' * q를 역계산한다.
- x'는 이전 x, y'는 이전 y를 의미하고 q는 현재 몫을 의미한다.
- 처음 시작하는 x, y는 이전 값이 없으므로 x', y'를 각각 1, 0으로 지정하여 역계산을 진행한다.

이렇게 알아낸 최종 x = 2, y = -1은 ax + by = gcd(a, b)를 만족한다.

STEP 3

c / gcd(a, b) = K 를 가정하면 최초 방정식의 해를 구할 수 있다.
- 주어진 조건에서 c = 2, gcd(a, b) = 1 이므로 K = 2 이다.
따라서 해 Kx, Ky는 각각 2*2 = 4, 2 * (-1) = -2 가 된다.

코드 작성하기

위에서 설명한 알고리즘을 코드로 작성하면 다음과 같다.

a, b, c = map(int, input().split())  # ax + by = c 일 때 세 수 입력

# 유클리드 호제법을 이용한 최대 공약수 구하기
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def solve(a, b):
    result = [0] * 2  # x, y를 저장할 배열

    # x', y' 초기 값 설정
    if b == 0:
        result[0] = 1
        result[1] = 0
        return result
    
    q = a // b  # q = a를 b로 나눈 몫
    v = solve(b, a % b)  # 재귀 형태로 유클리드 호제법 수행

    # 역순으로 올라오며 x, y 계산
    result[0] = v[1]
    result[1] = v[0] - v[1] * q
    
    return result

# c가 최대공약수의 배수가 아니라면 방정식의 해를 구할 수 없음
if c % gcd(a, b) != 0:
    print(-1)
else:  # 방정식의 해 구하기
    k = int(c / gcd(a, b))
    ret = solve(a, b)
    x = k * ret[0]
    y = k * ret[1]
    print(x, y)