개요
해당 시리즈에서는 코딩테스트를 통해 알고리즘을 학습하며 기록이 필요하다고 느껴지는 문제들을 정리해 포스팅 해보려합니다. 🥳
문제 '최대공약수와 최소공배수'는 간단한 문제이지만 해결하는 데 생각보다 많은 시간이 소요되었고, 나중에 고난이도 문제에서 충분히 응용할 수 있는 개념이라 생각되어 포스팅하게 되었습니다!
문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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]을 리턴해야 합니다.
Solution 및 풀이
두 자연수 a와 b의 최대공약수와 최소공배수는 특별한 관계가 있습니다.
바로 두 자연수 ab = 최대공약수 * 최소공배수이기 때문입니다.
따라서 최대공약수와 최소공배수 중 하나의 값만 구한다면 나머지 값은 쉽게 구할 수 있습니다.
최대공약수는 유클리드 호제법을 통해 쉽게 구할 수 있습니다.
유클리드 호제법은 A를 B로 나눈 몫을 Q라 하고, 나머지를 R이라 했을 때 이 때, A,B의 최대공약수는 B,R의 최대공약수와 같다는 정수론으로, 프로그래밍에서 자주 사용된다고 합니다.
그래서 다음과 같이 A와 B값이 주어지면 A값을 B로 나눈 나머지값이 0일때까지 루프를 도는 재귀함수 형태로 gcd(_a: Int, _b: Int) 라는 함수를 통해 최대공약수를 구한 후, 앞서 말한 ab = 최대공약수 * 최소공배수 를 활용해 최대공배수까지 구해주었습니다.
/// 최대공약수
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)]
}더 많은 풀이를 보고 싶다면 이곳으로 놀러오세요! 아직은 부족하지만 알고리즘 공부를 시작하시는 분들에게 많은 도움이 되었으면 좋겠어요. :)
글 읽어주셔서 감사합니다. 😊
질문과 지적은 편하게 남겨주세요!
