유클리드 호제법

유클리드 호제법

최대공약수를 구하는 알고리즘 내가 처음으로 단순 문제 풀이가 아니라 어떤 식으로 접근해서 풀어야 되는지 생각해본 알고리즘

개요

gcd(a,b)가 있다. 여기서 gcd(a,b)는 a와 b의 최대공약수이다.

a = bq + r 라고 하면 아래식이 성립한다.

gcd(a,b) = gcd(b,r)

증명

a = gcd(a,b) * x

b = gcd(a,b) * y

r = a - bq = gcd(a,b)*x - gcd(a,b)*y*q   
= gcd(a,b)(x-y*q)

여기서 r은 a와 b의 최대공약수의 배수라는 것을 알 수 있다. 여기서 a>r이기 때문에 b와 r의 공약수가 gcd(a,b)이외에 더 큰 공약수가 나올 수 없다. 따라서 gcd(a,b) = gcd(b,r)이 성립한다. 이제 이 문제를 코드로 변환해보자.

코드

최대공약수를 구하기 위해서는 gcd(a,b) = gcd(b,r) 임을 이용해 반복해서 호출하여 r이 0이 되는 시점을 찾아야 한다. 이를 재귀함수로 구현해봤다.

func gcd(a int, b int) int{
    if b == 0 {     //b(r)이 0이 되는 시점에 리턴
        return a    //여기서 리턴된 a값이 최대 공약수다.
    }
    return gcd(b,a%b)   //0이되는 시점을 찾을 때 까지 재귀
}

gcd(b,r)에서 r은 위에서 식을 보면 유추할 수 있듯이 a를 b로 나눈 나머지이다. 따라서 %연산으로 나머지룰 구해줘서 대입해주면된다.

최소공배수

최소공배수는 최대공약수를 구해주면 쉽게 구할 수 있다. (최소공배수) = a*b/(최대공약수)

func lcm(a int, b int) int{
    g := gcd(a,b)
    return a*b/g
}

끝