[코딩 팁] 최대공약수 : 유클리드 호제법 원리

✍️ 최대공약수와 유클리드 호제법

코딩 테스트에서 심심치 않게 등장하는 최대공약수 구하기

2부터 시작하는 반복문으로 구할 수 있지만 유클리드 호제법을 사용하면 보다 효율적으로 구할 수 있다.

 

유클리드 호제법의 과정은 다음과 같다.

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

2. 나누는 수를 나머지로 계속 나눈다.

3. 나머지가 0이 나오면 나누는 수가 최대공약수이다.

 

$1512$와 $1008$의 최대공약수를 유클리드 호제법으로 풀어보면

 

$1512 = 1008 * 1 + 504$

$1008 = 504 * 2 + 0 $

 

두 수의 최대공약수는 504이다.

 

💡 유클리드 호제법 이해하기

나는 원리를 알지 못한다면 금방 까먹는 사람으로서... 대충이라도 원리를 정리해 보려 한다.

 

(1) 어떤 수 $A$를 $B$로 나눈다면 다음과 같이 표현한다.

$$ A = B * Q + R$$

 

(2) 이때 $A$와 $B$의 최대공약수를 $G$라고 했을 때 $A = a * G$ $B = b * G$로 나타낼 수 있고 위 식에 대입해 $R$에 대해 정리하면 다음과 같이 표현할 수 있다.

$$ a * G = b * G * Q + R$$

$$R = a * G - b * G * Q$$

$$ = G * (a - b * Q)$$

 

(3) 즉 나머지 $R$도 최대 공약수$(G)$를 갖고 있으니 $B$와 $R$의 최대 공약수가 곧 $A$와 $B$의 최대공약수를 구하는 것과 동일하다.

 

🍊 코드

[유클리드 호제법 반복문]

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

 

[유클리드 호제법 재귀 함수]

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

 

✏️ 관련 문제

최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수