[알고리즘] 최대공약수(GCD), 최소공배수 구하기 (유클리드 호제법)

유클리드 호제법

유클리드 호제법

두 개의 수가 주어졌을 때 최대 공약수를 구하는 알고리즘

이를 이용하여 최소 공배수도 구할 수 있음

 

 

약수?

어떠한 수를 나누어 떨어지게 하는 수

 

 

최대공약수(GCD)?

두 자연수의 공통된 약수 중 가장 큰 수

 

 

최소공배수?

두 자연수가 공통으로 표현할 수 있는 가장 작은 배수 

 

 

최대공약수를 구하는 방법

1. 소인수 분해를 통한 소인수를 곱하기 -> 값이 크면 오래 걸림

 

2. 유클리드 호제법

숫자 N, M이 존재(N > M)할 때,

L = N % M  

이 때, N와 M의 최대 공약수는 M와 L의 최대 공약수와 같음

-> 이를 반복하여 L == 0이 될 때의 M

 

 

최소공배수 구하는 방법

숫자 M * 숫자 N / 최대공약수

N * M / G

 

 

N개의 숫자에 대한 최대공약수, 최소공배수 구하는 방법

추천 문제 3번의 경우 여러 개의 숫자에 대해서 최대공약수와 최소공배수를 구하는 문제입니다.

(기존은 2개의 숫자에 대해서 최대공약수, 최소공배수를 구하는 문제)

 

만약 숫자 A, B, C가 있을 때 gcd(A, B)의 결과 G가 나왔다면, gcd(G, C)를 통해서 세 개 숫자의 최대공약수를 구할 수 있습니다.

 

최소공배수의 경우 이전_최소공배수 * 현재 숫자 / gcd(이전_최소공배수, 현재_숫자) 로 구할 수 있습니다.

(아래 코드 2 참고)

 

다시 말해, 숫자 2개를 구할 때는 최대공약수를 재사용했다면, 숫자 N개에서는 최대공약수와 최소공배수를 따로 따로 구한다는 의미입니다.

 

 

gcd() 함수 자체는 2개의 값을 찾기 위해서 작성한 기본 코드를 그대로 재사용하면 됩니다.

 

 

 

코드

- GCD 기본

// gcd()
public static int gcd(int A, int B) {
    if (B > A) {
        int temp = B;
        B = A;
        A = temp;
    }

    int C = A % B;
    if (C == 0) {
        return B;
    }
    return gcd(B, C);
}

// main()
int N = 24;
int M = 18;

int G = gcd(N, M); // 최대공약수
int L = N * M / G; // 최소공배수

 

- M개 숫자에 대한 최소공배수, 최대공약수 구하기

int A = number[0]; // 최대공약수
int L = number[0]; // 최소공배수
for (int i = 1; i < M; i++) {
    int B = number[i];


    A = gcd(A, B); // 최대공약수 구하기
    L = L * number[i] / gcd(L, number[i]); // 최소공배수 구하기
}

 

 

 

추천 문제

- 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

 

- 링

https://www.acmicpc.net/problem/3036

 

- 최대공약수, 최소공배수

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&code=1002&sca=99 

 

- 가로수

https://www.acmicpc.net/problem/2485