<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

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

BlockDMask 2017. 12. 14. 14:00
반응형
  • 안녕하세요. 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. 소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//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;
}
cs


4. 인증


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

감사합니다.

반응형