최대공약수

두 수 a와 b의 최대공약수(Greatest Common Divisor 또는 Greatest Common Factor)는 a와 b를 나머지 없이 나눌 수 있는 가장 큰 양의 정수다. GCD.swift 파일에는 최대공약수를 계산하는 세 가지 알고리즘이 포함되어 있다.

예를 들어, gcd(39, 52) = 13인데, 이는 13이 39(39 / 13 = 3)와 52(52 / 13 = 4)를 모두 나누기 때문이다. 하지만 13보다 큰 수로는 둘 다 나눌 수 없다.

학교에서 이 개념을 배운 기억이 있을 것이다. :-)

실제 문제에서 최대공약수나 최소공배수를 사용할 일은 거의 없지만, 이 고대 알고리즘을 가지고 놀아보는 것은 재미있다. 이 알고리즘은 기원전 300년경 유클리드가 그의 저서 Elements에서 처음 설명했다. 소문에 따르면 그는 Commodore 64를 해킹하던 중 이 알고리즘을 발견했다고 한다.

다양한 알고리즘

이 예제는 동일한 결과를 얻기 위해 세 가지 다른 알고리즘을 포함한다.

반복적 유클리드 알고리즘

두 수의 최대공약수(GCD)를 찾는 번거로운 방법은 먼저 두 수의 약수를 구한 다음, 공통으로 가지는 가장 큰 수를 찾는 것이다. 문제는 수를 인수분해하는 것이 상당히 어렵다는 점이다. 특히 수가 커질수록 더욱 어려워진다. (반면, 이 어려움이 온라인 결제를 안전하게 유지하는 데 기여한다.)

최대공약수를 계산하는 더 똑똑한 방법이 있다. 바로 유클리드 알고리즘이다. 핵심 아이디어는 다음과 같다.

gcd(a, b) = gcd(b, a % b)

여기서 a % b는 a를 b로 나눈 나머지를 계산한다.

이 아이디어를 Swift로 구현한 코드는 다음과 같다.

func gcdIterativeEuklid(_ m: Int, _ n: Int) -> Int {
    var a: Int = 0
    var b: Int = max(m, n)
    var r: Int = min(m, n)

    while r != 0 {
        a = b
        b = r
        r = a % b
    }
    return b
}

플레이그라운드에 이 코드를 넣고 아래 예제로 테스트해 보자.

gcd(52, 39, using: gcdIterativeEuklid)        // 13
gcd(228, 36, using: gcdIterativeEuklid)       // 12
gcd(51357, 3819, using: gcdIterativeEuklid)   // 57

재귀적 유클리드 알고리즘

유클리드 알고리즘을 조금 다르게 구현한 버전이다. 이전 버전과 달리 while 루프를 사용하지 않고 재귀를 활용한다.

func gcdRecursiveEuklid(_ m: Int, _ n: Int) -> Int {
    let r: Int = m % n
    if r != 0 {
        return gcdRecursiveEuklid(n, r)
    } else {
        return n
    }
}

이 코드를 플레이그라운드에 넣고 반복적 유클리드 알고리즘과 결과를 비교해 보면 동일한 결과를 반환한다.

gcd(52, 39, using: gcdRecursiveEuklid)        // 13
gcd(228, 36, using: gcdRecursiveEuklid)       // 12
gcd(51357, 3819, using: gcdRecursiveEuklid)   // 57

함수 상단의 max()와 min()은 항상 큰 수를 작은 수로 나누도록 보장한다.

세 번째 예제를 재귀적 유클리드 알고리즘으로 단계별로 살펴보자.

gcd(51357, 3819)

유클리드 규칙에 따르면 이는 다음과 동일하다.

gcd(3819, 51357 % 3819) = gcd(3819, 1710)

51357 % 3819의 나머지는 1710이기 때문이다. 이 나눗셈을 계산하면 51357 = (13 * 3819) + 1710이 되지만, 우리는 나머지 부분만 관심이 있다.

따라서 gcd(51357, 3819)는 gcd(3819, 1710)와 같다. 이는 계속 단순화할 수 있다.

gcd(3819, 1710) = gcd(1710, 3819 % 1710) =
gcd(1710, 399)  = gcd(399, 1710 % 399)   =
gcd(399, 114)   = gcd(114, 399 % 114)    =
gcd(114, 57)    = gcd(57, 114 % 57)      =
gcd(57, 0)

이제 더 이상 나눌 수 없다. 114 / 57의 나머지는 114 = 57 * 2이므로 0이다. 이는 답을 찾았다는 의미다.

gcd(3819, 51357) = gcd(57, 0) = 57

유클리드 알고리즘의 각 단계에서 숫자가 점점 작아지고, 어느 시점에서 하나가 0이 되면 종료된다.

참고로 두 숫자의 GCD가 1일 수도 있다. 이를 서로소라고 한다. 두 숫자를 모두 나누는 수가 없을 때 발생한다. 예를 들어:

gcd(841, 299)     // 1

이진 재귀 스타인 알고리즘

이진 GCD 알고리즘은 스타인 알고리즘으로도 알려져 있다. 이 알고리즘은 두 개의 음이 아닌 정수의 최대공약수를 계산한다. 스타인 알고리즘은 재귀적인 유클리드 알고리즘과 매우 유사하지만, 일반적인 유클리드 알고리즘보다 컴퓨터가 수행하기 더 간단한 산술 연산을 사용한다. 이 알고리즘은 나눗셈 대신 산술 시프트, 비교, 뺄셈을 활용한다.

func gcdBinaryRecursiveStein(_ m: Int, _ n: Int) -> Int {
    if let easySolution = findEasySolution(m, n) { return easySolution }

    if (m & 1) == 0 {
        // m이 짝수일 때
        if (n & 1) == 1 {
            // n이 홀수일 때
            return gcdBinaryRecursiveStein(m >> 1, n)
        } else {
            // m과 n이 모두 짝수일 때
            return gcdBinaryRecursiveStein(m >> 1, n >> 1) << 1
        }
    } else if (n & 1) == 0 {
        // m이 홀수이고 n이 짝수일 때
        return gcdBinaryRecursiveStein(m, n >> 1)
    } else if (m > n) {
        // 더 큰 인수를 줄일 때
        return gcdBinaryRecursiveStein((m - n) >> 1, n)
    } else {
        // 더 큰 인수를 줄일 때
        return gcdBinaryRecursiveStein((n - m) >> 1, m)
    }
}

애플리케이션과 입력 예상치에 따라, 다른 GCD 구현을 사용해 "쉬운 해결책"을 찾는 것도 합리적일 수 있다:

func findEasySolution(_ m: Int, _ n: Int) -> Int? {
    if m == n {
        return m
    }
    if m == 0 {
        return n
    }
    if n == 0 {
        return m
    }
    return nil
}

이 코드를 플레이그라운드에 넣고 다른 GCD 구현과 결과를 비교해 보자:

gcd(52, 39, using: gcdBinaryRecursiveStein)        // 13
gcd(228, 36, using: gcdBinaryRecursiveStein)       // 12
gcd(51357, 3819, using: gcdBinaryRecursiveStein)   // 57

최소공배수

GCD와 관련된 또 다른 알고리즘은 최소공배수(Least Common Multiple, LCM)이다.

두 수 a와 b의 최소공배수는 두 수 모두의 배수인 가장 작은 양의 정수를 의미한다. 즉, LCM은 a와 b로 나누어 떨어지는 가장 작은 수이다. LCM 구현 예제는 두 수와 사용할 GCD 알고리즘을 선택적으로 지정할 수 있다.

예를 들어: lcm(2, 3, using: gcdRecursiveEuklid) = 6은 6이 2와 3으로 나누어 떨어지는 가장 작은 수임을 나타낸다.

LCM은 유클리드 알고리즘을 사용해 계산할 수 있다:

a * b
lcm(a, b) = ---------
gcd(a, b)

코드로 구현하면 다음과 같다:

func lcm(_ m: Int, _ n: Int, using gcdAlgorithm: (Int, Int) -> (Int) = gcdIterativeEuklid) throws -> Int {
    guard (m & n) != 0 else { throw LCMError.divisionByZero }
    return m / gcdAlgorithm(m, n) * n
}

플레이그라운드에서 테스트해보면:

lcm(10, 8)    // 40

토론

이 알고리즘들은 모두 동일한 결과를 계산하지만, 단순히 평면 복잡도를 비교하는 것만으로는 어떤 알고리즘을 선택할지 결정하기에 충분하지 않다. 기존의 반복적 유클리드 알고리즘은 이해하기 쉽다. 반면 재귀적 유클리드 알고리즘과 스타인 알고리즘은 일반적으로 더 빠르지만, 실행 시간은 실행 환경에 크게 의존한다.

최대공약수를 빠르게 계산해야 한다면, 재귀적 유클리드 알고리즘과 스타인 알고리즘에 대해 특정 플랫폼과 컴파일러 최적화 수준에서 실행 시간을 비교해야 한다.

Swift Algorithm Club을 위해 Matthijs Hollemans가 작성함

Simon C. Krüger가 추가 작성함