최대공약수, 최소공배수 구하기 알고리즘(+약수 구하기)

[최대공약수 / 최소공배수 알고리즘]

정보처리기사 실기 문제 중 한 가지인 최대공약수/최소공배수 알고리즘을 공부하면서 포스팅을 해 본다.

보너스로 약수 구하는 알고리즘도 간단하게 남겨본다.

1. 최대공약수 (Greatest Common Divisor)

최대공약수는 0이 아닌 두 개 이상의 정수의 공통되는 약수이다. 보통 최대공약수를 구하라 하면

이와 같이 그려서 구할 것이다. 하지만 프로그래밍 언어로 변환하여 나타내려면 어려울 것이다.

따라서 프로그래밍 언어로 구현하고자 할 때는 다음과 같은 방법으로 나타낸다.

이와 같이 두 수의 나머지값으로 최대공약수를 구할 수 있다.

글로만 봐서는 이해가 어려울 수 있으니 최대공약수를 구하는 함수와 같이 보자.

//gdc : 최대공약수
int get_gdc(int big, int small)
{
    int big2 = big, small2 = small;
 
    //mod_bs : 나머지 값을 받을 변수
    int mod_bs = (big2 % small2);
 
    while (mod_bs != 0)
    {
        //나머지가 0이 아니면 big변수에 small값, small변수에 나머지값을 넣고 다시 반복
        big2 = small2;
        small2 = mod_bs;
        mod_bs = (big2 % small2);
    }
    //반복이 끝났다는 것은 나머지가 0일때 이므로 이때 small변수값이 최대공약수!
    return small2;
}

이 위의 최대공약수를 구하는 방법을 이해하는 것은 상대적으로 어렵고 복잡할 수 있으니 저 방법을 코드로 어떻게

짰는가를 이해했으면 좋겠다. 이해를 한다면 응용문제가 나와도 어렵지 않게 해결할 수 있을테니까!

2. 최소공배수 (Least Common Multiple)

최소공배수는 2개 이상의 수의 공배수 중 가장 최소인 값으로 소인수분해하여 각 수 중에 어느 한 곳에라도 있는

약수를 찾아 곱해준 값이다.

최소공배수를 일반적으로 구할 때는

이 그림에서 보면 3*5*4 = 60 이처럼 구한다.

하지만 이 방식을 자세히 분석해보면 다음과 같다.

바로 15*12 이 값을 두 수의 최대공약수로 나눈 값이 바로 최소공배수가 되는 것이다.

그럼 프로그래밍적으로 구할 때, 두  수 x, y 그리고 최대공약수 총 3개의 수만 있으면 OK!

//lcm : 최소공배수
int get_lcm(int x, int y, int gdc)
{
    return (x * y) / gdc;
}

               (이처럼 간단히 나타낼 수 있다!)

+BONUS) 약수 구하기

약수는 말 그대로 어떤 수를 나누어 떨어지게 하는 수이다. 즉, 나누면 나머지가 0인 값을 찾으면 그만이다!

//divisor : 약수
void print_div(int x)
{
    int i;
    for (i = 1; i <= x; i++)
    {
        if (x % i == 0)            //약수는 자신보다 작거나 같은 값 중 나눌 때 나머지가 0인 값이다.
            printf("%d ", i);
    }
    printf("\n");
}

함수 내에서 printf처리를 해 바로 출력하도록 만들어봤다. 

본격적으로 정보처리기사를 공부하기 앞서 워밍업 겸 실기문제를 찾아서 내 힘으로 코드를 짜 보았다.

이렇게 내 기록을 포스팅하는 것이 나름 재미있어졌다.  이 기세를 몰아 더 열심히 알고리즘 공부를 해야겠다