[레벨1] 최대공약수와 최소공배수 - 유클리드 호제법

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int a,b;
    if(n > m)
	swap(n,m);
    for(int i = 1; i <= n; ++i) // 최대공약수 구하기
    {
        if(n % i == 0 && m % i == 0)
            a = i;
    }
    
    // 최소 공배수 구하기
    if(n % m == 0) 
        b = n;
    else
    {
        int i = 1;
        while(true)
        {
            if((n * i) % m == 0)
            {
                b = n * i;
                break;
            }
            i++;
        }
    }
    
    answer.push_back(a);
    answer.push_back(b);
    return answer;
}

 

너무 무식하게 구현했다. -> 이것도 글을 수정하면서 조금씩 수정한 것

검색을 해보니 최대공약수를 구하는 알고리즘중 가장 빠른 유클리드 호제법이 존재.

 

여기서 깨달은 점은 최대공약수만 알면 최소공배수를 쉽게 구할 수 있다.

여기에다가 주어진 두 수를 곱하고 최대공약수로 나누면 그것이 최소 공배수.

 

위를 깨닫고 다시 코드를 다듬었을때.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int a,b;
    if(n > m)
        swap(n,m);
    
    for(int i = 1; i <= m; ++i)
    {
        if(n % i == 0 && m % i == 0)
            a = i;
    }
    
    b = (n * m) / a; // 최소 공배수구하기
    
    answer.push_back(a);
    answer.push_back(b);
    return answer;
}

좀 더 코드가 줄어들었다.

 

유클리드 알고리즘의 공식은 다음과 같다. -> 최대공약수를 구한다.

int GCD(int a,int b)
{
    int r;
    if(a < b)
        swap(a,b);
        
    while(true){
        r = a % b;
        if(r == 0) 
            return b;
        a = b;
        b = r;
    }
}

간단하게 60,48이 넘어왔다고 가정해보자.

 

1. r = 60 % 48. r에는 12가 저장. a = 48, b = 12

2. r = 48 % 12. r에는 0이 저장. 탈출. 최대 공약수는 12.

 

기존의 내코드는 1부터 더 큰 수의 범위까지 반복한다. -> 시간 복잡도 O(N)

이 코드는 단 2번만에 연산이 종료. 찾아보니 시간 복잡도는 로그 시간복잡도에 가깝다.

 

그리고 위 GCD함수를 이용한 LCM(최소 공배수구하기)함수

int LCM(int n, int m)
{
      return (n * m) / GCD(n,m);
}

 

그렇기에 유클리드 알고리즘으로 풀이한 코드

#include <string>
#include <vector>

using namespace std;

int GCD(int n, int m)
{
    int r;
    if(n < m)
        swap(n,m);
    
    while(true)
    {
        r = n % m;
        if(r == 0)
            return m;
        n = m;
        m = r;
    }
}

int LCM(int n, int m)
{
    return (n * m) / GCD(n,m);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    int a = GCD(n,m), b = LCM(n,m);
    
    
    answer.push_back(a);
    answer.push_back(b);
    return answer;
}