[BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법

[BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법

 

BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수

유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와 최소 공배수를 구하는 문제

 

 

---

 

문제

 

풀이

 

1. 유클리드 호제법

A = 106, B = 16

1.

C = A % B = 106 % 16 = 10

A <- B, A가 16이 된다.

B <- C, B가 10이 된다.

2.

C = A % B = 16 % 10 = 6

A <- B, A가 10이 된다.

B <- C, B가 6이 된다.

3.

C = A % B = 10 % 6 = 4

A <- B, A가 6이 된다.

B <- C, B가 4가 된다.

4.

C = A % B = 6 % 4 = 2

A <- B, A가 4이 된다.

B <- C, B가 2가 된다.

5.

C = A % B = 4 % 2 = 0

끝, 106과 16의 GCD는 'B'값, 즉 2가 된다.

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나입니다.
A와 B를 나눈 나머지 값을 R이라고 한다면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같습니다!
이 성질을 이용하여, B(혹은 Determinant)를 이전의 나머지 값으로 나누는 작업을 반복합니다.
최종적으로, 나머지 값이 0이 되었을 때, "마지막 B" 값이 A와 B의 최대 공약수가 되는 것입니다.

 

2. 최소공배수 공식

A와 B의 최소 공배수 = (A * B) / gcd(A, B)

 

결과 코드

#include <iostream>
using namespace std;

int N, M;

/* 1. 최대 공약수 : 유클리드 호제법
    a % b = c
    b % c = d
    d % c = e
    .
    .
    .
    q % r = 0
    gcd = r !
*/
int gcd(int a, int b)
{
    int c = a % b;
    while(c != 0)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

// 2. 최소 공배수 : a * b / (a와 b의 최대공약수)
int lcm(int a, int b)
{
    return (a * b)/ gcd(a, b);
}

int main()
{
    // 수행 시간 감소를 위한 라인
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    cin >> N >> M;

    cout << gcd(N, M) << '\n' << lcm(N, M) << endl;

}