[정글 베이직 10] — 정수론- GCD & LCM

크래프톤 정글 › 베이직 10

[정글 베이직 10]
정수론 — GCD & LCM

유클리드 호제법으로 최대공약수를, GCD로 최소공배수를 O(log n)에 구하기

▶ INPUT

a = 48
b = 18

두 양의 정수

✓ OUTPUT

GCD = 6
LCM = 144

최대공약수 · 최소공배수

01 문제 설명

두 양의 정수 a, b가 주어졌을 때, 최대공약수(GCD, Greatest Common Divisor)와 최소공배수(LCM, Least Common Multiple)를 구합니다. 단순 반복으로 구하면 O(min(a, b))이지만, 유클리드 호제법을 사용하면 O(log n)으로 줄어듭니다.

📌 핵심 입출력
입력: 두 양의 정수 a, b
출력: GCD (최대공약수), LCM (최소공배수)

예제 1 : a=48, b=18 → GCD=6, LCM=144
예제 2 : a=100, b=75 → GCD=25, LCM=300
예제 3 : a=17, b=19 → GCD=1, LCM=323 (서로소)

02 핵심 공식

gcd(a, b) = gcd(b, a % b) 유클리드 호제법 — b가 0이 될 때까지 재귀적으로 나머지를 구함

lcm(a, b) = (a × b) // gcd(a, b) LCM 공식 — GCD를 구한 뒤 한 번의 나눗셈으로 계산

왜 a * b // gcd(a, b)로 LCM을 구할 수 있을까요? 두 수의 곱 a × b는 항상 gcd × lcm과 같기 때문입니다. 즉, a × b = gcd(a, b) × lcm(a, b) 가 항상 성립합니다.

⚠️ 오버플로우 주의!
a * b를 먼저 계산하면 두 수가 클 때 오버플로우가 발생할 수 있습니다. Python은 임의 정밀도 정수를 지원해 괜찮지만, C/Java에서는 a // gcd(a, b) * b 순서로 계산해야 안전합니다.

03 유클리드 호제법 시각화 — gcd(48, 18)

🔍 단계별 나머지 계산

step 0 gcd(48, 18) → 48 % 18 = 12 b≠0, 계속

step 1 gcd(18, 12) → 18 % 12 = 6 b≠0, 계속

step 2 gcd(12, 6) → 12 % 6 = 0 b≠0, 계속

step 3 gcd(6, 0) → b == 0 → return 6 ✅ 종료

같은 과정을 재귀 호출 트리로 표현하면:

gcd(48, 18) └─→ gcd(18, 12) └─→ gcd(12, 6) └─→ gcd(6, 0) └─→ b == 0 ∴ return 6 ← 6 ← 6 ← 6 ← 6 (최종 GCD)

💡 핵심: 매 호출마다 나머지(a % b)가 반드시 감소하므로 유한 번 만에 b=0이 됩니다. 이때 a가 바로 GCD입니다.

04 gcd — 재귀 구현 O(log n)

 

 

 

Python 3

def gcd(a, b): """유클리드 호제법 — 재귀 구현""" # base case: b가 0이면 a가 GCD if b == 0: return a # recursive: gcd(b, a % b)로 문제 축소 return gcd(b, a % b) # 테스트 print(gcd(48, 18)) # 6 print(gcd(100, 75)) # 25 print(gcd(17, 19)) # 1 (서로소)

💡 base case가 b == 0인 이유
gcd(a, 0)은 "a와 0의 최대공약수"입니다. 어떤 수든 0과의 공약수는 자기 자신이므로 return a가 맞습니다.
반대로 gcd(0, b)를 호출하면 다음 단계에서 gcd(b, 0)이 되어 b를 반환합니다.

05 재귀 vs 반복 구현 비교

🔁 재귀 (Recursive)

def gcd(a, b): if b == 0: return a return gcd(b, a % b) # 코드 간결, 수식과 1:1 대응 # 깊은 재귀 시 스택 오버플로우 가능

🔄 반복 (Iterative)

def gcd_iterative(a, b): while b != 0: a, b = b, a % b return a # 스택 오버플로우 없음 # 실무에서 더 안전한 선택

항목	재귀	반복
가독성	수식과 1:1 대응, 직관적	코드량 약간 증가
안전성	깊은 재귀 시 스택 오버플로우 위험	스택 위험 없음
성능	함수 호출 오버헤드 있음	약간 더 빠름
시간 복잡도	O(log min(a,b))	O(log min(a,b))
Python 실무	깔끔한 코드 선호 시	대용량 입력 시 권장

🐍 Python 내장 gcd 활용: Python 3.5+ 부터는 math.gcd(a, b)로 바로 사용 가능합니다. Python 3.9+ 는 math.lcm(a, b)도 지원합니다. 알고리즘 학습 목적 외에는 내장 함수를 사용하세요.

06 lcm — 최소공배수 구현

 

 

 

Python 3

def lcm(a, b): """LCM = (a × b) ÷ GCD""" return (a * b) // gcd(a, b) # 테스트 print(lcm(48, 18)) # 144 → 48×18=864, 864//6=144 print(lcm(100, 75)) # 300 → 100×75=7500, 7500//25=300 print(lcm(17, 19)) # 323 → 17×19=323, 323//1=323

📐 lcm(48, 18) 계산 과정

① GCD gcd(48, 18) = 6

② 곱 48 × 18 = 864

③ LCM 864 ÷ 6 = 144 ✅

07 확장 유클리드 호제법 심화

기본 GCD를 넘어, ax + by = gcd(a, b)를 만족하는 정수 x, y까지 함께 구하는 알고리즘입니다. 암호학(RSA), 모듈러 역원 계산 등에 활용됩니다.

 

 

 

Python 3

def extended_gcd(a, b): """ 확장 유클리드 호제법 ax + by = gcd(a, b) 를 만족하는 (gcd, x, y) 반환 """ # base case: b == 0이면 a·1 + 0·0 = a if b == 0: return (a, 1, 0) # recursive: 한 단계 축소 g, x1, y1 = extended_gcd(b, a % b) # 역추적: 현재 단계의 x, y 계산 x = y1 y = x1 - (a // b) * y1 return (g, x, y) # 테스트 — 35x + 15y = gcd(35, 15) a, b = 35, 15 g, x, y = extended_gcd(a, b) print(f"GCD = {g}") # GCD = 5 print(f"{a}×{x} + {b}×{y} = {g}") # 35×1 + 15×-2 = 5 print(f"검증: {a*x + b*y}") # 5 ✓

🔐 활용: 모듈러 역원 (RSA 암호화)
ax ≡ 1 (mod m) 을 만족하는 x를 구할 때, gcd(a, m) == 1 이면 확장 유클리드로 x를 바로 구할 수 있습니다. 이 x를 a의 모듈러 역원이라고 합니다.

08 소수 판별 (is_prime) O(√n)

n이 소수인지 판별하는 가장 기본적인 방법은 2부터 √n까지 나누어 보는 것입니다. 짝수를 먼저 처리하고 홀수만 확인하면 연산 수를 절반으로 줄일 수 있습니다.

 

 

 

Python 3

def is_prime(n): """소수 판별 — O(√n)""" if n < 2: return False # 0, 1은 소수 아님 if n == 2: return True # 2는 유일한 짝수 소수 if n % 2 == 0: return False # 그 외 짝수는 소수 아님 # 3부터 √n까지 홀수만 검사 i = 3 while i * i <= n: if n % i == 0: return False i += 2 # 홀수만 (+2) return True # 테스트 결과 test_numbers = [2, 3, 4, 17, 20, 29, 100] for num in test_numbers: result = "소수" if is_prime(num) else "합성수" print(f"{num}: {result}") # 2: 소수 / 3: 소수 / 4: 합성수 / 17: 소수 / 20: 합성수 / 29: 소수 / 100: 합성수

🔍 왜 √n까지만 검사하면 될까?
n = a × b 라면 a와 b 중 하나는 반드시 √n 이하입니다. 따라서 √n까지 나누어 떨어지는 수가 없으면 n은 소수입니다.
i * i <= n으로 쓰면 import math 없이도 동일하게 동작합니다.

09 전체 테스트 결과

 

 

 

실행 결과

=== 테스트 케이스 1: GCD와 LCM === a = 48, b = 18 GCD (재귀): 6 GCD (반복): 6 LCM: 144 === 테스트 케이스 2 === a = 100, b = 75 GCD: 25 LCM: 300 === 테스트 케이스 3: 서로소 === a = 17, b = 19 GCD: 1 LCM: 323 서로소(coprime): GCD가 1 === 테스트 케이스 4: 확장 유클리드 === a = 35, b = 15 GCD = 5 35 × 1 + 15 × -2 = 5 검증: 5 = 5 ✓ === 테스트 케이스 5: 소수 판별 === 2: 소수 3: 소수 4: 합성수 17: 소수 20: 합성수 29: 소수 100: 합성수

10 복잡도 정리

함수	시간 복잡도	공간 복잡도	핵심 원리
gcd (재귀)	O(log n)	O(log n) 스택	나머지가 절반 이하로 감소
gcd_iterative	O(log n)	O(1)	재귀 없이 while 루프
lcm	O(log n)	O(1)	gcd 결과 활용, 나눗셈 1회
extended_gcd	O(log n)	O(log n) 스택	역추적으로 베주 계수 계산
is_prime	O(√n)	O(1)	√n까지만 홀수 검사

11 파이썬 문법 정리

a % b

나머지 — 유클리드 핵심 연산

a // b

정수 나눗셈 (몫만, 소수점 버림)

a, b = b, a % b

다중 할당 — 반복 gcd 한 줄 처리

i * i <= n

sqrt 없이 √n 조건 표현 (권장)

if b == 0: return a

재귀 base case — 종료 조건

math.gcd(a, b)

Python 내장 GCD (3.5+)

math.lcm(a, b)

Python 내장 LCM (3.9+)

g, x, y = extended_gcd(a, b)

튜플 언패킹 — 다중 반환값 처리

🚨 흔한 실수!
• a % 0 → ZeroDivisionError! base case로 b==0을 먼저 처리해야 합니다.
• is_prime에서 i * i < n (등호 누락) → n이 완전제곱수일 때 잘못된 결과 (예: is_prime(9) → True).
• lcm에서 a * b // gcd(a, b)가 아닌 (a * b) // gcd(a, b)로 괄호를 명시해야 합니다.

---

#크래프톤정글 #베이직10 #정수론 #GCD #LCM #유클리드호제법 #소수판별 #확장유클리드 #Python #OnCampus