유클리드 호제법 개념과 구현

알고리즘 문제를 풀다가 최대공약수를 어떻게 구해야 하지? 하다가 유클리드 호제법을 간단히 정리해보았습니다.

유클리드 호제법

유클리드 호제법은 두 수가 있을 때 최대공약수를 구할 수 있는 알고리즘입니다. 알고리즘은 간단합니다.

a, b의 최대공약수를 구해야 할 때, a > b인 경우 n = a%b으로 지정합니다. 만약 n = 0 이라면 b가 최대공약수가 됩니다. 만약 n이 0이 아닐 경우, b와 n에 대해 동일한 연산을 반복하면 최대공약수를 찾을 수 있습니다.

유클리드 호제법 구현하기(Python)

유클리드 호제법은 재귀나 반복문을 통해서 간단히 구현할 수 있습니다.

재귀로 구현

def findGCD(a, b):
    if a < b:
        a, b = b, a

    rem = a % b
    if rem == 0:
        return b

    return findGCD(b, rem)

반복문으로 구현

def findGCD(a,b):
    while 1:
        if a < b:
            a, b = b, a
        n = a % b
        if n == 0:
            return b  

너무나도 유명한 알고리즘이지만,, 저처럼 모르고도 잘 사셨던 분들을 위하여 이 글을 바칩니다. 자세한 증명이 궁금하시다면 하단의 위키피디아에서의 정수에서의 유클리드호제법의 증명 부분을 보시면 좋을 것 같습니다. 그럼 이만 총총..

References

• https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#%EC%A6%9D%EB%AA%85