안녕하세요! 이번 포스트에서는 알고리즘 문제 풀이를 통해 ‘최소 공배수(Least Common Multiple, LCM)’를 구하는 방법을 자세히 알아보겠습니다. 최소 공배수는 두 개 이상의 정수의 공통 배수 중에서 가장 작은 수를 의미합니다. 프로그래밍 면접이나 코딩 테스트에서 자주 출제되므로 이 문제를 확실히 이해하고 연습하는 것이 중요합니다.
문제 정의
주어진 두 개의 정수 A와 B에 대해, 두 숫자의 최소 공배수를 구하는 함수를 작성하세요.
입력
- 두 개의 정수 A, B (1 ≤ A, B ≤ 100,000)
출력
- A와 B의 최소 공배수 (LCM)
예제
입력: 4 5 출력: 20
문제 접근
최소 공배수를 계산하기 위해서는 최대 공약수(Greatest Common Divisor, GCD)를 활용하는 것이 효율적입니다. 최소 공배수는 다음과 같은 공식으로 구할 수 있습니다:
LCM(A, B) = (A × B) / GCD(A, B)
이 공식의 유래는 두 수의 공배수에 대한 정의와 최대 공약수의 성질에서 오기 때문입니다. 두 수의 곱을 최대 공약수로 나누면, 해당 숫자들이 공유하는 배수를 제외한 나머지 배수만 포함하게 됩니다.
파이썬에서 GCD 계산하기
파이썬에서는 기본적으로 제공되는 math 모듈을 사용할 수 있어, 최대 공약수를 쉽게 구할 수 있습니다.
문제 해결을 위한 코드 작성
이제 최소 공배수를 구하는 함수를 한 단계씩 구현해 보겠습니다.
import math
def lcm(a: int, b: int) -> int:
return (a * b) // math.gcd(a, b)
# 함수 테스트
a, b = map(int, input("두 개의 정수를 입력하세요: ").split())
print(f"{a}와 {b}의 최소 공배수는 {lcm(a, b)}입니다.")
코드 설명
- 우선
math모듈을 임포트하여gcd함수를 사용할 수 있도록 합니다. lcm함수를 정의합니다. 이 함수는 두 개의 정수를 매개변수로 받아서 최소 공배수를 계산하여 반환합니다.- 마지막으로 사용자 입력을 받아 함수를 테스트합니다.
테스트 케이스
이제 다양한 입력 값을 통해 함수가 제대로 작동하는지 확인해 보겠습니다.
# 테스트 케이스 print(lcm(4, 5)) # 출력: 20 print(lcm(12, 15)) # 출력: 60 print(lcm(7, 3)) # 출력: 21 print(lcm(100, 10)) # 출력: 100 print(lcm(27, 36)) # 출력: 108
복잡도 분석
이제 코드의 시간 복잡도와 공간 복잡도를 분석해 봅시다.
- 시간 복잡도: GCD를 계산하는 데에 유클리드 알고리즘을 사용하면 O(log(min(A, B)))의 시간 복잡도를 가집니다. 따라서 LCM을 구하는 전체 복잡도는 O(log(min(A, B)))입니다.
- 공간 복잡도: 상수 공간 O(1)입니다. 별도의 추가 메모리를 사용하지 않기 때문입니다.
마무리
이번 포스트에서는 두 개의 수를 이용해 최소 공배수를 구하는 알고리즘을 파이썬을 통해 구현해 보았습니다. 이번 문제는 공약수와 배수의 개념을 복습할 수 있는 좋은 기회가 되었을 것입니다. 코딩 테스트에서 자주 나타나는 유형이므로 충분히 연습하시기를 권장합니다.
다음 포스트에서는 더 다양한 문제를 가지고 찾아오겠습니다. 많은 관심 부탁드립니다!