JAVA

[Java] GCD 알고리즘(최대공약수) & LCM 알고리즘(최소공배수)

번잔중 2022. 10. 3. 01:56

GCD(Greatest Common Divisor) 알고리즘

GCD란 영어 단어 그대로 최대공약수라는 뜻이다. 최대공약수는 공약수 중에서 가장 큰 값을 의미한다.

 

우선 최대공약수를 구하기 위해서는 공약수가 무엇인지부터 알아내는 것이 먼저이다.

최대공약수를 구하기 전에 공약수를 알아보자!

공약수

사전에서는 둘 이상의 정수에 공통된 약수라고 정의되어 있다. 정수 두 개를 놓고 보았을 때, 둘 다 나누어 떨어지게 만들 수 있는 수를 공약수라고 한다. 

 

예를 들어 16과 24가 있다고 했을 때, 

  • 16의 약수: 1, 2, 4, 8, 16
  • 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24

16과 24의 공약수는 1, 2, 4, 8이다.

 

그렇다면 최대공약수는 8이 되는 것이다.

유클리드 호제법(Euclidean algorithm)

최대공약수를 구하는 알고리즘 중 하나이다. 호제법이란 말은 두 수가 서로(호) 상대방 수를 나누어서(제) 결국 원하는 수를 얻는 알고리즘을 뜻하는 것이다. 현존하는 알고리즘 중에서 가장 오래된 알고리즘으로 알려져 있다.(TMI 🤗)

 

2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지를 r이라고 했을 때, a와 b의 최대 공약수는 b와 r의 최대공약수와 같다. 이 방법을 나머지가 0이 될 때까지 반복하면 a와 b의 최대공약수가 된다.

 

이것을 식으로 나타내면 (a, b) = (b, a % b)이라고 할 수 있다.

 

이것도 예를 들어서 보겠다.

16과 24를 다시 예로 들어보면

 

(24, 16) = (16, 8) = (8, 0)이므로 최대공약수는 8이 된다. 

 

일반적으로 16과 24의 최대공약수는 소인수분해를 통해 구할 수 있지만 그 수가 소인수분해로 구할 수 없을만큼 크다면 유클리드 호제법을 사용하여 구하는 것이 효율적이다.

GCD Algorithm(Euclidean algorithm)의 자바 코드

이 글을 읽는 분들은 아마 이게 제일 궁금해서 들어왔을텐데, 지금 보여주게 되어서 필자도 마음이 헤비(heavy)하다. 하지만 굳이 내 블로그가 아니라도 볼 수 있는 곳이 많기 때문에 내 맘대로 할것이다. (내 블로그니까)

 

// 재귀 함수
public static int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 반복문
public static int gcd(int a, int b) {
    int c;
    while(b != 0) {
    	c = a % b;
        a = b;
        b = c;
    }
    return a;
}

간단한 코드이지만 설명을 곁들여보자면 재귀 함수로 돌아가는 코드이다. 

b와 a를 b로 나눈 나머지의 값을 b의 인자로 계속 보내주면서 b 인자 자리에 위치한 값이 0이 될 때까지 재귀적으로 호출하는 것이다.

LCM(Least common multiple) 알고리즘

최소공배수라는 뜻으로 최소공배수는 공배수 중에서 가장 작은 값을 의미한다.

 

최소공배수를 구해보기 전에 공배수를 간단하게 알아보겠다.

공배수

공배수는 두 개 이상의 자연수의 공통인 배수라는 뜻이다. 쉽게 말해 여러 개의 수가 있을 때, 공통적으로 배수가 되는 수를 말하는 것이다. 두 개 이상의 모든 공배수는 최소공배수의 배수이다.

 

예를 들어 3과 4가 있을 때, 3의 배수이면서 4의 배수인 수를 공배수라고 할 수 있는데,

  • 3의 배수: 3, 6, 9, 12, 15, 18, 21, 24, ...
  • 4의 배수: 4, 8, 12, 16, 20, 24, ...

3과 4의 공배수는 12와 24가 된다.

그렇다면 최소공배수는? 12이다.

GCD와 LCM 사이의 관계

GCD를 구현할 수 있으면 LCM은 쉽게 구할 수 있다. 

간단하게 정리를 해보겠다.

 

두 자연수 A와 B의 최대공약수를 G, 최소공배수를 L이라고 했을 때, A = G x a, B = G x b(a, b는 서로소)로 나타낼 수 있다.

  1. L = G x a x b
  2. A x B = (a x G) x (b x G) = (a x b x G) x G = L x G

로 나타낼 수 있다. 공식만 봐서는 이해가 잘 가지 않으니 예를 들어서 24와 16으로 구해보겠다!

 

먼저 소인수분해로 최대공약수를 먼저 구해보겠다.

24와 16의 최대공약수와 최소공배수

 

최대공약수 G는 8이 되고, 이를 바탕으로 최소공배수 L은 48이 된다.

이제 공식에 대입해서 구해보자!

  • G = 8
  • A = 8 x 3 = 24
  • B = 8 x 2 = 16
  • L = 8 x 3 x 2 = 48

이 된다는 것을 알 수 있다. 이제 위 공식의 2번을 살짝 변형해보자. 

  • A x B = (a x G) x (b x G) = (a x b x G) x G = L x G
  • A x B = L x G로 간단하게 나타낼 수 있고, L = A x B / G라고 표현할 수도 있다.
  • 그렇다면 위의 예시에 값을 대입해보았을 때, 24 x 16 / 8 = 48로 공식과 일치함을 확인할 수 있다!

따라서 우리가 최대공약수(GCD)와 최소공배수(LCM) 사이의 관계를 아래와 같이 표현할 수 있다.

LCM(a, b) = a x b / GCD(a, b)

 

이제 알고리즘을 확인해보자.

LCM Algorithm의 자바 코드

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

GCD만 포스팅하려다가 LCM까지 포스팅하게 되었습니다. 굉장히 힘든 밤이네요 ㅎㅎ

읽어주셔서 감사합니다.