13. [수치] 최대공약수 구하기 (유클리드 알고리즘)

<문제>

두 수 a, b가 있을 때, 두 수의 최대공약수를 GCD(a,b)라 표기하고, 최대공약수 관련해서 아래와 같은 수식이 만족된다고 알려져 있다.

• GCD(a,0) = a
• GCD(a,b) = GCD(b,a)
• GCD(a,b) = GCD(a-b,b)
• GCD(a,b) = GCD(a%b, b)

위와 같은 성질을 이용해서 두 수의 최대공약수를 구하시오.

 

예)

GCD(30,280) =  30

 

<풀이>

최대공약수를 구하는데 가장 많이 알려진 방법이 유클리드 알고리즘이다.

이는 GCD(a,b) = GCD(a-b,b)   GCD(a,0) = a 를 이용한 알고리즘이다.

예를 들어 두 수 a=30, b=280의 경우를 유클리드 알고리즘을 이용해서 손으로 풀어보면 다음과 같다.

 

1. a=30  b=280 

2. 큰쪽값이 a가 되도록 한다. a=280  b=30

3. a를 30씩 빼 나간다. 30보다 작아질 때까지 ; GCD(a,b) = GCD(a-b,b)이므로, GCD(280,30)을 구하는 것은 GCD(250,30)구하는것과 같다.

     a :  280  -> 250 -> 220 -> 190 -> 160 -> 130 -> 100 -> 70 -> 40 -> 10

4. a=10 b=30 에서, 두 수를 바꾼다. ; GCD(a,b) = GCD(b,a)이므로, 두 수를 바꿔도 된다.

    a=30  b=10

5. a의 값을 10씩 뺀다. b의 값인 10보다 작아질 때까지

    a: 30 -> 20 -> 10 -> 0

6. a=0 b=10 이다. 즉, GCD(0,10) = 10  ==> 답은 10

위의 3번을 보면 a=280에서 30씩 빼서 a=10이 될 때가지 여러번 반복해서 빼야하는 번거로움이 있다. 이를 한번에 하도록 알고리즘을 개선할 수 있다. 즉, GCD(a,b) = GCD(a-b, b)를 이용하는 것이 아니라, GCD(a,b) = GCD(a%b, b)를 이용

이를 이용한 풀이는 다음과 같다.

 

1. a=30 b=280

2. a = a % b를 한다. 

3. a, b의 순서를 바꾼다. (왜냐면 a%b < b 이기 때문)

4. b가 0이면 답은 a로하고 종료. 아니면 2~3번 반복

 

실제 손으로 풀어보면,

1. a=30, b=280

2. a=30 % 280 = 30,  b=280

3. 순서 교환: a=280  b=30

4. b가 0이 아니므로 2~3번 반복

2. a=280%30=10, b=30

3. 순서 교환: a=30, b=10

4. b가 0이 아니므로 2~3번 반복

2. a=30%10=0, b=10

3. 순서 교환: a=10, b=0

4. b=0이므로, 답은 10

 

이제, 두 정수를 입력으로 받아서 최대공약수를 리턴하는 메서드를 짜보면 다음과 같겠다.

private int gcd(int a, int b){

    int t;

        while(b!=0){

        t=b;

            b = a % b;

            a = t;

        }

        return a;

    }

이 메서드에서 특이한 점은, a>b라야하는 조건이 없는 것이다. 즉, a와 b의 크기를 비교해서 큰 쪽이 a가 되게하는 루틴이 없는 것.

이는 b = a % b; 라는 코드에 의한 것이다. gcd(30,280)이 호출되었을 때를 손으로 풀어보자.

처음에 a=30 b=280이므로, 

t=b=280,  b=a%b=30%280=30, a=t=280  ==> a=280, b=30  :자연스럽게 a가 큰 수가 되도록 바꼈다.

<소스 코드>

package p1;

 

public class CalculateGCD {

         public CalculateGCD(){

                  test();

         }

        

         private void test(){

                  int a, b, g;

                 

                  a=30;

                  b=280;

                 

                  g=gcd(a,b);

                 

                  System.out.println("GCD("+a+","+b+")="+g);

         }

        

         private int gcd(int a, int b){

                  int t;

                  while(b!=0){

                           t=b;

                           b = a % b;

                           a = t;

                  }

                  return a;

         }

 

         public static void main(String[] args) {

                  new CalculateGCD();

 

         }

 

}

 

 

 

-끝-