[Level 1] 최대공약수와 최소공배수

• 안녕하세요. BlockDMask 입니다.

• 프로그래머스 알고리즘 문제 C++ 언어로 풀어보겠습니다.
  171108 문제 빼먹음 -> 171214 완료

0. 제목

• 프로그래머스 Level 1 최대공약수와 최소공배수

• Programmers Level1 GCD & LCM

• C++ gcd, lcm

1. 문제 설명

• 두 수를 입력받아 두 수의 최대공약수(gcd)와 최소공배수(lcm)를 반환해주는 gcdlcm 함수를 완성해 보세요.

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

• 예를 들어 gcdlem(12, 54)가 입력되면, [6, 108]를 반환하면 됩니다.

2. 풀이 과정

• swap 함수를 통해서 항상 파라미터로 받은 a가 큰수가 되도록 하였습니다.

• 최대공약수(gcd)는 유클리드 알고리즘을 통해서 구하였습니다.
  유클리드 알고리즘에 대한 자세한 설명은 [바로가기]에 있습니다.

• 최소공배수(lcm)은 두 수의 배수중에 가장 작은 값 이므로, 
  두 수를 곱한 부분에서 최대 공약수를 나누어 준 값이 최소공배수가 됩니다.
  (공통 부분을 없앴으므로)

3. 소스 코드

//https://programmers.co.kr/learn/challenge_codes/149
//LEVEL1_GCDLCM
 
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
 
void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}
 
//최대 공약수(유클리드 알고리즘)
//a가 큰 수로.
int gcd(int a, int b){
    if(a<b) swap(a, b);
    while(b!=0){
        int tmp = a%b;
        a = b;
        b = tmp;
    }
    return a;
}
//최소 공배수
int lcm(int &a, int &b){
    return (a*b)/gcd(a, b);
}
 
vector<int> gcdlcm(int a,int b)
{
    vector<int> answer;
    answer.push_back(gcd(a, b));
    answer.push_back(lcm(a, b));
    return answer;
}

4. 인증

문제출처 : https://programmers.co.kr/learn/challenge_codes/149

감사합니다.