최대공약수와 최소공배수(feat. 유클리드 호제법)

문제

 

코드

func solution(_ n:Int, _ m:Int) -> [Int] {
    func gcd(_ a: Int, _ b: Int) -> Int {
        let mod: Int = a % b
        return 0 == mod ? min(a, b) : gcd(b, mod)
    }
    func lcm(_ a: Int, _ b: Int) -> Int {
        return a * b / gcd(a, b)
    }
    return [gcd(n, m), lcm(n, m)]
}

해석

유클리드 호제법을 사용하여 두 수의 최대공약수(GCD)와 최소공배수(LCM)을 찾자. 

1. gcd(_ a: Int, _ b: Int) -> Int: 이 함수는 두 수의 최대공약수를 찾는 역할을 합니다. 유클리드 호제법을 사용하여, 두 수의 나머지를 계속해서 구하면서, 나머지가 0이 될 때까지 반복합니다. 나머지가 0이 되면, 그때의 나누는 수가 최대공약수입니다.

2. lcm(_ a: Int, _ b: Int) -> Int: 이 함수는 두 수의 최소공배수를 찾는 역할을 합니다. 두 수를 곱한 후 최대공약수로 나누면 최소공배수를 얻을 수 있습니다. 이유는 두 수의 곱이 최대공약수와 최소공배수의 곱과 같기 때문입니다.

3. solution(_ n:Int, _ m:Int) -> [Int]: 이 함수는 위의 두 함수를 사용하여 두 수의 최대공약수와 최소공배수를 배열 형태로 반환합니다. 이때, 배열의 첫 번째 요소는 최대공약수, 두 번째 요소는 최소공배수입니다.

4. 예를 들어, solution(3, 12)를 호출하면, gcd(3, 12)는 3을, lcm(3, 12)는 12를 반환하므로, 최종적으로 [3, 12]가 반환됩니다. 이는 문제에서 요구하는 결과와 일치합니다.