CodeUtility
개발자의 삶을 더 쉽게!
Python 알고리즘

Euclidean GCD Algorithm in Python

Find the greatest common divisor in a few steps with Euclid's remainder trick, then compare with math.gcd.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개
배울 내용
  • What the GCD is
  • Euclid's algorithm
  • math.gcd in the standard library
Python 컴파일러에서 실행 →
gcd(48, 18)
  1. 48 % 18 = 12→ (18, 12)
  2. 18 % 12 = 6→ (12, 6)
  3. 12 % 6 = 0→ gcd = 6

Replace the pair with (b, a % b)

두 정수의 최대공약수(GCD)는 두 수를 모두 나누어떨어지게 하는 가장 큰 양의 정수입니다. 유클리드 호제법은 간단한 성질을 이용해 최대공약수를 아주 빠르게 구합니다. a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다는 성질입니다.

핵심 포인트

  1. gcd(a, b) equals gcd(b, a % b).
  2. Repeat until the remainder is 0; the other number is the answer.
  3. math.gcd(48, 18) gives the same result.

언제 사용하나요?

  • 논리적 사고력을 기르고 알고리즘이 동작하는 과정을 단계별로 이해합니다.
  • 데이터가 많거나 프로그램을 빠르게 만들어야 할 때 알맞은 방법을 고릅니다.
  • 시험, 과제, 코딩 면접을 준비합니다.

예제 코드

코드 실행 →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
이 예제의 실행 버튼 만들기

실행 결과

6

코드 설명

단계마다 (first, second) 쌍을 (second, first % second)로 바꿉니다. 나머지가 0이 되면 first에 남은 값이 최대공약수이므로, 48과 18의 최대공약수는 6입니다. abs() 함수는 결과가 항상 양수가 되게 합니다. 단계 수는 숫자 크기에 비해 아주 천천히, 대략 O(log n)으로 늘어납니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지