[프로그래머스 1단계] 알고리즘 1. 최대공약수 최소공배수 구하기

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 1. 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환해주는 gcdlcm 함수를 완성해 보세요

풀이 : 

최대공약수(gcd) = 유클리드 알고리즘으로 풀어라

최소공배수(lcm) = gcd * (a / gcd) * (b / gcd) = (a * b) / gcd

최대공약수를 구하는 코드는 반복문으로 다음과 같이 작성할 수 있다.

int gcd(int a, int b){

int gcd_value = (a < b) ? a : b;  //a, b 중 작은 수를 가져옴

while(gcd_value >= 1){            //이 값이 1이 될때까지

//만약 a와 b랑 둘 다 나누어 떨어지면

//최대공약수 반환

if ((a % gcd_value == 0) && (b % gcd_value == 0))

return gcd_value;

gcd_value -= 1;

}

//이 반복문을 벗어나면 둘 사이의 최대공약수는 1이다.

//즉 서로소이다.

return 1;

}

그러나 유클리드 알고리즘으로 보다 깔끔하게 코드를 작성할 수 있다. 유클리드 알고리즘은 다음과 같은 성질이 있다.

1) a,b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대 공약수와 같다. gcd(a, b) = gcd(b, a%b)

2) 어떤 수 x와 0의 최대공약수는 바로 자신이다. gcd(x, 0) = x

쉽게 표현하기 위해 예를 들어보자. 6, 8이 있다고 할 때 유클리드 알고리즘은

gcd(6, 8) = gcd(8, 6%8=6) = gcd(6, 8%6=2) = gcd(2, 6%2=2) = gcd(2, 2%2=0) = gcd(2, 0) = 2 

따라서 6, 8 의 최대공약수는 2이다. 위의 두 성질을 이용하면 재귀 함수를 이용하여 새로운 최대공약수 알고리즘을 작성할 수 있다.

int uclid_gcd(int a, int b){

if(b == 0)

    return a;

return uclid_gcd(b, a%b);

}

또한 이 코드는 삼항연산자를 이용하여 한줄로 줄일 수 있다.

int uclid_gcd(int a, int b){

return (b == 0) ? a : uclid_gcd(b, a%b);

}

밑 코드는 필자가 작성한 정답 코드이다.

#include<vector>

#include<iostream>

using namespace std;

//작성코드

int uclid_gcd(int a, int b){

return (b == 0) ? a : uclid_gcd(b, a%b);

}

vector<int> gcdlcm(int a,int b)

{

vector<int> answer;

//작성 코드

//최대송약수 최소공배수 구하는 코드

int gcd = uclid_gcd(a, b);  

int lcm = a * b / gcd;

//벡터에 값을 넣는 코드

answer.push_back(gcd);  //gcd = Greatest Common Divisor

answer.push_back(lcm);  //lcm = Least Common Multiple

//

return answer;

}

int main()

{

int a=3, b=12;

vector<int> testAnswer = gcdlcm(a,b);

cout<<testAnswer[0]<<" "<<testAnswer[1];

}