[Algorithm] 최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

문제 유형

• 최대 공약수
• 최소 공배수

 

문제 아이디어

• 최대 공약수는 유클리드 호제법으로 풀 수 있다.
• 유클리드 호제법
  • 최대공약수 (GCD)
    • "a를 b로 나눈 나머지가 r일 떄, a와 b의 최대 공약수는 b와 r의 최대공약수와 같다."
    • 두 수 (48, 18)
      • 48 % 18 = 12,
      • 18 % 12 = 6,
      • 12 % 6 = 0, 최대공약수는 6이다.
  • 최소공배수 (LCD)
    • 두 수를 최대공약수로 나눈 값과 같다.
    • 두 수 (48, 18)
      • 48 * 18 / 6

 

코드 작성

#include <vector>

using namespace std;

int gcd(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    
    return a;
}

int lcd(int a, int b)
{
    return a * b / gcd(a, b);
}

vector<int> solution(int n, int m) {
    vector<int> result;
    result.push_back(gcd(n,m));
    result.push_back(lcd(n,m));
    
    return result;
}

 

참고

최소공배수와 최대공약수 알고리즘 (유클리드 호제법)