이번 글에서는 자바를 이용한 코딩테스트에서 자주 출제되는 문제인 최소 공배수(Least Common Multiple, LCM)를 구하는 방법에 대해 깊이 있게 다루어보겠습니다. 최소 공배수는 두 개 이상의 수의 배수 중에서 가장 작은 수를 말하며, 다양한 알고리즘 문제에서 매우 중요한 역할을 합니다.
1. 문제 정의
다음은 최소 공배수를 구하는 문제의 간단한 정의입니다.
문제: 두 정수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하시오.
예시:
입력: a = 4, b = 6
출력: 12
2. 최소 공배수(L.C.M)란?
최소 공배수는 두 수의 배수 중에서 가장 작은 수를 의미합니다. 예를 들어, 4와 6의 배수는 다음과 같습니다:
- 4의 배수: 4, 8, 12, 16, 20, …
- 6의 배수: 6, 12, 18, 24, 30, …
위의 예시에서 4와 6의 배수 중 가장 작은 수는 12입니다. 따라서 12가 4와 6의 최소 공배수입니다.
3. 공약수와 공배수
최소 공배수를 이해하기 위해서는 먼저 최대 공약수(Greatest Common Divisor, GCD)에 대한 이해가 필요합니다. 최대 공약수는 두 수의 공통 약수 중에서 가장 큰 수를 의미합니다. 최소 공배수는 최대 공약수를 이용하여 다음과 같이 계산할 수 있습니다:
LCM(a, b) = (a * b) / GCD(a, b)
위의 공식을 사용하면 큰 수에 대해서도 빠르고 효율적으로 최소 공배수를 구할 수 있습니다.
4. 알고리즘 설계
최소 공배수를 구하는 알고리즘은 다음과 같이 설계할 수 있습니다:
- 두 정수 a와 b를 입력받는다.
- GCD(a, b)를 구한다.
- LCM(a, b)를 계산한다.
- 결과를 출력한다.
5. 자바 코드 구현
이제 자바코드를 통해 위의 알고리즘을 구현해 보겠습니다.
public class LCMCalculator {
// 최대 공약수(GCD) 계산 메서드
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 최소 공배수(LCM) 계산 메서드
public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
// 메인 메서드
public static void main(String[] args) {
int a = 4;
int b = 6;
int result = lcm(a, b);
System.out.println("최소 공배수: " + result);
}
}
5.1 코드 설명
위 코드의 동작 과정을 설명하겠습니다.
- gcd 메서드: 두 정수 a와 b를 입력받아 최대 공약수를 계산합니다. 유클리드 알고리즘을 사용해 효율적으로 GCD를 구합니다.
- lcm 메서드: 두 수의 최소 공배수를 구하는 메서드로, 앞서 설명한 GCD 공식을 적용합니다.
- main 메서드: 사용자가 입력한 두 수에 대해 최소 공배수를 계산하고 출력합니다.
6. 추가적인 예제와 테스트
이제 몇 가지 다른 입력에 대해서도 테스트해 보겠습니다. 다양한 테스트 케이스를 통해 코드의 신뢰성을 높일 수 있습니다.
예제 1
입력: a = 15, b = 20
출력: 60
예제 2
입력: a = 9, b = 12
출력: 36
예제 3
입력: a = 7, b = 5
출력: 35
7. 시간 복잡도 분석
위 알고리즘의 시간 복잡도는 다음과 같이 분석할 수 있습니다:
- 최대 공약수를 구하는 gcd 메서드는 O(log(min(a, b)))의 시간 복잡도를 가집니다.
- 따라서 전체 시간 복잡도는 O(log(min(a, b)))으로 매우 효율적입니다.
8. 결론
이번 강좌에서는 자바를 이용하여 최소 공배수를 구하는 알고리즘을 소개하였습니다. 알고리즘의 설계 뿐만 아니라, 구현 과정과 시간 복잡도 분석까지 다루었습니다. 코딩 테스트에서 자주 출제되는 문제이니 만큼 충분한 연습을 통해 실력을 키우길 바랍니다. 다음 강좌에서도 유용한 알고리즘을 다룰 예정이니 많은 기대 바랍니다!