[내일배움캠프] 데일리 루틴(iOS_3회차) - 최대공약수와 최소공배수

이미지를 클릭하면 코딩테스트 페이지로 이동합니다

 

내 풀이

/// 최대공약수
func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        return gcd(b, a % b)
    }
}

/// 최소공배수
func lcm(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a, b)
}

func solution(_ n:Int, _ m:Int) -> [Int] {
    return [gcd(n, m), lcm(n, m)]
}

 

 

gcd(_:_:) : 주어진 두 수의 최대공약수를 계산하는 함수

    유클리드 호제법을 사용하여 재귀적으로 최대공약수를 구함

    두 수 중 하나가 0이 될 때까지 나머지를 구하고, 0이 되면 다른 수가 최대공약수가 됨

lcm(_:_:) : 주어진 두 수의 최소공배수를 계산하는 함수

    최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같음

solution(_:_:) : 주어진 두 수의 최대공약수와 최소공배수를 배열에 담아 반환하는 함수

    이 함수 내에서 gcd(_:_:)와 lcm(_:_:) 함수를 호출하여 최대공약수와 최소공배수를 구한 뒤, 배열에 담아 반환

 

 

또 다른 풀이 

func solution(_ n:Int, _ m:Int) -> [Int] {
    let g = gcd(n,m)
    return [g, g * (n/g) * (m / g)]
}

func gcd(_ n:Int,_ m: Int)->Int {
    return n % m == 0 ? m : gcd(m, n % m)
}

 

gcd(_:_:) : 주어진 두 수의 최대공약수를 구하는 함수

    한 수가 다른 수로 나누어 떨어질 때까지 반복하여 최대공약수를 찾음 

solution(_:_:) : 먼저 gcd(n, m)을 호출하여 두 수의 최대공약수를 구함

    그 다음 최대공약수를 이용하여 최소공배수를 계산

    최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같음, 이를 통해 최소공배수를 반환

 

 

 

유클리드 호제법(Euclidean Algorithm)이란?

    두 개의 자연수의 최대공약수를 구하는 알고리즘

 

원리

1. 두 수 a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, a % b)
2. 두 수 중 하나가 0이면, 다른 수가 최대공약수가 된다. 즉, gcd(a, 0) = a

이 두 가지 원리를 이용하여 재귀적으로 최대공약수를 구하는 방법이 유클리드 호제법.

두 수의 크기가 매우 큰 경우에도 빠르게 최대공약수를 구할 수 있다.

 

최대공약수를 구하는 과정

1. 두 수 a와 b 중 큰 수를 a, 작은 수를 b로 지정한다.
2. b가 0이 될 때까지 a를 b로 나눈 나머지를 구한다.
3. b가 0이 되면, 이때의 a가 최대공약수가 된다.