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

What is GCD?

GCDis Greatest Common Divisor 

한국어로 최대공약수입니다.

 

최대공약수라고 하면 초등학교 과정에서 배우는 기초수학, 아주 간단한 개념입니다.

 

어느 두 변수인, a와 b의 약수 중에 

서로 중복면서 가장 큰 약수를 최대공약수라고 합니다.

 

예시)

a = 100,

b = 20

a의 약수 = 1, 2, 4, 5, 10, 20, 25, 50, 100

b의 약수 = 1, 2, 4, 5, 10, 20

서로 중복이 됨과 동시에 가장 큰 수인 20이 최대공약수입니다.

---

How to get GCD by using C/C++

보통 우리가 최대공약수를 구할 때 

이런식으로 표를 만들어 구합니다.

 

하지만 이것을 프로그래밍 언어로 구현하기란 쉽지않습니다.

 

일단 해결하고자 하는 문제를 컴퓨터로 원활하게 해결하기 위해서는 순서도가 필요합니다.

유클리드 알고리즘을 이용한 GCD 구하는 순서도입니다.

 

두 변수 a, b가 있을 때

1. if a > b, a - b

2. if a < b, a랑 b의 수를 바꿔줍니다.

3. if a == 0, b == GDC

 

아래 코드를 보시기전에 혼자서 해보시길 바랍니다.

#include <iostream>

int gettingGCD(int a, int b){ // 최대공약수를 구하는 함수
    int t;		    // a, b의 값을 서로 바꿀 때 사용할 변수
    while (a) {		   // a가 0이 될 때까지 반복
        if(a < b){         // a가 b보다 작다면 서로의 값을 변경해주는 if문
            t = a;
            a = b;
            b = t;
        }
        a -= b;            // 위에 if문과 관계없이 a가 0이 될 때까지 끊임없이 a = a - b를 해줍니다
    }
    return b;              // while문이 끝나면 최대공약수인 b를 리턴합니다
}

int main(){
    int a = 100;           // gettingGCD에 쓰일 a, b를 선언해줍니다.
    int b = 20;
    
    printf("%d\n", gettingGCD(a, b));
    return 0;
}

이렇게 하시고 실행을 하시면 

100과 20의 최대공약수인 20이 나오는걸 보실 수 있습니다.

---

The better way to get GCD

모든 알고리즘에는 무엇이 최선이다 무엇이 최적이다 라는 것은 명확하게 정의할 수 없지만

위에 방법은 상당히 비효율적입니다.

그 이유는 구하고자하는 두 변수의 수가 커지면 커질 수록

뺄셈을 더욱 많이 반복해야 합니다.

 

반복적인 뺄셈을 피할 수 있는 간단한 방법이 있습니다.

반복적인 덧셈을 더욱 효율적으로 하기 위해 탄생한 것이 곱셈

반복적인 뺄셈은 나눗셈으로 효율을 높일 수 있습니다.

 

이 방법에 대한 순서도는 아래와 같습니다.

두 변수 a, b가 있을 때

b가 0이 아니면

    1. a = a % b  

    2. a와 b의 수를 변경

    3. 1로 돌아감

b가 0이면 

    a가 최대공약수입니다.

참고로 %는 나눗셈의 나머지를 구하는 연산자입니다.

#include <iostream>

int gettingGCD(int a, int b){
    int t;
    while (b) {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main(){
    int a = 100;
    int b = 20;
    
    printf("%d\n", gettingGCD(a, b));
    return 0;
}

위에 했던 코드와 같은 값을 도출하지만

효율은 훨씬 높은 것을 볼 수 있습니다.

 

더 간단하게 재귀호출을 이용한 방법도 있지만 그건 나중에 따로 포스팅하도록 하겠습니다.

 

한 문제에 여러가지 문제풀이가 있습니다.

문제풀이를 알고리즘이라고 합니다.

여러분들도 문제를 풀었다는 것에 만족하지 마시고 어떻게하면 더욱 효율적으로 더욱 빠르게 

답을 구할 수 있을까를 고민해주시면 알고리즘 실력이 늘지않을 수가 없을겁니다.