1줄로 짜는 최대공약수와 최소공배수 계산 알고리즘


작성일 : 2017-01-22 05:22:37
조회수 : 2846


본문

이걸 직접적으로 물어본 경험은 없지만, 최대공약수와 최소공배수를 구하는 알고리즘을 실제로 작성해본 적 없는 분들이 의외로 많음을 알았습니다. 여기서는 유클리드 호제법을 이용하여, 최대공약수(GCD)와 최소공배수(LCM)을 한 줄로 코딩하는 방법을 설명하겠습니다.


먼저 유클리드 호제법은 무려 기원전 300년 경에 유클리드 원론에 쓰인 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘입니다. 이 호제법의 핵심은 어떤 임의의 수 $a$, $b$에 대해 $a \mod b = r$ 이라고 한다면, $gcd(a,b) = gcd(b,r)$ 이 성립한다는 점을 이용합니다. 이렇게 반복하면서 최종적으로 나머지가 0이 되는 순간 그 나누는 수가 최대공약수가 됩니다. 여기서는 수학적 증명에 대해서는 다루지 않겠습니다. 수학적 증명은 여기서 읽어보실 수 있습니다.


이제 이것을 소스코드로 구현을 해야 합니다. 먼저 말 그대로 소스코드로 이 내용을 옮겨봅시다.


int gcd(int a, int b)

{

    while (1)

    {

        int r = a%b;

        /*나머지가 0이라면*/

        if (r == 0)

            return b;


        /*gcd(a,b) = gcd(b,r)*/

        a = b;

        b = r;

    }

}


제목에서 말했다시피 우리는 이 소스를 1줄로 압축할 것입니다. 압축하는 과정에서 위의 소스를 재귀함수의 형태로 변경하겠습니다. 즉, r=a%b 부분을 만들어 검사하는 대신, b의 값을 파라미터 a의 위치에, a%b 을 파라미터 b의 위치로 넘겨주어, 나머지가 0이 될 때까지를 체크합니다. 이럴 경우 소스코드가 다음과 같이 바뀝니다.


int gcd(int a, int b)

{

    if (b == 0) return a;

    else return gcd(b, a%b);

}


여기서 깨끗한 문법은 아니지만, 다음과 같은 작업을 거쳐 최종적으로 1줄로 최대공약수를 구할 수 있습니다.

int gcd(int a, int b)

{

    return !b ? a : gcd(b,a%b);

}


다소 길었던 소스가 1줄로 압축되었음을 알 수 있습니다. 최소공배수는 어떻게 구할 까요? 최소공배수는 두 수의 공통적인 배수이므로, 두 개의 수를 곱한 다음, 최대공약수로 나눈 것이 항상 답이 됨을 알 수 있습니다. 그러므로 이 소스 역시 1줄로 짤 수 있습니다.

int lcm(int a, int b)

{

    return a*b/gcd(a,b);

}


이 2가지의 원리를 이해하고 소스를 외운(?)다면, 이것들을 이용한 문제를 아주 쉽게 해결할 수 있을 것입니다. 소스코드에는 예제 소스를 첨부하겠습니다.


클릭하여 소스코드 보기

#include<iostream>
using namespace std;

int gcd(int a, int b){return !b ? a : gcd(b, a%b);}
int lcm(int a, int b) { return a*b / gcd(a, b); }
int main()
{
    cout << gcd(10, 24) << "\n" << lcm(22,66);
}

1줄로 짜는 최대공약수와 최소공배수 계산 알고리즘 - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.