[프로그래머스]C++ LV1 최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

1.문제 설명

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

 

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3,12]
2	5	[1,10]

 

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

 

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

2.문제풀이

• 최대공약수와 최소공배수를 구하는 함수를 작성한다.
• 작성한 함수를 이용해 answer벡터에 첫 번째 원소에는 최대공약수를 두번째 원소에는 최소공배수를 넣는다.

먼저 최대공약수와 최소공배수의 의미부터 살펴 보도록 하자.

최대공약수 : 두 수의 공약수 중 가장 큰 수를 의미한다.

- 예를 들어 20과 30의 최대 공약수를 구하고자 한다. 

20의 약수는 1,2,4,5,10,20이고 30의 약수는 1,2,3,5,6,10,15,30이다.

두수의 공약수(두 수의 공통된 약수)는 1,2,5,10이고 이중 가장 큰 수인 10이 최대공약수가 된다!!

 

최소공배수 : 두 수의 공배수 중 가장 작은 수를 의미한다.

-예를 들어 20과 30의 최소 공배수를 구하고자 한다.

20의 배수는 20, 40, 60, 80· · · · 이고  30의 배수는 30, 60, 90· · · ·이다

두수의 공배수(두 수의 공통된 배수) 중 가장 작은 수인 60이 최소공배수가 된다!!

  

• 최대공약수 구하기

최대공약수를 구하는 대표적인 알고리즘 유클리드 호제법을 사용한다. 유클리드 호제법은 정수 a와 b가 있을 때 큰 숫자에서 작은 숫자로 나눈 나머지를 구한다. a를 작은 수인 b로 바꾸고, b는 나머지 숫자로 바꾼다. 그렇게 a자리에 오게 된 작은수와 b자리에 오게된 나머지 숫자를 나누는 이 과정을 반복하면서 나머지 숫자가 0이 될 때까지 반복하도록 한다. 수학적인 공식으로는 GCD(a,b)=GCD(b,a mod b)라고 한다.

 

• 최소공배수 구하기

최대공약수를 구했다면 최소공배수를 구하는 것은 비교적 간단하다. 두 수를 곱한 다음 최대공약수로 나눠주기만 하면 된다.

 

3.소스코드

#include <string>
#include <vector>

using namespace std;

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

int lcm(int a,int b)
{
    int c = (a * b) / gcd(a,b);
    return c;
}

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

 

4.다른 풀이

C++17부턴 gcd,lcm함수를 지원한다.이 함수들은 <numeric> 헤더에 포함되어 있다. 

#include <string>
#include <vector>
#include <numeric>

using namespace std;

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