코딩테스트에서 자주 출제되는 알고리즘 문제 중 하나는 ‘최소 공배수(Least Common Multiple, LCM)’를 구하는 문제입니다. 최소 공배수는 두 수에서 각각의 배수를 구했을 때, 가장 작은 공통의 배수를 의미합니다. 이 글에서는 최소 공배수를 구하는 알고리즘을 코틀린으로 구현해보겠습니다.
문제 설명
정수 두 개 𝑎와 𝑏가 주어질 때, 이 두 수의 최소 공배수를 구하는 함수를 작성해주세요. 함수의 시그니처는 다음과 같습니다:
fun lcm(a: Int, b: Int): Int예를 들어, 4와 6의 최소 공배수는 12이며, 15와 20의 최소 공배수는 60입니다. 입력 범위는 1 부터 106 사이의 정수입니다.
최소 공배수 구하기
최소 공배수는 두 수의 곱을 최대 공약수(Greatest Common Divisor, GCD)로 나누어 계산할 수 있습니다. 최소 공배수는 다음과 같은 식으로 정의됩니다:
LCM(a, b) = (a * b) / GCD(a, b)위의 식을 사용하여 최소 공배수를 계산하기 위해서는 먼저 두 수의 최대 공약수를 구해야 합니다. 이를 위해 유클리드 호제법(Euclidean algorithm)을 사용할 수 있습니다.
유클리드 호제법 설명
유클리드 호제법은 두 수의 최대 공약수를 구하는 효율적인 방법입니다. 두 수 𝑎와 𝑏에 대해, 𝑏가 0이 아닐 때는 다음과 같이 진행합니다:
- 𝑎를 𝑏로 나눈 나머지를 구합니다.
- 𝑏를 𝑎에 대입합니다.
- 나머지를 𝑎에 대입합니다.
- 𝑏가 0이 될 때까지 반복합니다.
마지막으로 𝑎의 값을 최대 공약수로 반환합니다.
코틀린 구현
이제 위의 알고리즘을 기반으로 코틀린에서 최소 공배수를 계산하는 함수를 구현해보겠습니다.
fun gcd(a: Int, b: Int): Int {
return if (b == 0) a else gcd(b, a % b)
}
fun lcm(a: Int, b: Int): Int {
return (a * b) / gcd(a, b)
}
fun main() {
val a = 4
val b = 6
println("최소 공배수: ${lcm(a, b)}") // 출력: 최소 공배수: 12
}함수 설명
위의 코드는 두 가지 함수를 포함하고 있습니다:
gcd(a: Int, b: Int): Int– 최대 공약수를 계산하는 함수입니다. 0이 될 때까지 나머지를 반복적으로 계산합니다.lcm(a: Int, b: Int): Int– 두 수의 곱을 최대 공약수로 나누어 최소 공배수를 계산하는 함수입니다.
복잡도 분석
유클리드 호제법의 시간 복잡도는 O(log min(a, b))입니다. 이는 두 수의 크기에 따라 훨씬 빠르게 최대 공약수를 계산할 수 있는 방법이 됩니다. 따라서, 최소 공배수를 구하는 전체 알고리즘의 시간 복잡도 또한 O(log min(a, b))입니다.
테스트 케이스
작업이 제대로 이루어졌는지 확인하기 위해 몇 가지 테스트 케이스를 살펴보겠습니다:
- lcm(4, 6): 12
- lcm(15, 20): 60
- lcm(7, 5): 35
- lcm(1, 999999): 999999
- lcm(123456, 789012): 493827156
각 함수의 결과를 통해 로직의 정확성을 검증할 수 있습니다.
결론
코틀린을 사용하여 최소 공배수를 구하는 문제를 해결하는 방법을 배워보았습니다. 유클리드 호제법을 통해 최대 공약수를 효율적으로 계산하고, 이를 활용하여 최소 공배수를 구하는 과정을 살펴보았습니다. 이와 같은 알고리즘은 코딩테스트에서 빈번히 출제되므로, 반드시 숙지하고 연습하는 것이 좋습니다.