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

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

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

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

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

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

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

삽입정렬(Insertion sort) 개념 이해하고 구현하기 (0)	2021.11.02
Binary Search, Parametric Search 이해하기 (0)	2021.07.03

dev-log