GCD(최대공약수, Greatest Common Divisor) 알고리즘

1. GCD(최대공약수)란?

두 숫자를 나눌 수 있는 가장 큰 숫자를 찾는 것이라고 보면 된다.

 

예를 들어, 48과 18의 최대공약수(GCD)는 6이다.

왜냐하면 6은 48도 나누고, 18도 나누는 가장 큰 수이기 때문이다.

 

 

 

---

2. 가장 쉬운 방법 (완전탐색)

모든 숫자를 하나씩 확인하면서 공약수를 찾고, 가장 큰 걸 선택하는 방법이다.

 

✅ 방법

1부터 두 수 중 작은 숫자까지 하나씩 나누어보고, 둘 다 나눠지는 가장 큰 수를 선택한다.

 

❌ 단점

숫자가 커지면 너무 오래 걸린다. 예를 들어, 1,000,000,000 같은 큰 숫자를 다 확인하려면 시간이 너무 많이 든다.

 

📌 코드 예제

def gcd_brute_force(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

 

하지만 이 방법은 비효율적이다.

 

 

 

---

3.  빠른 방법: 유클리드 알고리즘

유클리드 알고리즘은 “큰 수에서 작은 수를 계속 빼면 결국 GCD가 나온다”는 원리를 사용한다.

하지만 빼는 대신 나머지를 사용하면 더 빨라진다.

 

✅ 방법

1. 큰 수를 작은 수로 나눈다.

2. 나머지를 구한다.

3. 작은 수와 나머지로 다시 최대공약수를 구한다.

4. 나머지가 0이 되면, 그때 작은 수가 바로 GCD!

 

💡 예제: GCD(48, 18)

• 48 ÷ 18 → 몫 = 2, 나머지 = 12

• 18 ÷ 12 → 몫 = 1, 나머지 = 6

• 12 ÷ 6 → 몫 = 2, 나머지 = 0

• 나머지가 0이 되었다! 6, 0이 남았고, 정답은 6 🎯

 

📌 코드

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

 

이 방법은 숫자가 엄청 커도 빠르게 실행된다! 🚀

시간 복잡도는 O(log(min(a, b)))로, 완전탐색보다 훨씬 빠르다.

 

 

 

---

3. 확장 유클리드 알고리즘 (더 나아가기)

이 알고리즘은 GCD뿐만 아니라, 아래 식을 만족하는 x, y도 구한다.

 

ax + by = gcd(a, b)

이 식은 나머지 연산에서 역원을 구할 때 매우 유용하다.

 

📌 코드

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

 

 

 

---

4. 정리

방법	속도(시간 복잡도)	특징
완전 탐색	느림 O(n)	작은 숫자에는 괜찮지만 비효율적
유클리드 알고리즘	빠름 O(log(n))	실제로 가장 많이 사용됨
확장 유클리드	빠름 O(log(n))	추가로 x, y도 구할 수 있음