07. 일곱 번째 수업: 유클리드 호제법 (Euclidean Algorithm)

두 개의 거대한 숫자, 예를 들어 $10,710$과 $3,696$이 주어졌을 때 이 두 숫자를 모두 깔끔하게 나누어떨어지게 하는 ‘가장 큰 공통된 약수(최대공약수, GCD)’를 사람의 머리로 어떻게 찾을 수 있을까요? 소수들을 하나씩 끼워 맞춰보는 것은 너무나도 고통스러운 일입니다. 기원전 300년경, 이집트 알렉산드리아의 천재 수학자 유클리드(Euclid)는 인류 역사상 가장 위대하고 완벽한 알고리즘을 발명해 냈습니다.

학습 목표

  • 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 가장 빠른 전략인 ‘유클리드 호제법’을 이해합니다.
  • 뺄셈과 나눗셈의 반복(나머지 교차)을 통해 거대한 숫자를 기하급수적으로 축소시키는 원리를 배웁니다.
  • 파이썬의 math.gcd 라이브러리와 직접 구현하는 재귀 함수(Recursive Function) 코드를 통해 수만 자리의 최대공약수를 $0.001초$ 만에 찾아냅니다.

1. 꼬리 물기 나눗셈: 유클리드의 마법

유클리드는 거대한 숫자를 직접 소인수분해하는 바보 같은 짓을 하지 않았습니다. 그는 두 수의 차이나 나머지 속에 반드시 ‘최대공약수’의 영혼이 그대로 남아있다는 규칙을 깨달았습니다.

$A$를 $B$로 나누었을 때 나머지가 $R$이라고 합시다.

“원래의 두 수 $A$와 $B$의 최대공약수는, 찌꺼기로 남은 $B$와 $R$의 최대공약수와 완벽히 똑같다!”

이 무서운 진리를 깨달으면 우리는 다음과 같은 연쇄 나눗셈(호제법)을 할 수 있습니다. 대상은 $10,710$과 $3,696$ 입니다.

  1. $10,710 \div 3,696 = 2$ … 나머지 $\mathbf{3,318}$ (이제 큰 수는 버리고 $3,696$과 $3,318$로 타겟이 확 줄어듭니다!)
  2. $3,696 \div 3,318 = 1$ … 나머지 $\mathbf{378}$ (타겟이 $3,318$과 $378$로 더 줄어듭니다!)
  3. $3,318 \div 378 = 8$ … 나머지 $\mathbf{294}$
  4. $378 \div 294 = 1$ … 나머지 $\mathbf{84}$
  5. $294 \div 84 = 3$ … 나머지 $\mathbf{42}$
  6. $84 \div 42 = 2$ … 나머지 $\mathbf{0}$ (우와! 딱 떨어졌다!)

찌꺼기(나머지)가 정확히 $0$이 되는 순간, 마지막으로 사용되었던 나누는 수 $42$가 바로 두 거대 숫자의 최대공약수(GCD)입니다! 아무리 큰 숫자라도 이 꼬리 물기를 몇 번만 반복하면 순식간에 두 자리 숫자로 박살이 납니다.

2. Python 코드로 구현하는 ‘분신술 (Recursion)’

이 꼬리 물기 찌꺼기 연산을 컴퓨터 프로그램으로 짤 때는, 완전히 똑같은 행동(나누고 찌꺼기 넘기기)을 반복하므로 재귀 함수(자신이 자신을 다시 호출하는 함수)라는 고급 기술을 사용합니다.

import math

# 파이썬으로 환생한 2300년 전의 알고리즘 (유클리드 호제법)

def euclid_gcd(A, B):
    """나머지가 0이 될 때까지 스스로를 계속 소환하는 재귀 함수(Recursion)"""
    
    # 찌꺼기가 하나도 남지 않고 딱 떨어졌다면(0이 되었다면) 
    # 바로 직전에 나눴던 숫자(B)가 최후의 심판관(GCD)입니다!
    if A % B == 0:
        return B
    else:
        # 나머지가 남았다면?
        remainder = A % B
        print(f"-> 찌꺼기 {remainder} 발생! 다시 좁혀서 들어갑니다: gcd({B}, {remainder})")
        
        # B와 나머지(remainder)를 가지고 자기 자신 함수를 또다시 호출합니다! (분신술)
        return euclid_gcd(B, remainder)


num1 = 10710
num2 = 3696

print(f"탐색 시작: {num1} 과 {num2} 의 최대공약수 찾기")
final_gcd = euclid_gcd(num1, num2)

print("="*40)
print(f"👑 유클리드 알고리즘이 찾아낸 최종 보스(최대공약수): {final_gcd}")

# 파이썬 내장 라이브러리로 0.0001초 만에 확인하기
print(f"✅ 파이썬 기본 탑재 모듈 math.gcd 검증: {math.gcd(num1, num2)}")

$A$와 $B$라는 두 매개변수 방을 계속해서 $B$와 $Remainder$(찌꺼기)로 교체해가면서 빙글빙글 도는 이 재귀(Recursion) 알고리즘은 현대 컴퓨터 과학(CS) 트리 탐색과 암호학 계산에서 뼈대가 되는 가장 우아한 로직입니다.

기원전 수학자의 머릿속 아이디어가, $21$세기 컴퓨터의 메모리 안에서 가장 파괴적인 효율을 내는 인공지능 해킹 툴로 동작하고 있는 것입니다.

학습 정리

  1. 유클리드 호제법: 두 큰 수의 나눗셈 찌꺼기(나머지)를 연속적으로 넘겨받아가며 최대공약수를 기하급수적으로 축소하여 찾아내는 인류 최고의 산술 알고리즘.
  2. 최대공약수 (GCD): 아무리 큰 집합(숫자)이라도 서로를 공통으로 엮을 수 있는 가장 거대한 블록 크기. 암호학의 열쇠 생성을 나눌 때 핵심이 된다.
  3. 똑같은 로직 안에 인자(Parameter)의 스케일만 축소하여 스스로를 끝없이 부르는 파이썬의 재귀 함수(Recursion)는 복잡한 while 문을 단 3줄의 우아한 수학 공식으로 압축해 버린다.
서브목차