최대공약수와 최소공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

풀이

#include <string>
#include <vector>

using namespace std;

int max(int a, int b)
{
    while(b != 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    int g = max(n , m);
    int l = (n * m) / g;
    
    answer.push_back(g);
    answer.push_back(l);
    
    return answer;
}

풀이 방식

• 유클리드 호제법을 사용해 최대공약수를 구하기
  -> 두 정수 a, b에 대해 a를 b로 나눈 나머지 c를 구하고 b와 c로 다시 과정을 반복해서 나머지가 0이 되면 그 수가 최대공약수
• while 문 : 유클리드 호제법은 O(logN)만큼만 반복해서 매우 빠르고 반복 횟수도 적으니 while이 효율적
• 조건 : 종료 조건이 나머지가 0이 될때, 즉 a가 아니라 b가 0이 될때가 최대공약수
• a, b 의 크기는 고려를 안해도 되나?
  -> 안해도 됨 어차피 b 가 이 될때까지 반복하면서 결국 최대공약수에 도달하기 때문
  Ex) gcd(12, 30) : 12 % 30 = 12 -> gcd(30, 12) -> 30 % 12 = 6 처럼 어차피 정렬됨.
• 최소 공배수 : 두 수의 고베서 최대 공약수를 나누기

다른 풀이

• C++17 이상에서는 gcd와 lcm라는 라이브러리 함수를 이용해서 쉽게 구할 수 있음

#include <string>
#include <vector>
#include <numeric>  // std::gcd, std::lcm

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    int g = gcd(n, m);       // 최대공약수
    int l = lcm(n, m);       // 최소공배수
    
    answer.push_back(g);
    answer.push_back(l);
    
    return answer;
}