TIL - 최대공약수(GCD) 와 최소공배수(LCM), 확장 유클리드 호제법

문제

두 정수의 최대공약수와 최소공배수를 구합니다. 유클리드 호제법을 사용하여 GCD 를 효율적으로 계산합니다.

 

문제풀이

유클리드 호제법

유클리드 호제법은 한번 정리하긴 했었는데, 원리는 모르고 있던 터라 다시한번 정리해봤다. 

 

[Java] 백준1934 최대공약수와 최소공배수 구하기 : 유클리드 호제법

 

우선 왜 유클리드 호제법이 최대공약수가 되는지는 타일링을 통해 이해하였다. 두 수 중 작은 값으로 큰 값을 채우고, 남은 값들을 채우고 남은 값들을 채우면, 다 채워졌을 때의 타일은 큰 타일들도 채울 수 있다.

 

euclid_tiles.html

0.01MB

 

 

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

 

코드로는 이렇게 구현한다. Recursive 재귀 함수를 이용해 구현하였다. b 가 0이 될 때까지 나머지를 구한다.

 

[알고리즘] 재귀함수(Recursion Function)

 

 

 

반복문을 이용한 최대공약수 계산

def gcd_iterative(a, b):
    while True:
        if b != 0:
            a, b = b, a % b

        elif b == 0:
            return a

 

파이썬에서는 a,b = b,a 이런식으로 값을 교환할 수 있어서 temp 변수가 필요없다. b 가 0 이 될때까지 반복하도록 하였다.

 

 

 

최소공배수(LCM) 계산

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

 

최소공배수는 (a * b) // gcd 로 구한다. 

[Java] 백준1934 최대공약수와 최소공배수 구하기 : 유클리드 호제법

 

 

 

확장 유클리드 호제법

확장 유클리드 호제법은 ax + by = gcd(a,b) 를 만족하는 x, y 를 찾는것이다. 

 

gcd(7,5) => 7 = 5 * 1 + 2 => 2 = 7 - 5 * 1
		=> 5 = 2 * 2 + 1 => 5 = 2 * (7 - 5 * 1) + 1
        => 2 = 1 * 2 + 0

 

처음에 위와 같이 했었는데, ax + by = gcd 형태를 숫자로까지는 도달했다. 그런데 수식을 도저히 도출해낼 수 없어서, 같은 팀원 분의 도움을 받아 아래와 같이 정리하였다. 정말 이해가 쏙쏙 되는 !

 

이해가 어렵다면, 최초로는 숫자로 해보고 숫자에 해본 것처럼 수식을 대입해보면 될 것 같다. 나는 나온 숫자 결과를 가지고 대입하려해서 안된 것 같다.

 

gcd(a,b) = gcd(b, a % b)

ax + by = gcd(a, b)
		= gcd(b, a % b)

# 이전의 b, a%b 값을 대입 (이때, x, y 도 기존과는 다른 값으로 변경됨)
bx' + (a % b)y' = gcd 
# (a % b) = (a - b(a // b))
# a // b = a 를 b 로 나눈 값의 몫이다.
bx' + (a - b(a // b))y' = gcd 

# ax + by 구조로 변경하면 아래와 같다.
ay' + b(x' - (a // b)y') = gcd
x = y'
y = x' - (a // b) y'

 

 

코드로 구현하면 아래와 같이 나온다.

 

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0

    gcd, x, y = extended_gcd(b, a % b)    
    return gcd, y , x - (a // b) * y

 

 

확장 유클리드 호제법은 모듈러 역원, 일차 부정방정식 등에서 사용한다.

 

 

 

 

 

어려웠던 점

1. 아무래도 확장 유클리드 호제법이 어렵다. 관련된 문제를 많이 풀어봐야 할 것 같다.