Least Common Multiple
두 양의 정수 a와 b가 주어집니다. 두 정수 a와 b가 모두 나누어떨어지는 가장 작은 양의 정수인 최소공배수를 반환하세요.
함수
- ainteger
- 첫 번째 양의 정수
- binteger
- 두 번째 양의 정수
- 반환값integer
- a와 b 모두의 배수인 가장 작은 양의 정수
제약 조건
1 ≤ a ≤ 1061 ≤ b ≤ 106- 답은 부호 있는 32비트 정수에 들어갑니다:
lcm(a, b) ≤ 231-1. 곱a × b는 들어가지 않을 수도 있습니다.
예제
- 입력
- a = 4b = 6
- 출력
- 12
- 설명
6의 배수는 6, 12, 18부터 시작하고,4의 배수는 4, 8, 12부터 시작합니다. 두 목록에서 처음으로 공통되는 수는12입니다.
- 입력
- a = 7b = 3
- 출력
- 21
- 설명
7과3은1외에 공통 인수가 없으므로 최소공배수는 두 수의 곱인21입니다.
- 입력
- a = 15b = 45
- 출력
- 45
- 설명
15은45를 나누어떨어지게 하므로,45는 이미 두 수 모두의 배수이며45보다 작은 배수는 없습니다.
후속 질문
나눗셈이나 나머지 연산을 전혀 사용하지 않고, 뺄셈과 절반으로 나누기만 사용해 최대공약수를 구할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
정답은 더 큰 수의 배수입니다. 그 사이의 모든 수를 시도해야 할까요, 아니면 더 큰 수의 배수만 시도하면 될까요?
최대공약수와 최소공배수는 서로 연관되어 있습니다:
gcd(a, b) × lcm(a, b) = a × b. 유클리드 알고리즘은 수십 단계 만에 최대공약수를 구합니다.최대공약수를 계산한 다음
a / gcd × b를 반환하세요. 먼저 나누세요. 정답이 32비트 정수에 들어가더라도 곱a × b는 오버플로될 수 있습니다.
풀이
최소공배수와 최대공약수는 다음 한 가지 사실로 연결됩니다: gcd(a, b) × lcm(a, b) = a × b. 따라서 빠른 답은 a × b / gcd(a, b)입니다. 곱은 10^12까지 커질 수 있어 답은 범위에 들어가더라도 32비트 정수에서 오버플로가 발생할 수 있으므로, 곱하기 전에 최대공약수로 나누세요.
더 큰 수부터 세어 올라가세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
답은 더 큰 수 이상입니다. m을 max(a, b)에서 시작해 두 수 모두로 나누어떨어질 때까지 1씩 더합니다. 후보를 오름차순으로 시도하므로 처음 찾은 값이 최솟값입니다. 4와 6의 경우 6부터 11까지 시도한 다음 12에서 멈춥니다. a × b가 공배수이므로 반복문은 항상 끝납니다.
시도 횟수는 답의 크기 정도입니다. 소수 46337과 46327의 답은 2146654199로, 시도 횟수가 20억 회를 넘습니다.
알고리즘
a와b중 더 큰 값으로m을 설정합니다.m % a또는m % b가0이 아닐 동안m에 1을 더합니다.m을 반환합니다.
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return m더 큰 수의 배수로 진행하기
핵심 아이디어
정답은 더 큰 수인 big의 배수여야 하므로, big, 2 × big, 3 × big을 차례로 확인하고 더 작은 수로 나누어떨어지는 첫 번째 수에서 멈추세요. 4와 6의 경우 6을 확인한 다음 12를 확인합니다.
small × big은 항상 공배수이므로, 반복문은 최대 min(a, b)번 실행되며, 여기서는 최대 백만 번입니다. 이 제한에서는 충분히 빠르지만, 입력값이 커지면 실행 횟수도 늘어납니다. 숫자가 10^18까지라면 그렇지 않을 것입니다.
알고리즘
big을 더 큰 수로,small을 더 작은 수로 둡니다.m = big으로 설정합니다.m % small이0이 아닌 동안m에big을 더합니다.m을 반환합니다.
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return m최대공약수로 나눈 다음 곱하세요
핵심 아이디어
두 수를 모두 소인수분해합니다. 각 소수에 대해 gcd는 두 지수 중 작은 값을, lcm은 큰 값을 취하므로, 두 값을 함께 사용하면 a와 b의 모든 인수를 각각 정확히 한 번씩 사용합니다. 즉, gcd × lcm = a × b입니다. 4 = 2²와 6 = 2 × 3의 경우 gcd는 2이고 lcm은 2² × 3 = 12입니다.
유클리드 알고리즘은 O(log(min(a, b))) 단계 만에 gcd를 구합니다. 그런 다음 a / gcd × b 순서로 계산합니다. gcd는 a를 정확히 나누므로 값이 손실되지 않고, 어떤 단계의 값도 결과를 초과하지 않습니다. a × b / gcd는 a = b = 10^6일 때 32비트 정수의 범위를 넘습니다. 이 경우 곱은 10^12이고 결과는 10^6에 불과합니다.
알고리즘
a와b를x와y에 복사합니다.y가0이 아닐 동안(x, y)를(y, x % y)로 바꿉니다. 이제x가 최대공약수입니다.a를x로 나눕니다.- 그 결과에
b를 곱한 뒤 반환합니다.
def lcm(a, b):
x, y = a, b
while y != 0:
x, y = y, x % y
# x is gcd(a, b). Divide before multiplying.
return a // x * b
함정과 경계 사례
- 먼저
a × b를 계산하는 것. Java, C, C++, C# 및 Rust에서는10^6에 가까운 두 수의 곱이 32비트 정수의 범위를 넘어서 잘못된 값이나 음수가 됩니다(Rust 디버그 빌드에서는 패닉이 발생합니다). 하지만 lcm은 범위 안에 들어갑니다. - 부동 소수점으로 나누는 것. 결과가
2.146654199E9로 나오거나 마지막 자릿수를 잃을 수 있으므로, 모든 계산을 정수로 처리하세요. a와b자체에 유클리드 알고리즘의 반복문을 실행하는 것. 실행이 끝나면 두 변수에는 gcd와0이 들어 있으므로, 복사본을 사용하세요.- 답이
a × b라고 가정하는 것. 두 수가 공통 인수를 갖지 않을 때만 성립합니다.lcm(4, 6)은24가 아니라12입니다.
자주 묻는 질문3
두 수의 최소공배수(LCM)를 구하는 공식은 무엇인가요?
lcm(a, b) = a × b / gcd(a, b)이며, 중간 값이 답을 초과하지 않도록 a / gcd(a, b) × b로 계산합니다. 4와 6의 gcd는 2이고, 4 / 2 × 6 = 12입니다.
LCM을 계산하는 시간 복잡도는 얼마인가요?
gcd 공식은 Euclid 알고리즘의 비용과 같은 O(log(min(a, b))) 시간 복잡도와 O(1) 공간 복잡도를 가집니다. 더 큰 수의 배수를 차례로 확인하는 방법은 O(min(a, b))이고, 1씩 세는 방법은 O(lcm(a, b))입니다.
두 개보다 많은 수의 최소공배수는 어떻게 구하나요?
목록을 접습니다: lcm(a, b, c) = lcm(lcm(a, b), c). [4, 6, 10]의 경우 lcm(4, 6) = 12이고 lcm(12, 10) = 60입니다. 누적값은 빠르게 커지므로 목록이 길 때는 64비트 정수를 사용하세요.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def lcm(a, b):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
a = 4 b = 6
예상 출력
12