[Algorithm/Swift] 프로그래머스(Lv.1) - 최대공약수와 최소공배수

안녕하세요 제인입니다!!

오늘은 프로그래머스 문제를 풀다가 알게된 최대공약수, 최소공배수 구하는 방법에 대해 기록해보려고 합니다!

프로그래머스의 최대공약수와 최소공배수 문제는 레벨1의 간단한 문제이지만

최대공약수, 최소공배수를 구하는 공식(?)과 같은 개념을 알고있지 않다면 쉽게 풀 수 없는 문제이기 때문에 다른 문제들에서의 응용에 대비해 정리하고 넘어가려고 합니다!!

문제 링크

프로그래머스

문제 설명

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

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

 

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

문제 풀이

약수, 배수 구하기는 반복문을 사용하면 코드로도 간단하게 구현이 되기 때문에 이 문제도 쉽게 풀 수 있을 것이라고 생각했는데,

막상 두 수의 최대공약수와 최소공배수를 구하는 코드를 작성하려고 하니 어라라.. 코드가 엄청 복잡해지고..

뭔가 문제의 의도는 이게 아닌 것 같고..해서 풀이를 찾아보게 되었다.

 

먼저, 최대공약수는 유클리드 호제법을 이용해 구할 수 있습니다.

유클리드 호제법을 간단히 정리해보자면, 다음과 같습니다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b),
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

이 성질에 따라, b를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여

나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다!

이를 코드로 구현하면, a를 b로 나눈 나머지 값이 0일 때까지 반복되는 재귀함수 형태로 구현할 수 있습니다.

 

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

 

최소공배수는 최대공약수를 구했다면 최대공약수와 최소공배수의 관계를 이용해 쉽게 구할 수 있습니다!

최대공약수와 최소공배수의 관계는 다음과 같습니다.

두 자연수 A, B의 최대공약수가 G이고, 최소공배수가 L일 때,
A = a x G, B = b x G (a, b는 서로소) 라 하면 다음이 성립한다.
1) L = a x b x G
2) A x B = L x G

 

즉, 두 수를 곱한 값은 두 수의 최대공약수 x 최소공배수 와 같습니다!

a*b = 최대공약수 * 최소공배수를 활용해 코드로 구현해보면 아래와 같이 구현할 수 있습니다.

 

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

전체 코드

/// 최대공약수
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)]
}

 

---

 

[참고 자료]

https://ko.wikipedia.org/wiki/유클리드_호제법

https://hongjeongseob82.medium.com/ios-swift-gcd-lgm-최대공약수-최소공배수-49d57a36fda3

https://velog.io/@2dubu/Swift-알고리즘-최대공약수와-최소공배수