[C++] GCD 최대공약수, LCM 최소공배수 / 재귀함수를 이용한 알고리즘

GCD Greatest Common Divisor 혹은 Greatest Common Factor 이라고 표현하는 최대공약수

LCM Lowest Common Multiple 이라고 불리는 최소공배수

현실에서는 초등학교 수학 수준으로 굉장히 쉬운 개념입니다.

 

예를 들어 24, 18이라는 두 수의 최대공약수와 최소공배수를 구하라 라는 문제의 답은

두 수를 소인수분해 한 후

24 = 2 * 2 * 2 * 3

18 = 2 * 3 * 3 

최대공약수 : 2 * 3 = 6

최소공배수 : 2 * 2 * 2 * 3 * 3 = 72

이처럼 엄청 간단한 문제이다.

 

하지만 이를 프로그래밍 언어로 컴퓨터에게 이해시키려고 하면 어디부터 시작해야할지 막히기 마련이다.

 

쉬운 방법은 이 전에 포스팅 해놓았으니 아래 링크를 보길바란다.

https://eng-dev.tistory.com/4

[C++] GCD 최대공약수 구하기 / 유클리드 알고리즘 구현하기

---

재귀함수 최대공약수

이번엔 저번에 약속했듯이 

재귀함수를 이용한 유클리드 알고리즘을 알아볼것이다.

 

코드를 먼저 보자

int GCD(int a, int b) {
    if(a == 0) return b;
    return GCD(b % a, a);
}

재귀함수를 이용하면 코드가 굉장히 짧아진다.

 

32, 12라는 두 수가 있다면

a = 32는 0이 아니므로 return GCD(b % a, a)를 실행한다.

GCD(12 % 32, 32); 12 % 32 == 20

GCD(32 % 20, 20) 32 % 20 = 12

GCD(20 % 12, 12) 20 % 12 = 8

GCD(12 % 8, 8) 12 % 8 = 4

GCD(8 % 4, 4) 8 % 4 = 0

 

여기서 a == 0이 됐으므로 b를 리턴한다. b = 4;

 

32, 12의 최대공약수는 4이다.

 

재귀함수를 처음보면 굉장히 당황스럽고 이게 뭔가 싶을 수도있다.

하지만 마음을 가다듬고 하나하나 따라가다보면 답이 나온다.

 

재귀함수의 내부에는 반드시 조건문이 있어야한다.

함수안에서 계속해서 함수를 호출하기 때문에 어디서 그만 호출해야하는지 컴퓨터에게 알려줘야하기 때문이다.

---

재귀함수 최소공배수

최소공배수를 구하는것은 공식만 알고있으면 더욱 쉽다.

공식은 

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

 

이 공식을 이용해서 최소공배수를 구할 수 있다.

int GCD(int a, int b) {
    if(a == 0) return b;
    return GCD(b % a, a);
}

int LCM(int a, int b) {
    return (a * b) / GCD(a, b);
}

32, 12라는 두 수로 예를 들자면 

32 * 12 = 384

GCD(32, 12) = 4

LCM(32, 12) = 384 / 4 = 96

---

오늘 소개해준 함수와 공식은

https://www.geeksforgeeks.org/program-to-find-lcm-of-two-numbers/

Program to find LCM of two numbers - GeeksforGeeks

위에 사이트를 참고했다.