재귀) 유클리드 호제법과 최대공약수, 최소공배수

목차

머리말

들어가기 전에

유클리드 호제법을 배워 보고 재귀적으로(recursively) 구현한 것과 반복적으로(iteratively) 구현한 것을 서로 비교해 보자.

재귀(Recursion)에 대한 개념이 궁금하다면?

본문

유클리드 호제법(Euclidean Algorithm)

이름도 어려운 호제법은 무엇일까? '호제(互除)'는 '서로 덜어낸다'는 뜻이다. '무엇을 덜어내냐' 하면 바로 '큰 수를 작은 수로 나눈 나머지'를 구하는 것이다. 또다시 기존의 작은 수는 큰 수가 되고, 구한 나머지는 작은 수가 되어 또 다른 나머지를 구한다.

1558년에 출판된 ≪유클리드의 원론(Euclid's Elements)≫. 그리스어와 라틴어로 출판되었다.

Mathematical Treasure: First Euclid's Elements in Greek and Latin | Mathematical Association of America

유클리드의 이름이 들어간 이유?

이름에 수학자 유클리드의 이름이 들어간 것은 그가 남긴 저서 《원론(Elements)》에 실제로 나오기 때문이다. 그 중 호제법은 제7권, 명제 1~3번에 나오며 역사상 가장 오래된 알고리즘으로 알려져 있다.

호제법을 이용한 최대공약수(GCD; greatest common divisor)

위의 호제법을 반복하여 최대공약수를 구할 수 있다.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.
유클리드 알고리즘은 큰 숫자를 큰 숫자와 작은 숫자와의 차이로 대체해도 두 수의 최대공약수는 변하지 않는다는 원칙을 기반으로 한다.

Euclidean algorithm - Wikipedia

알고리즘의 순서

큰 수를 $a$, 작은 수를 $b$, 나머지를 $r$이라 하자.

1. $a$와 $b$를 입력한다.
2. $a$를 $b$로 나누어 $r$를 구한다.
3. 다시 1번으로 돌아가 2번의 $b$는 큰 수가 되고, 2에서 구한 $r$는 작은 수가 된다.
4. 작은 수를 더 이상 나눌 수 없을 때까지 1~3번을 반복한다.
5. 4번의 경우가 되면 큰 수가 곧 최대공약수가 된다.
6. 최대공약수를 출력한다.

재귀적인 최대공약수(recursive GCD)

in Python

• 종료 조건(base case)은 작은 수 $n$이 $0$이 되었을 때 큰 수 $m$을 반환하는 것으로 한다.
• 재귀 단계(recursive steps)는 작은 수($n$)과 나머지($m \bmod n$)를 매개변수로 하여 다시 함수를 호출한다.

# 재귀적으로 해결하는 최대공약수 함수 정의
def gcd_recursive(a, b):
    # a, b 중 큰 값은 m으로, 작은 값은 n으로 할당
    m, n = max(a, b), min(a, b)
    if (n == 0):
        return m
    else:
        return gcd_recursive(n, m % n)

반복적인 최대공약수(iterative GCD)

in Python

반복은 while 문을 사용했다. 작은 수($n$)가 $0$이 될 때까지 나머지($m \bmod n$)를 구하는 것을 반복한다.

# 반복적으로 해결하는 최대공약수 함수 정의
def gcd_iterative(a, b):
    # a, b 중 큰 값은 m으로, 작은 값은 n으로 할당
    m, n = max(a, b), min(a, b)
    # 임시로 값을 할당할 변수 temp을 0으로 초기화
    temp = 0

    while (n != 0):
        temp = m % n
        m = n
        n = temp

    return m

최소공배수(LCM, least common multiple)

in Python

두 수를 곱한 뒤 최대공약수로 나눠주면 바로 최소공배수를 구할 수 있다.

# 최소공배수 함수 정의
def lcm(a, b):
    return int(a * b / gcd_iterative(a, b)) // int(a * b / gcd_recursive(a, b)) 또한 괜찮다.

 

수정일 2024-01-02