제로베이스 데이터사이언스 스쿨 - Part 03. 기초 수학-04

 Chapter 01. 기초 수학

 

최소공배수 (Least Common Multiple, LCM)

1. 공배수란?

• 정의:
  두 개 이상의 수에서 공통으로 나오는 배수를 말한다.
• 예시:

수	배수	공배수
3	3, 6, 9, 12, 15, 18, …
5	5, 10, 15, 20, 25, 30, …	15, 30, 45, …

💡 “공배수”는 서로 다른 수들이 일정한 주기로 만나는 공통 배수 패턴이다.

---

2. 최소공배수란?

• 정의:
  공배수 중에서 가장 작은 수를 최소공배수(LCM) 라고 한다.
• 예시:
  

  수	최소공배수
  3, 5	15
  4, 6	1

💡 두 수가 같은 주기로 만나는 첫 번째 지점을 찾는 개념.

---

3. 소인수분해로 구하기

소인수분해를 이용하면 최소공배수를 빠르게 구할 수 있다.

 

규칙:
공통된 소인수는 큰 지수로, 공통되지 않은 소인수는 모두 곱한다.

수	소인수분해	최소공배수
6	2 × 3
12	2² × 3	12 (2² × 3)
15	3 × 5	60 (2² × 3 × 5)

💡 최대공약수(GCD)는 공통 소인수의 작은 지수,
최소공배수(LCM)는 공통 소인수의 큰 지수를 사용한다.

---

4. 소수 나눗셈으로 구하기

공통된 소수로 나누며, 나눌 수 없는 수는 그대로 내려 적는 방식.

예시: 6, 12, 15의 LCM 구하기

소수	나눈 결과	누적 곱
2	3, 6, 15	2
2	3, 3, 15	2²
3	1, 1, 5	2²×3
5	1, 1, 1	2²×3×5 = 60

💡 이 방식은 ‘소인수분해를 표 형태로 표현한 계산법’이다.

---

5. 실습 예시

수	최소공배수	공배수
12, 21, 33	924	924, 1848, 2772, …
12, 36, 48	144	144, 288, 432, …

추가 문제

2, 5, 8 중 하나만 5를 곱했을 때 LCM이 변하는 수는?

• 2, 5, 8 → LCM = 40
• 2, 25, 8 → LCM = 200
  ➜ 25를 곱했을 때만 최소공배수가 변함

---

6. 파이썬으로 LCM 구하기

(1) 두 수의 최소공배수 구하기

x = int(input("첫 번째 수: "))
y = int(input("두 번째 수: "))

for i in range(max(x, y), (x * y) + 1):
    if i % x == 0 and i % y == 0:
        print("최소공배수:", i)
        break

(2) 세 수의 최소공배수 구하기

def lcm(x, y):
    for i in range(max(x, y), (x * y) + 1):
        if i % x == 0 and i % y == 0:
            return i

a = int(input())
b = int(input())
c = int(input())

print(lcm(lcm(a, b), c))

💡 두 수의 LCM을 구한 뒤, 그 결과를 세 번째 수와 다시 계산하면 된다.

---

7. 응용 문제 — 입항 주기 계산

과일선: 3일 / 생선선: 4일 / 야채선: 5일 주기로 입항한다면
모든 배가 함께 입항하는 날은?

→ LCM(3, 4, 5) = 60일마다

💡 실생활에서도 주기 계산 문제는 LCM 개념으로 해결 가능하다.

 

* 이 글은 제로베이스 데이터사이언스 파트타임 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.

---

 

💡 생각 정리

이번 강의에서는 단순 계산을 넘어 ‘주기와 패턴을 찾는 사고’ 를 배웠다.
최소공배수는 반복되는 이벤트의 최소 주기를 구하는 원리이기 때문에 실제 생활이나 프로그래밍에서 매우 자주 등장한다.

특히 파이썬으로 구현하면서,

• 반복문(for)과 조건문(if)의 흐름
• 함수를 통한 구조적 사고
• GCD-기반 LCM 계산의 효율성
  을 자연스럽게 익힐 수 있었다.

---

🚀 적용점

• 실무 응용:
  • 생산라인, 이벤트 주기, 신호 동기화 등 ‘주기 일치 문제’에 활용
  • 예: A 공정 3일, B 공정 4일, C 공정 5일 → 공정 전체 동기 주기 = 60일
• 코딩 테스트 연습:
  • LCM은 GCD와 세트로 자주 출제되며,
    수학적 규칙을 코드로 구현하는 좋은 알고리즘 훈련 주제다.
  • 공식: LCM(a, b) = (a * b) // GCD(a, b)
• 심화 학습 아이디어:
  • 여러 수(리스트 형태)의 LCM을 구하는 함수 작성
  • math.gcd() 내장 함수를 활용해 효율적으로 LCM 구현
  • 주기, 회전, 반복 문제를 시뮬레이션 형태로 확장

👉 최소공배수는 ‘시간적 규칙성’을 다루는 알고리즘의 핵심 개념으로, 이번 실습을 통해 수학적 사고와 프로그래밍 사고가 유기적으로 연결되었다.