정의
두 수(또는 여러 수)가 공통으로 가지는 배수 중 가장 작은 양의 정수입니다.
최소 공배수는 “배수를 나열해서 찾는 문제”처럼 보이지만, 실제 구현은 GCD(최대공약수)를 유클리드 호제법으로 빠르게 구한 뒤 수학적 관계식을 적용해 로그 시간에 해결합니다.
예를 들어 12와 18의 공통 배수는 36, 72, 108... 이고, 그 중 가장 작은 공통 배수는 36입니다.
예를 들어 12와 18의 공통 배수는 36, 72, 108... 이고, 그 중 가장 작은 공통 배수는 36입니다.
TIP
LCM은 “배수”이기 때문에 값이 빠르게 커집니다.
자바 구현에서는 int 범위를 넘을 가능성이 높아, 기본적으로 long으로 계산하는 습관이 안전합니다.
수학 개념
LCM을 지지하는 수학: 약수, 배수, 소인수분해, GCD
(1) 배수의 판정
어떤 수 n이 a의 배수라는 말은 n % a = 0 (a로 나누어떨어짐)을 뜻합니다. LCM은 “a로도, b로도 나누어떨어지는 수” 중 가장 작은 값을 찾는 개념입니다.
(2) 소인수분해 관점
a와 b를 소인수분해했을 때, LCM은 각 소수의 지수(횟수)를 큰 쪽으로 맞춰 곱한 값입니다.
예) 12 = 2²×3, 18 = 2×3² → LCM = 2²×3² = 36
(3) GCD와의 관계식
소인수분해 관점에서, 공통으로 포함되는 소수(겹치는 부분)는 GCD가 가져가고, 전체를 포괄하는 조합은 LCM이 가져갑니다. 그 결과 다음 관계가 성립합니다.
LCM(a, b) × GCD(a, b) = |a × b|
따라서 LCM(a, b) = |a × b| / GCD(a, b) 로 빠르게 계산할 수 있습니다.
알고리즘 개념
유클리드 호제법: GCD를 O(log n)에 구하는 표준
핵심 점화식
gcd(a, b) = gcd(b, a % b) 를 b가 0이 될 때까지 반복합니다.
일반적으로 시간복잡도는 O(log(min(a,b)))로 매우 빠릅니다.
1
GCD 계산
(a, b) → (b, a%b)로 갱신하며 b=0이 되면 그때의 a가 GCD
2
LCM 확장
LCM(a,b)=|a×b|/GCD(a,b) (단, 오버플로우 계산 순서가 중요)
3
여러 수로 일반화
LCM(a,b,c)=LCM(LCM(a,b),c) 처럼 앞에서부터 누적
구현
Java로 LCM 구현하기: 안전한 계산 순서가 핵심
TIP
(a * b) / gcd 는 곱셈이 먼저 overflow 날 수 있습니다. 자바에서는 보통 (a / gcd) * b 순서로 계산해 중간값 폭증을 줄입니다.
포인트 오버플로우 방지를 위해 (a / gcd) * b 순서로 계산합니다.
public class LcmGuide {
// 유클리드 호제법 (반복문): O(log(min(a,b)))
static long gcd(long a, long b) {
a = Math.abs(a);
b = Math.abs(b);
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return a;
}
// LCM: lcm(a, b) = |a / gcd(a,b) * b|
static long lcm(long a, long b) {
// 코테/실무에서 흔히: LCM(0, x) = 0 (문제 정의 우선)
if (a == 0 || b == 0) return 0;
long g = gcd(a, b);
return Math.abs((a / g) * b); // 나눗셈 먼저 -> 중간값 폭증/overflow 위험 감소
}
// 여러 수의 LCM (누적): LCM(a,b,c)=LCM(LCM(a,b),c)
static long lcmAll(long[] nums) {
long ans = 1;
for (long x : nums) {
ans = lcm(ans, x);
if (ans == 0) return 0;
}
return ans;
}
public static void main(String[] args) {
System.out.println(lcm(12, 18)); // 36
System.out.println(lcmAll(new long[]{2, 6, 8})); // 24
System.out.println(lcm(0, 10)); // 0
}
}GOOD
(a / gcd) * b 형태로 계산
곱셈 전에 나눗셈을 해서 중간값이 과도하게 커지는 걸 줄입니다.
곱셈 전에 나눗셈을 해서 중간값이 과도하게 커지는 걸 줄입니다.
BAD
(a * b) / gcd 형태로 계산
a*b가 먼저 overflow면 결과가 즉시 깨집니다.
a*b가 먼저 overflow면 결과가 즉시 깨집니다.
예시
LCM(12, 18)을 수학 → 알고리즘으로 검증하기
수학 12=2²×3, 18=2×3² → LCM=2²×3²=36
알고리즘
GCD(12,18): (18,12) → (12,6) → (6,0) 이므로 GCD=6
LCM(12,18)=|12×18|/6=36
LCM(12,18)=|12×18|/6=36
코테 포인트
자주 틀리는 지점 (실수 방지 체크)
1
오버플로우 계산 순서
곱셈을 먼저 하면 쉽게 터집니다. (a / gcd) * b로 계산하세요.
2
음수 입력
LCM은 보통 양수로 정의합니다. 입력이 음수일 수 있으면 abs 처리로 결과를 양수로 맞추세요.
3
0 포함 케이스
대부분의 문제는 LCM(0, x)=0로 처리합니다. 단, 문제의 정의를 최우선으로 확인하세요.
요약
체크리스트로 마무리
CHECK
✅ LCM은 공통 배수의 최소값 (가장 작은 양의 정수)
✅ 수학 관계: LCM(a,b)×GCD(a,b)=|a×b|
✅ 알고리즘: GCD는 유클리드 호제법으로 O(log(min))
✅ 구현 안정성: (a / gcd) * b 순서로 overflow 위험 낮추기
✅ 여러 수: LCM(LCM(a,b),c) 방식으로 누적 계산
728x90