최소공배수 최대공약수

문제

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

풀이

단순하게 최대공약수와 최소공배수를 출력하는 문제이다.

최대 공약수와 최소 공배수를 구하는 좋은 알고리즘은 많이 있지만 단순하고 직관적으로 구하도록 코딩하였다(사실 머리를 안쓴....)

Level 2에서 GCD와 LCM에 관한 문제가 있는데 거기서는 유클리드 호제법을 사용하였다.

1부터 두 수의 곱까지 반복하며 공통적으로 나뉘는 수를 구한다. 그리고 마지막(a*b)까지 탐색하니까..(당연히 이게 최대공약수..)

최소공배수는 최대공약수와 최대공약수로 각각의 수를 나눈 값의 곱이다.

최소공배수(LCM) = A * B * 최대공약수(GCD)

소스 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> gcdlcm(int a, int b)
{
  vector<int> answer;
  int         gcd, lcm;
  int         temp = 0;
  for (int i = 1; i < a * b; i++)
  {
    if ((a % i == 0) && (b % i == 0))
    {
      temp = i;
    }
  }
  gcd = temp;
  lcm = gcd * (a / gcd) * (b / gcd);
  answer.push_back(gcd);
  answer.push_back(lcm);
  return answer;
}

int main()
{
  int         a = 3, b = 12;
  vector<int> testAnswer = gcdlcm(a, b);
  cout << testAnswer[0] << " " << testAnswer[1];
}

알고리즘 문제 Level 1 | 프로그래머스