개발기록

1. 최대공약수란?

최대공약수는 두 수를 동시에 나눌 수 있는 수 중 가장 큰 수이다. 영어로는 GCD라고 한다.

GCD = Greatest Common Divisor

// 예를 들어 12와 18이 있다.
12의 약수: 1, 2, 3, 4, 6, 12
18의 약수: 1, 2, 3, 6, 9, 18

//공통 약수는 1, 2, 3, 6이고, 이 중 가장 큰 수는 6이다.
gcd(12, 18) = 6

2. 최소공배수란?

최소공배수는 두 수의 공통 배수 중 가장 작은 수이다. 영어로는 LCM이라고 한다.

LCM = Least Common Multiple

// 예를 들어 12와 18의 배수는 다음과 같다.
12의 배수: 12, 24, 36, 48, ...
18의 배수: 18, 36, 54, ...

공통 배수 중 가장 작은 수는 36이다.
lcm(12, 18) = 36

3. 유클리드 호제법이란?

유클리드 호제법은 최대공약수를 빠르게 구하는 방법이다. 핵심 공식은 다음과 같다.

gcd(a, b) = gcd(b, a % b)

즉, 두 수 a, b가 있을 때 a를 b로 나눈 나머지를 계속 이용한다.

// 예를 들어 gcd(18, 12)를 구하면 다음과 같다.
18 % 12 = 6
12 % 6 = 0

gcd (18, 12) 
= gcd(12, 6) 
= gcd(6, 0) 
// 나머지가 0이 되었을 때 남는 수 6이 최대공약수이다.

4. 직접 구현한 gcd 함수 (유클리드 호제법)

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }

    return a;
}

이 코드는 b가 0이 될 때까지 나머지를 계속 구한다.

흐름은 다음과 같다.

a = 18, b = 12
r = 18 % 12 = 6

a = 12, b = 6
r = 12 % 6 = 0

a = 6, b = 0 // 반복문이 끝났을 때 a에 남은 값이 최대공약수이다.

5. 최소공배수 구하는 방법

최소공배수는 최대공약수를 이용해서 구할 수 있다.

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

하지만 숫자가 큰 경우 a * b를 먼저 계산하면 오버플로우가 날 수 있다.

그래서 보통은 다음처럼 작성한다.

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

먼저 a를 최대공약수로 나눈 뒤 b를 곱하는 방식이다.

6. 직접 구현 전체 코드

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    long long a, b;
    cin >> a >> b;

    cout << "최대공약수: " << gcd(a, b) << '\\n';
    cout << "최소공배수: " << lcm(a, b) << '\\n';

    return 0;
}

7. C++ 내장 함수 사용하기

C++17부터는 최대공약수와 최소공배수를 구하는 함수가 제공된다.

#include <numeric>

// 사용 함수는 다음과 같다.
gcd(a, b); // 최대공약수
lcm(a, b); // 최소공배수

// 예시코드

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int a = 12;
    int b = 16;

    cout << "최대공약수: " << gcd(a, b) << '\\n'; //최대공약수: 6
    cout << "최소공배수: " << lcm(a, b) << '\\n'; //최소공배수: 36

    return 0;
}

8. 최종 요약

유클리드 호제법은 최대공약수를 빠르게 구하는 방법이다.

두 수 a, b가 있을 때 a % b의 나머지를 이용해 gcd(a, b) = gcd(b, a % b) 형태로 계속 바꿔가며 계산한다. 나머지가 0이 되는 순간 남아 있는 수가 최대공약수이다.

C++에서는 직접 구현할 수도 있고, C++17 이상에서는 <numeric> 헤더의 gcd, lcm 함수를 사용할 수도 있다.

헤더파일: #include <numeric>
최대공약수: gcd(a, b)
최소공배수: lcm(a, b)
사용 기준: C++17 이상