[Algorithm] 유클리드 호제법

이현우·2020년 7월 23일

Algorithm

목록 보기

1/3

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

노가다를 시도한다

어느 것 하나 쉽게 시작하는 것은 없다.
물론 비효율적인 방식인 것은 알지만, 처음 이런 과정도 없이 쉬운 길로 가려고 한다면, 이후에 이런 과정으로만 풀릴 수 있는 문제를 맞딱뜨렸을 때, 쉽게 접근할 수 없을 것이다.

따라서 이번 게시글뿐만 아니라 필자가 게재하는 알고리즘 게시글은 단순히 나의 풀이뿐만 아니라
조금 비효율적인 과정을 보여주면서 특정 부분을 개선시킨 알고리즘을 제시하는 방향으로 정리할 것이다.

아마 가장 먼저 떠올릴 수 있는 방법은 두 수 중 작은 수를 골라 1부터 {작은 수}까지 순차적으로 나눠서, 가장 큰 공약수를 알아내는 것일 것이다. 이 부분의 알고리즘은 다음과 같이 코드로 작성할 수 있을 것이다.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int gcd = 0;
    int orA, orB;
    cin >> orA >> orB;
	
    //두 수 중 최소를 고른다
    int minOf = min(orA, orB);
    
    for(int i = 1; i <= minOf; i++)
    {
    	if(orA % i == 0 && orB % i == 0)
        	gcd = i;
    }
    
    cout << gcd;
    
    return 0;
    
}

그러나 위의 과정은 두 수 중 가장 작은 것(n)을 기준으로 무조건 1부터 n까지 두 수를 나눠봐야한다. 이것보다 조금 더 효율적으로 공약수를 구할 수 없을까?

학교 수학과 연결 : 나머지정리

우리는 고등학교 1학년 때 나머지 정리라는 것을 배웠을 것이다. 아마 그 때의 기억을 되살려보자면 두 다항식이 차와 원래 다항식들의 인수가 같다는 것을 배웠을 것이다.

이는 자연수에서도 마찬가지로 두 수의 차는 두 수와 최대 공약수와 같다. 윗 문단에서는 고등학교 때 처음 배웠다고 가정했지만, 중학교 때 심화수학(?)을 한 학생들은 이를 유클리드 호제법이라는 멋있는 이름의 공식으로 배웠을 것이다.

이 공식으로 최대공약수를 아주 빠르게 구할 수 있는 알고리즘을 구현할 수 있다.

유클리드 호제법

두 수의 차와 두 수의 최대 공약수는 동일하다

증명도 할 수 있지만 실제 코드를 구현할 때에는 이러한 증명은 필요가 없을 것이라 사료되므로 하단에 별첨으로 증명을 첨부하겠다.

이 사실을 적용하면, 다음과 같이 생각할 수 있다.

두 수의 차와 두 수의 최대 공약수가 동일하네?
그럼 '두 수 중 작은 수'와 '두 수의 차'의 최대공약수를 구해도 되겠네

이를 반복적으로 적용하자. 한 수가 0이 나올 때까지 반복적으로 차를 구하면, 다른 한 수가 자명하게 최대공약수가 될 수밖에 없을 것이다. (무한강하)

이를 코드로 구현하면 다음과 같다. (getGcd 함수)

#include <iostream>
#include <algorithm>

using namespace std;

int getGcd(const int& a, const int& b)
{
    //두 수 중 큰 수와 작은 수로 구별하여 저장한다
    int maxOf = max(a, b);
    int minOf = min(a, b);
    
    //최대공약수가 maxOf로 결정되기까지 계속 차를 구한다
    while(minOf != 0)
    {
        int temp = maxOf % minOf;
        maxOf = minOf;
        minOf = temp;
    }
    
    //minOf는 0이 되고 maxOf는 최대공약수가 된다
    return maxOf;
}

int main()
{
    return 0;
}

위와 같이 최대공약수를 구할 때는 순차(선형)적으로 수들을 탐색하지 않고 특정 케이스로 분기하여 해결해야 할 케이스의 수를 확 줄였다.
유클리드 호제법을 활용한 알고리즘의 시간복잡도는 O(logN)이다. (노가다 방법은 O(N))

관련 문제

백준 9613번 GCD 합
https://www.acmicpc.net/problem/9613

우선 N 개의 수에서 두 개씩 짝지어서 그 쌍의 최대공약수를 더하는 것이므로

모든 수를 vector로 받고
두 수를 인덱싱해서 선택하여 두 수의 최대공약수를 구하고
이를 한 변수에 더하면 된다

필자는 위 알고리즘을 다음과 같이 구현하였다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//수의 크기가 커질 것을 대비
long getGcd(long a, long b)
{
    long maxOf = max(a, b);
    long minOf = min(a, b);

    while(min(maxOf, minOf) != 0)
    {
        long temp = maxOf % minOf;
        maxOf = minOf;
        minOf = temp;
    }

    return maxOf;
}

int main()
{
    int repeat;
    cin >> repeat;

    for(int i=0; i<repeat; i++)
    {
        int num;
        cin >> num;
        vector<long> nums;
        long ans = 0;
		
        //모든 수를 vector로 받는다
        for(int j=0; j<num; j++)
        {
            long temp;
            cin >> temp;
            nums.push_back(temp);
        }
		//두 수를 2중 for문으로 인덱싱한다
        for(int j=0; j<num-1; j++)
        {
            for(int k=j+1; k<num; k++)
            {
                //최대공약수를 ans에 더해 저장한다
                ans += getGcd(nums[j], nums[k]);
            }
        }
        cout << ans << endl;
        nums.clear();
    }

    return 0;
}