2300년 전 알고리즘이 지금도 쓰인다고? - 유클리드와 최대공약수의 비밀

2300년 전 알고리즘이 지금도 쓰인다고? - 유클리드와 최대공약수의 비밀

여러분, 최대공약수 구하는 방법 기억하시나요?

초등학교 때 배웠던 그 방법 말이에요. 두 수를 소인수분해해서 공통인 인수를 찾아 곱하는...

 

 

48 = 2 × 2 × 2 × 2 × 3
18 = 2 × 3 × 3
최대공약수 = 2 × 3 = 6

맞습니다. 이 방법도 정답이에요.

그런데 만약 두 수가 엄청 크다면 어떻게 될까요?

1,234,567,890과 9,876,543,210의 최대공약수를 구한다고 생각해보세요. 소인수분해... 가능은 하겠지만 머리가 아플 것 같죠?

오늘 소개할 유클리드 호제법은 2300년 전에 만들어진 알고리즘인데, 지금도 컴퓨터가 사용하는 가장 효율적인 방법입니다.

그리고 이 알고리즘을 만든 사람이 바로 **유클리드(Euclid, 기원전 4~3세기경 활동)**입니다.

기하학의 아버지, 유클리드

유클리드는 고대 그리스의 수학자입니다.

사실 유클리드에 대해 우리가 아는 건 많지 않아요. 정확한 생몰년도는 물론이고, 어디서 태어나고 어디서 죽었는지도 확실하지 않습니다. 기원전 4세기에서 3세기경 알렉산드리아에서 활동했을 것으로 추정될 뿐이죠. 심지어 실존 인물인지 아니면 여러 수학자들의 집단 필명인지도 논란이 있었을 정도예요.

하지만 확실한 건, 유클리드가 남긴 책 **『원론(Elements)』**이 인류 역사상 가장 많이 읽힌 수학책이라는 사실입니다.

성경 다음으로 많이 출판된 책이 바로 유클리드의 『원론』이라고 해요. 2000년 넘게 수학 교과서로 사용됐으니까요.

『원론』은 총 13권으로 이루어져 있는데, 기하학의 모든 것이 담겨 있습니다. 점, 선, 면의 정의부터 시작해서 삼각형, 원, 입체도형까지... 우리가 중고등학교에서 배우는 기하학의 대부분이 이 책에서 나왔어요.

그런데 『원론』 7권에 특별한 내용이 하나 나옵니다.

바로 **유클리드 호제법(Euclidean Algorithm)**입니다.

유클리드 호제법이란?

호제법(互除法)이라는 한자를 보면 '서로 나눈다'는 뜻입니다.

원리는 놀랍도록 간단해요.

두 수 a, b의 최대공약수는 b와 (a를 b로 나눈 나머지)의 최대공약수와 같다.

뭔 소리인지 모르겠죠? 예시로 보면 쉽습니다.

예제: 48과 18의 최대공약수 구하기

1단계: 48을 18로 나눈다

 

 

48 ÷ 18 = 2 ... 나머지 12

2단계: 이제 18과 12의 최대공약수를 구한다

 

 

18 ÷ 12 = 1 ... 나머지 6

3단계: 이제 12와 6의 최대공약수를 구한다

 

 

12 ÷ 6 = 2 ... 나머지 0

나머지가 0이 됐으므로, 답은 6입니다!

소인수분해 없이, 나눗셈만으로 최대공약수를 구했어요.

큰 수로 해볼까요?

1071과 462의 최대공약수는?

 

 

1071 ÷ 462 = 2 ... 나머지 147
462 ÷ 147 = 3 ... 나머지 21
147 ÷ 21 = 7 ... 나머지 0

답: 21

소인수분해로 풀려면 1071 = 3 × 3 × 7 × 17, 462 = 2 × 3 × 7 × 11... 이렇게 복잡하게 계산해야 하는데, 호제법은 훨씬 빠르죠?

왜 이게 작동하는 걸까?

수학은 '왜?'를 물어봐야 진짜 이해한 겁니다.

유클리드 호제법이 작동하는 이유를 간단히 설명해볼게요.

a = bq + r (a를 b로 나눈 몫이 q, 나머지가 r)이라고 하면,

a와 b의 공약수는 r의 약수이기도 합니다.

왜냐하면:

• a와 b가 d로 나누어떨어진다면
• a = bq + r에서 r = a - bq이므로
• r도 d로 나누어떨어진다

역으로, b와 r의 공약수도 a의 약수입니다.

따라서 **gcd(a, b) = gcd(b, r)**이 성립하는 거죠.

이 과정을 나머지가 0이 될 때까지 반복하면, 최대공약수를 찾을 수 있습니다.

2300년이 지나도 최고의 알고리즘

놀라운 건, 유클리드 호제법이 가장 오래된 알고리즘 가운데 하나라는 점입니다.

기원전 300년경에 만들어졌는데, 지금도 많은 프로그래밍 언어의 표준 라이브러리에서 사용되고 있어요.

Python으로 구현하면 이렇게 간단합니다:

 

 

python

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))  # 6
print(gcd(1071, 462))  # 21

단 4줄입니다!

컴퓨터 과학자들이 알고리즘의 효율성을 분석해봤는데, 유클리드 호제법은 **O(log n)**의 시간복잡도를 가진다고 해요. 즉, 숫자가 아무리 커져도 계산 횟수가 천천히만 증가한다는 뜻입니다.

실제로 대규모 인터넷 서비스의 암호화 시스템에서도 유클리드 호제법이 핵심적으로 활용되고 있습니다.

2300년 전 그리스 수학자가 만든 알고리즘이, 21세기 인터넷을 지키고 있는 겁니다.

고등학생 생활기록부 활동 아이디어

유클리드 호제법은 수학, 정보, 과학 등 여러 분야에서 탐구 활동으로 활용하기 정말 좋습니다.

📐 수학 계열 - 증명과 이론 탐구

활동 1: 유클리드 호제법의 수학적 증명

목표: 귀납법과 나눗셈 정리를 활용한 엄밀한 증명

탐구 내용:

1. 나눗셈 정리(Division Algorithm) 이해
2. 최대공약수의 성질 분석
3. gcd(a, b) = gcd(b, a mod b) 증명
4. 알고리즘이 반드시 종료됨을 증명

세특 기록 예시: "유클리드 호제법의 수학적 정당성을 엄밀하게 증명하는 프로젝트를 수행함. 나눗셈 정리를 기반으로 gcd(a,b) = gcd(b, a mod b)가 성립함을 증명하고, 나머지가 단조감소 수열을 이루므로 알고리즘이 유한 번의 단계 내에 종료됨을 수학적 귀납법으로 보임. 또한 최악의 경우 연속된 피보나치 수일 때임을 발견하고, 이때의 시간복잡도를 분석함. 고대 알고리즘의 현대적 효율성을 수학적으로 입증함."

활동 2: 확장 유클리드 호제법 연구

목표: 베주 항등식(Bézout's Identity) 이해

베주 항등식: ax + by = gcd(a, b)를 만족하는 정수 x, y가 존재한다

세특 기록 예시: "유클리드 호제법을 확장하여 ax + by = gcd(a,b)를 만족하는 정수 해 x, y를 구하는 알고리즘을 연구함. 호제법의 역과정을 추적하며 선형결합 계수를 역산하는 방법을 이해하고, 이것이 모듈로 연산에서의 역원을 구하는 데 활용됨을 발견함. RSA 암호화의 핵심 원리와 연결하여 고대 수학이 현대 정보보안에 어떻게 활용되는지 탐구함."

💻 정보/컴퓨터 계열 - 알고리즘 구현과 최적화

활동 3: 여러 언어로 구현 및 성능 비교

목표: 재귀/반복 방식 비교, 언어별 성능 분석

Python 재귀 버전:

 

 

python

def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

Python 반복 버전:

 

 

python

def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

C++ 버전 (성능 최적화):

 

 

cpp

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

세특 기록 예시: "유클리드 호제법을 Python, C++, JavaScript로 각각 구현하고 재귀와 반복 방식의 성능을 비교 분석함. 동일한 입력(최대 10^9)에 대해 실행 시간을 측정한 결과, C++이 가장 빠르고, Python에서는 재귀가 스택 오버플로우 위험이 있음을 발견함. 또한 내장 함수(Python의 math.gcd)와 직접 구현의 성능 차이를 분석하여 알고리즘 최적화의 중요성을 체감함."

활동 4: 시각화 프로그램 제작

목표: 알고리즘 실행 과정을 애니메이션으로 표현

세특 기록 예시: "유클리드 호제법의 실행 과정을 실시간으로 시각화하는 웹 애플리케이션을 개발함. JavaScript와 Canvas API를 활용하여 각 단계에서의 나눗셈과 나머지 계산을 막대 그래프로 표현하고, 사용자가 직접 숫자를 입력하면 알고리즘이 단계별로 진행되는 애니메이션을 제작함. 이를 통해 추상적인 알고리즘을 직관적으로 이해할 수 있는 교육 자료를 만들고, 학급 친구들에게 공유하여 알고리즘 교육에 기여함."

🔐 암호학과의 연결 - 융합 탐구

활동 5: RSA 암호화의 수학적 원리 탐구

목표: 유클리드 호제법이 어떻게 암호화에 사용되는가

핵심 개념:

1. 서로소(coprime) 판별: gcd(a, b) = 1
2. 모듈로 역원 계산: ax ≡ 1 (mod m)
3. RSA의 공개키/비밀키 생성

세특 기록 예시: "현대 인터넷 보안의 핵심인 RSA 암호화 알고리즘에서 유클리드 호제법이 어떻게 활용되는지 탐구함. 두 소수의 곱 n = pq에서 오일러 파이 함수 φ(n) = (p-1)(q-1)과 서로소인 공개 지수 e를 선택하고, 확장 유클리드 호제법으로 비밀 지수 d를 계산하는 과정을 Python으로 구현함. 실제 작은 소수로 암호화/복호화를 직접 수행하며, 2300년 전 알고리즘이 21세기 정보보안의 토대가 됨을 확인함."

활동 6: 간단한 암호화 프로그램 제작

세특 기록 예시: "유클리드 호제법을 활용한 간단한 메시지 암호화 프로그램을 제작함. 사용자가 입력한 평문을 ASCII 코드로 변환하고, RSA 원리를 단순화한 방식으로 암호화/복호화하는 Python 프로그램을 개발함. 키 생성 과정에서 확장 유클리드 호제법이 필수적임을 실습을 통해 이해하고, 작은 키 크기로 인한 보안 취약점도 체험함. 고대 수학 원리가 현대 기술과 결합하는 과정을 몸소 경험함."

🎯 경시대회/알고리즘 문제 해결

활동 7: 정보올림피아드 문제 풀이

대표적인 문제들:

• 백준 2609번: 최대공약수와 최소공배수
• 백준 1850번: 최대공약수 (큰 수)
• 백준 9613번: GCD 합

심화 문제:

• 백준 11689번: GCD(n, k) = 1 (오일러 파이 함수)
• 백준 2824번: 최대공약수 (자릿수 100개)

세특 기록 예시: "유클리드 호제법을 응용한 정보올림피아드 문제들을 해결하며 알고리즘적 사고력을 함양함. 단순히 최대공약수를 구하는 것을 넘어, 문자열로 주어진 큰 수의 GCD 계산, 여러 수들의 GCD 합 구하기 등 다양한 변형 문제를 해결함. 특히 오일러 파이 함수를 소인수분해와 유클리드 호제법으로 계산하는 문제에서 두 알고리즘의 연계를 깊이 이해함. 한국정보올림피아드 1차 대회 통과."

📊 수학사/과학사 탐구

활동 8: 고대 알고리즘의 현대적 의의

목표: 알고리즘의 역사적 발전 과정 연구

탐구 포인트:

• 왜 유클리드는 이 알고리즘을 만들었을까?
• 중세 아랍 수학자들은 어떻게 발전시켰나?
• 19세기 가브리엘 라메(Gabriel Lamé)의 분석
• 현대 컴퓨터 과학에서의 재발견

세특 기록 예시: "유클리드 호제법의 2300년 역사를 추적하는 과학사 프로젝트를 수행함. 고대 그리스에서는 기하학적 선분의 공통 측도를 찾기 위해 개발됐으나, 중세 아랍을 거쳐 근대 정수론으로 발전했고, 20세기 컴퓨터의 등장으로 알고리즘의 효율성이 재조명됨을 발견함. 특히 라메가 1844년 피보나치 수와의 관계를 증명한 과정을 분석하고, 시간복잡도 개념이 등장하기 전에도 수학자들이 효율성을 고민했음을 이해함."

🎨 예술/디자인과의 융합

활동 9: 유클리드 호제법과 황금비

목표: 연분수와 황금비의 관계 탐구

피보나치 수열의 연속된 두 항은 유클리드 호제법의 최악의 경우이며, 동시에 황금비에 수렴합니다.

세특 기록 예시: "유클리드 호제법을 시각화하는 과정에서 피보나치 수와 황금비의 관계를 발견함. 호제법을 기하학적으로 표현하면 사각형을 정사각형들로 분할하는 과정이 되며, 이것이 황금 나선과 연결됨을 확인함. Python의 matplotlib으로 이 과정을 시각화하고, 자연에서 발견되는 황금비(해바라기 씨앗 배열, 조개 껍데기 등)가 수학적으로 유클리드 호제법과 연결됨을 탐구함. 수학과 예술의 융합을 체험함."

🧬 생명과학/물리학과의 연결

활동 10: DNA 염기서열 분석

목표: 생물정보학에서의 활용

두 DNA 서열의 공통 패턴 찾기는 일종의 최대공약수 문제입니다.

세특 기록 예시: "생물정보학에서 DNA 염기서열의 공통 부분 서열을 찾는 문제가 유클리드 호제법과 유사한 원리를 사용함을 발견함. 두 문자열의 최장 공통 부분 수열(LCS) 문제를 연구하며, 수학 알고리즘이 생명과학 연구에 어떻게 적용되는지 탐구함. Python으로 간단한 DNA 서열 비교 프로그램을 작성하고, NCBI 데이터베이스의 실제 유전자 서열로 테스트함. 융합적 사고의 중요성을 깨달음."

유클리드가 우리에게 주는 교훈

2300년 전, 유클리드는 기하학 문제를 풀다가 최대공약수를 구하는 효율적인 방법을 발견했습니다.

당시에는 컴퓨터도 없었고, '알고리즘'이라는 개념조차 없었어요.

하지만 그가 발견한 원리는 시대를 초월했습니다.

• 중세 아랍 수학자들이 발전시켰고
• 17세기 유럽에서 정수론의 기초가 됐으며
• 20세기 컴퓨터 과학의 핵심 알고리즘이 됐고
• 21세기 암호화 기술의 토대가 됐습니다

진정한 원리는 시대를 초월합니다.

여러분이 지금 배우는 수학 공식, 알고리즘, 과학 원리도 마찬가지예요.

단순히 시험을 위해 외우는 게 아니라, 그 안에 담긴 원리를 이해하면, 그건 평생 여러분의 무기가 됩니다.

학원에서 함께 탐구해요

원당컴퓨터학원에서는 유클리드 호제법 같은 고전 알고리즘부터 최신 AI 기술까지, 원리를 중심으로 가르칩니다.

C++ 알고리즘반:

• 정보올림피아드 대비
• 유클리드 호제법 포함 정수론 완벽 정리
• 심화 알고리즘 문제 해결

Python 융합과정:

• 알고리즘을 직접 구현하며 이해
• 암호학, 생물정보학 등 융합 프로젝트
• 학생부 기록을 위한 맞춤형 탐구 활동

단순히 코드를 따라 치는 게 아니라, 왜 이렇게 작동하는지 이해하고, 어디에 활용할 수 있는지 생각하는 수업을 진행합니다.

2300년 전 유클리드처럼, 여러분도 시대를 초월하는 통찰을 발견할 수 있어요.

---

유클리드가 그랬듯이, 여러분도 단순한 원리에서 위대한 발견을 할 수 있습니다.

지금 바로 시작해보세요!

---

원당컴퓨터학원
📍 인천시 서구 당하동 장원프라자 502호
📞 032-565-5497

---

#유클리드 #유클리드호제법 #최대공약수 #알고리즘 #정보올림피아드 #수학탐구 #세특활동 #학생부종합전형 #원당컴퓨터학원 #인천학원 #서구학원 #당하동학원 #코딩교육 #Python #C언어 #암호학 #RSA #정수론 #수학의역사 #컴퓨터과학