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

🖥 문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.
배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.
예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

🤔 풀이 방법

유클리드 호제법으로 최대공약수 구하기

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.
2개의 자연수 n, m에 대해서 n를 m로 나눈 나머지를 r이라 하면, n과 m의 최대공약수는 m과 r의 최대공약수와 같다.
이를 이용하여 m을 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 n과 m의 최대공약수이다.

• 1071과 1029의 최대공약수를 구하면,
  1. 1071 % 1029 = 42
  2. 1029 % 42 = 21
  3. 42 % 21 = 0
     따라서, 최대공약수는 21
• 78696과 19332의 최대공약수를 구하면,
  1. 78696 % 19332 = 1368
  2. 19332 % 1368 = 180
  3. 1368 % 180 = 72
  4. 180 % 72 = 36
  5. 72 % 36 = 0
     따라서, 최대공약수는 36

최소공배수 구하기

n과 m의 최소공배수는 n과 m을 곱한 수를 최대공약수로 나누면 구할 수 있다.
식으로 표현하면 최소공배수 = n * m / 최대공약수 이다.

👩🏻‍💻 Swift Code

func solution(_ n:Int, _ m:Int) -> [Int] {
    var gcd = 0
    var lcm = 0    
    var num1 = max(n, m)
    var num2 = min(n, m)
    var r = num1 % num2

    while num1 % num2 != 0 {
        r = num1 % num2
        num1 = num2
        num2 = r
    }

    gcd = num2
    lcm = n * m / gcd

    return [gcd, lcm]
}

 

코딩테스트 연습 - 최대공약수와 최소공배수