[Algorithm] 유클리드 호제법 (최대공약수, 최소공배수)

유클리드 호제법이란?

드디어 알고리즘을 공부하다가 처음 마주한 녀석이다. 두 양의 정수 최대공약수를 구하는 방법으로 유클리드 알고리즘이 있다. 아래의 설명이 가장 이해하기 쉬운것 같아서 가져왔다.

출처 : 나무위키

 

Swift로 구현하기

최대공약수를 영어로 하면 Greatest Common Divisor 이기 때문에 보통 GCD 라 한다. 결과값이 나올때까지 자기자신을 계속 사용하는 재귀함수를 구현하여 구할 수 있다. a > b 일 경우 a = bq + r 이기 때문에 r 을 a % b 로 구할 수 있어 반복이 가능하다. 만약 여기서 a < b 일 경우에도 b 가 0 이 되지 않기 때문에 결국 a < b 일 경우 gcd(a, b) = gcd(b, a) 로 결국 가기 때문에 고려할 필요가 없다.

func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        return gcd(b, a % b)
    }
}


// 더 짧은 버전
func gcd(_ a: Int, _ b: Int) -> Int {
    return b == 0 ? a : gcd(b, a % b)
}

 

최대공약수와 최소공배수의 관계

직접 손으로 쓴... 아래와 같다... 결국 최대공약수 x 최소공배수는 두 수를 곱한것과 같다!

따라서 최대공배수 LCD (Largest Common Multiple) 는 아래와 같이 구할 수 있다.

func lcd(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a, b)
}

 

유클리드 호제법 증명

아래는 증명법인데... 확실히 오랜만에 수학을 해서 그런지 어색하다.