BOJ(2609).cpp 유클리드 호제법

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수(Greatest Common Divisor) 를 구하는 알고리즘이다. 비교대상의 두 개의 자연수 a와 b에서 a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."(단 a>b) 라는 원리를  활용한 알고리즘입니다.

ex) GCD(24,18) -> GCD(18,6) -> GCD(6,0) : 최대공약수 = 6

 

재귀 함수 활용

int GCD(int a, int b)
{
    if (a > b)
    {
        if (b == 0)
        {
            return a;
        }
        else
        {
            return GCD(b, a % b);
        }
    }
}

반복문 활용

int GCD(int a, int b)
{
    if (a > b)
    {
        while (1)
        {
            int r = a % b;
            if (r == 0)
            {
                return b;
            }
            a = b;
            b = r;
        }
    }
}

다항식

int a = 4;
int b = 8;
int c = 24;
	
int res = GCD(a,b); // 1. a와 b의 최대공약수 -> res 저장
res = GCD(res,c); //   2. a와 b의 최대공약수 res와 c의 최대공약수 

printf("%d",res);

다항식일 경우 GCD를 구하는 함수를 먼저 구현하고 a와b의 GCD를 구한다음 c와 GCD를 구하는 순차적인 방식으로 구해야 한다.

 

최소공배수 (Least Common Multiple, Lowest Common Multiple)

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

GCD를 구하는 함수를 구현하고 a * b / GCD(a,b)를 해주면 최소공배수 이다.

 

 

2609.cpp

#include <iostream>
using namespace std;

int GDC(int a, int b)
{
    if (a > b)
    {
        if (b == 0)
        {
            return a;
        }
        else
        {
            return GDC(b, a % b);
        }
    }
}
int LCM(int a, int b)
{
    return a * b / GDC(a, b);
}
int main()
{
    int i, j;
    cin >> i >> j;
    cout << GDC(i, j) << endl;
    cout << LCM(i, j);
}