스위프트 코딩테스트 강좌, 최소 공배수 구하기

문제 설명

두 개의 정수 A와 B가 주어졌을 때, 이 두 수의 최소 공배수(Lowest Common Multiple, LCM)를 구하는 프로그램을 작성하시오.

예제

입력: A = 12, B = 18
출력: LCM = 36

문제 풀이 과정

1. 최소 공배수 정의

최소 공배수는 주어진 두 수 A와 B의 공통된 배수 중에서 가장 작은 수를 의미합니다.
LCM을 구하는 공식은 다음과 같습니다:

LCM(A, B) = |A * B| / GCD(A, B)

여기서 GCD는 최대 공약수(Greatest Common Divisor)로, 두 수 A와 B의 공약수 중 가장 큰 수입니다.

2. 알고리즘 접근 방식

최소 공배수를 효율적으로 구하기 위해 최대 공약수를 먼저 구한 후, 위의 LCM 공식을 적용할 수 있습니다.
GCD를 구하는 알고리즘으로는 유클리드 알고리즘을 사용하며, 이는 빠르고 효율적입니다.

유클리드 알고리즘 설명

두 수 A와 B의 GCD를 구하기 위해 다음과 같은 과정을 반복합니다:

두 수 A와 B에서 더 작은 수를 B라고 하고, A를 B로 나눕니다.
B를 A와 B의 나머지로 업데이트합니다.
B가 0이 될 때까지 이 과정을 반복하면, A가 GCD입니다.

3. 스위프트 코드 구현

이제 스위프트 프로그래밍 언어를 사용하여 최소 공배수를 구하는 코드를 구현해보겠습니다.

import Foundation

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

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

// 테스트 예제
let A = 12
let B = 18
let result = lcm(A, B)
print("LCM(\(A), \(B)) = \(result)") // LCM(12, 18) = 36

4. 코드 설명

– gcd 함수는 두 개의 정수 A와 B를 매개변수로 받고, 유클리드 알고리즘을 통해 최대 공약수를 구합니다.
– lcm 함수는 두 수 A와 B의 곱을 GCD로 나누어 최소 공배수를 계산합니다.

5. 추가 테스트

여러 다른 수에 대해서도 테스트하여 코드가 잘 작동하는지 확인하세요.


let testCases = [(12, 18), (4, 5), (6, 8), (15, 25)]
for (num1, num2) in testCases {
    let result = lcm(num1, num2)
    print("LCM(\(num1), \(num2)) = \(result)")
}

결론

이번 강좌에서는 최소 공배수(LCM)를 구하는 방법에 대해 알아보았습니다. 유클리드 알고리즘을 통해 최대 공약수를 구한 후, LCM을 계산하는 방식을 배웠습니다.
다양한 숫자에 대해 함수를 테스트하고, 자주 사용하는 수학적 개념이기 때문에 알고리즘을 자주 활용하여 연습하는 것이 중요합니다.