유클리드 알고리즘

유클리드 알고리즘

💡

두 수의 최대공약수를 구하는 방법

정의

두 수 p, q(p>q)의 공약수 집합은 p-q와 q의 공약수 집합과 같다.

증명

p, q의 공약수 g가 존재한다고 해보자

그럼 다음과 같이 나타낼 수 있다.

p = p’g

q = q’g

이때 p-q = (p’ - q’)g 이므로

g는 p-q의 약수이며, q의 약수이다.

구현

위를 이용하여 코드로 구현해보자

int gcd(int p, int q) {
        if (p < q) {
            int tmp = q;
            q = p;
            p = tmp;
        }

        if (q == 0) {
            return p;
        }

        return gcd(p - q, q);
    }

짧은 코드로 구현이 가능하나, 위 코드를 보면 p와 q의 차이가 클 경우에 많은 연산이 이루어 질 수 있다는 단점이 있다.

gcd(1024,6)=gcd(1018,6)=gcd(1012,6)=…

결국 우리가 원한하는 답은 gcd(4,6)=gcd(2,0) 이 될 것이다.

이를 좀 더 빨리 할 수 있는 방법은 없을까?

우리는 나머지 연산을 이용하여 다음을 구해보도록 하자

왜 나머지 연산으로 가능한지 살펴보자

p % q = q * m + r 이다.

q를 m번 빼고 난 나머지가 r이 되는 것이다.

따라서 1024 % 6 연산을 하면 4가 되어 빠르게 줄여나갈 수 있다.

p<q인 경우를 살펴보자

메소드 내에서 gcd(q, p%q)를 호출을 할 때 p%q 인 경우를 보자

위 경우는 p가 더 작으므로 p값이 그대로 나온다.

따라서 호출을 할 때 마다 p<q 인 경우를 처리하지 않아도 된다.

위를 바탕으로 구현한 코드를 보자

int gcd2(int p, int q) {
        if (q == 0) {
            return p;
        }

        return gcd2(q, p % q);
    }

위 코드보다 간단하게 구현된 것을 알 수 있다.

Uploaded by N2T