JUNGOL...45

Beginner_Coder/수학1/최대공약수와최소공배수

---

문제                                            

두개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

입력 형식                                     

입력 파일의 첫째 줄에는 두 개의 자연수가 주어진다.

이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력 형식                                     

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

입력 예                                        

24 18

 

출력 예                                        

6

72

 

Hint!

최대공약수(GCD)란?

어떤 두 수 이상의 공통인 약수를 그 수들의 공약수라 하고 공약수들 중 가장 큰 수를 최대공약수라 한다. 

공약수는 최대공약수의 약수가 된다. 예를 들어 8의 약수는 1, 2, 4, 8이고 12의 약수는 1, 2, 3, 4, 6, 12이므로 8과 12의 공약수는 1, 2, 4 세 개이고 8과 12의 최대공약수는 공약수 중 가장 큰 수인 4이다. 

 

최소공배수(LCM)란? 

어떤 두 수 이상의 공통인 배수를 그 수들의 공배수라 하고 공배수들 중 가장 작은 수를 최소공배수라 한다. 공배수는 최소공배수의 배수가 된다. 예를 들어 8의 배수는 8, 16, 24, 32, 40, 48.... 이고 12의 배수는 12, 24, 36, 48, 60... 이므로 8과 12의 공배수는 24, 48... 이고 8과 12의 최소공배수는 공배수 중 가장 작은 수인 24이다. 

 

코드1 

int gcd_get(int x, int y)
{
    int i, ans;
    for (i = 1; i <= x; i++)
    {
        if (x % i == 0 && y % i == 0)
        {
            ans = i;
        }
    }
    return ans;
}
 
int main()
{
    .....
    gcd = gcd_get(a, b);
    lcm = a * b / gcd;
    .....
}

 

코드분석

gcd_get(int x, int y) 함수는 두 개의 수를 x와 y로 전달받아 최대공약수를 리턴해주는 함수이다. 

1부터 두 수중 한 개의 값(x)까지 모두 확인하면서 두 수의 공약수인지 확인하여 저장해 두었다가 그 값을 리턴하게 된다. 

공약수 중 맨 마지막 값이 저장되므로 그 수가 최대공약수가 된다. 

최소공배수(lcm)는 별도의 함수를 작성하여 구할 수도 있겠지만 두 수의 최대공약수를 알고 있다면 다음의 규칙을 이용하여 쉽게 구할 수 있다. 

두 수의 곱은 그 두수의 최대공약수와 최소공배수의 곱과 같다. 

a와 b의 최대공약수를 gcd(a, b), a와 b의 최소공배수를 lcm(a, b)라 하면 a * b = gcd(a, b) * lcm(a, b) 따라서 두 수의 최대공약수를 알 경우 최소공배수는 두 수의 곱을 최대공약수로 나눈 몫을 구하면 된다. (lcm = a * b / gcd) 

이 문제의 경우 x의 값이 최대 10000이므로 전혀 문제가 발생할 것이 없지만 만약 x의 값이 1억 이상의 큰 수라면 속도가 늦어질 수 있으므로 시간을 줄이기 위해 추가 작업이 필요하다. 

 

시간을 줄이기 위한 방법을 몇 가지 살펴보도록 하자. 

1) 1부터 x와 y중 작은 수까지만 살펴보면 조금은 줄일 수 있지만 큰 도움이 되지는 않는다. 

2) 두 수중 한 개 수에 대한 약수를 모두 구한 후, 그 약수들 중 다른 한 개 수의 약수가 되는 최대값을 구한다. 제곱근 만큼만 반복해서 모든 약수를 구하는 방법은 앞에서 익힌 바 있다. 

3) 프로그램에서 최대공약수를 가장 빠르고 간단하게 구하는 방법은 아래에 소개하는 유클리드 호제법을 이용하는 것이다. 

 

유클리드 호제법(Euclidean algorithm) : 

A를 B로 나눈 나머지가 r이라면 A와 B의 최대공약수는 B와 r의 최대공약수와 같다. GCD(A, B) = GCD(B, r) 이 원리를 이용하면 두 수의 최대공약수를 간단하게 구할 수 있다. 

이 방법으로 24과 16의 최대공약수를 구하는 과정을 살펴보면 다음과 같다. 

GCD(30, 18) = GCD(18, 12) = GCD(12, 6) = 6 * 30을 18로 나눈 나머지는 12, 18을 12로 나눈 나머지는 6, 12를 6으로 나눈 나머지는 0이므로, 30과 18의 최대공약수는 12와 6의 최대공약수인 6과 같다. 

 

코드2는 유클리드 호제법을 이용하여 최대공약수를 구하는 함수이다. 

코드3은 같은 내용을 재귀함수를 이용하여 더 간단하게 구현한 것이다. 

최대공약수나 최소공배수등과 관련된 문제를 해결하기 위해 항상 편리하게 활용할 수 있으므로 잘 익혀두는 것이 좋다. 

 

코드2 

int gcd_get(int x, int y)
{
    int r;
    while (y!=0)   // y 0이면 x가 최대공약수이므로 종료한다.
    {
        r = x % y; // 나머지를 구한후
        x = y; // x를 y로
        y = r; // y를 r로 바꾸고 다시 반복한다.
    }
    return x; // 최대공약수를 리턴한다.
}

 

코드3 

int gcd_get(int x, int y)
{
    if(y == 0) return x; // y 0이면 x가 최대공약수이다.
    return gcd_get(y, x % y); // x와 y의 최대공약수는 y와 x % y 의 최대공약수와 같다.
}

---

GCDAndLCM1.h

#include <iostream>

class GCDAndLCM1 : public Base
{
private:
	int GetGCD(int a, int b);
};

 

GCDAndLCM1.cpp

void GCDAndLCM1::Code()
{
	int a, b;

	std::cin >> a >> b;

	int GCD{ GetGCD(a, b) };
	int LCM{ a * b / GCD };

	std::cout << GCD << '\n';
	std::cout << LCM;
}

int GCDAndLCM1::GetGCD(int a, int b)
{
	if (b == 0)
	{
		return a;
	}
	return GetGCD(b, a % b);
}

 

Beginner_Coder/수학1/최대공약수, 최소공배수

---

문제                                            

n개의 정수를 입력받아서 최대공약수와 최소공배수를 구하는 프로그램을 작성하여 보자.

 

입력 형식                                     

첫째 줄에 N (2≤N≤10) 을 입력 받고 다음 줄에 N개의 정수를 공백으로 구분하여 입력 받는다.

입력 받는 정수는 2이상 10,000 이하이다. 데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.

 

출력 형식                                     

입력받은 정수들의 최대공약수와 최소공배수를 공백으로 구분하여 출력한다.

최소공배수는 20억 이하의 정수이다.

 

입력 예                                        

3

2 8 10

 

출력 예                                        

2 40

 

Hint!

두 개의 수 A와 B의 최대공약수를 D라 하면, 세 개의 수 A, B, C의 최대공약수는 D와 C의 최대공약수와 같다.

이런 규칙을 이용하면 두 수의 최대공약수를 구하는 함수 한 개만으로도 여러 수의 최대공약수를 구할 수 있다. 

최소공배수 역시 두 수의 최소공배수를 구해 나가는 방법으로 구할 수 있다. 

a배열에 N개의 수가 저장되어 있다고 가정한다면 다음과 같이 구현할 수 있다. 

 

코드 

gcd = lcm = a[0];
for (i=1; i < N; i++) { 
    gcd = gcd_get(gcd, a[i]); 
    lcm = lcm / gcd_get(lcm, a[i]) * a[i];
}

 

코드분석 

첫 번째 수를 최대공약수(gcd)로 정하고 두 번째 수부터 이전까지의 최대공약수(gcd)와 현재 배열의 값(a[i])의 최대공약수를 구하여 다시 gcd에 저장한다. 

이러한 작업을 마지막까지 반복하면 모든 수의 최대공약수가 구해진다. 

최소공배수도 같은 방법으로 구할 수 있다.

---

GCDAndLCM2.h

#include <iostream>

class GCDAndLCM2 : public Base
{
private:
	int GetGCD(int a, int b);
};

 

GCDAndLCM2.cpp

void GCDAndLCM2::Code()
{
	int n;
	int arr[10]{};

	std::cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		std::cin >> arr[i];
	}

	int GCD{ arr[0] }, LCM{ arr[0] };
	for (int i = 1; i < n; i++)
	{
		GCD = GetGCD(GCD, arr[i]);
		LCM = LCM * arr[i] / GetGCD(LCM, arr[i]);
	}

	std::cout << GCD << ' ' << LCM;
}

int GCDAndLCM2::GetGCD(int a, int b)
{
	if (b == 0)
	{
		return a;
	}
	return GetGCD(b, a % b);
}

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Beginner_Coder/수학1/최대공약수와최소공배수-JUNGOL

Beginner_Coder/수학1/최대공약수, 최소공배수-JUNGOL