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

 Chapter 01. 기초 수학

 

최대공약수 (Greatest Common Divisor, GCD)

 

1. 공약수란?

• 공약수(Common Divisor)
  → 두 개 이상의 수에서 공통으로 나누어떨어지는 약수

예시	약수	공약수
12	1, 2, 3, 4, 6, 12
20	1, 2, 4, 5, 10, 20	1, 2, 4

💡 공약수는 여러 수를 동시에 나눌 수 있는 공통된 인수들의 집합이다.

---

2. 최대공약수란?

• 최대공약수(Greatest Common Divisor, GCD)
  → 공약수 중 가장 큰 수

예시

12와 20의 공약수: 1, 2, 4
👉 최대공약수(GCD)는 4

---

3. 소인수분해로 구하기

공통인 소인수의 지수가 작은 것을 모두 곱한다.

수	소인수분해	최대공약수
12	2² × 3
20	2² × 5	4 (2²)

💡 공통된 소인수의 최소 거듭제곱만 곱하면 된다.

---

4. 소수 나눗셈 방법 (빠른 계산법)

소수를 이용해 두 수를 나누며 나머지가 0이 되는 경우만 추출하는 방식

예시	계산 과정	GCD
12, 20	2 → 2 → (남은 수: 3, 5)	2×2 = 4
36, 60	2 → 2 → 3 → (남은 수: 9, 15)	2×2×3 = 12

---

5. 실생활 응용 예시

문제:
빵 112개와 우유 80개를 학생들에게 남김없이 똑같이 나눠주려면
최대 몇 명이 나눠 가질 수 있을까?

• 112와 80의 최대공약수 = 16
• 학생 1명이 받는 양:
  • 빵: 112 ÷ 16 = 7개
  • 우유: 80 ÷ 16 = 5개

👉 공평 분배 문제는 실제 생활 속 GCD의 대표 응용 사례이다.

---

6. 파이썬으로 GCD 구하기

(1) 기본 버전 — for문을 이용한 최대공약수

 

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

for i in range(min(x, y), 0, -1):
    if x % i == 0 and y % i == 0:
        print("최대공약수:", i)
        break

➜ 1부터 공통으로 나누어지는 수 중 가장 큰 수를 찾는다.

---

(2) 유클리드 호제법 (Euclidean Algorithm)

두 수의 최대공약수는, 큰 수를 작은 수로 나눈 나머지와 작은 수의 GCD와 같다.

 

def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

print(gcd(36, 12))  # 출력: 12

단계	계산	결과
36 % 12	나머지 0	→ GCD = 12
60 % 36	나머지 24	→ 다음 단계 (36, 24)

💡 나머지가 0이 될 때의 나누는 수가 바로 최대공약수(GCD)

 

 

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

---

 

💡 생각 정리

이번 강의는 단순한 약수 계산이 아니라, 수의 구조적 관계를 이해하는 사고력 훈련이었다.
특히 유클리드 호제법은 반복적인 나눗셈을 통해 문제를 단순화시키는 알고리즘으로, “문제를 작게 나눠 푼다”는 프로그래밍적 사고를 잘 보여준다.

 

또한 파이썬으로 구현하면서,

• 반복문(for, while)의 흐름
• 조건문(if)의 논리 구조
• 두 수를 교환하며 나머지를 활용하는 재귀적 사고를 명확하게 익힐 수 있었다.

---

🚀 적용점

• 실무 응용:
  • 공평 분배, 배치, 주기 계산, 데이터 샘플링 등에서 활용
  • 예: 생산라인 주기 계산, 음원 샘플 구간의 동기화 등
• 알고리즘 학습:
  • GCD는 최소공배수(LCM) 계산의 기반이 된다 (LCM = (a*b)/GCD)
  • 효율적 반복 구조와 조건문 최적화 훈련에 적합
• 심화 실습 아이디어:
  • 세 개 이상의 수의 GCD 구하기
  • 리스트로 입력받아 functools.reduce()로 GCD 자동 계산
  • GCD와 LCM을 동시에 출력하는 함수 작성

👉 이번 주제는 단순한 수학이 아니라, 프로그래밍 사고력과 알고리즘 이해의 출발점이었다.