알고리즘) 유클리드 호제법

유클리드 호제법

 

두 수의 최대 공약수를 구하는 알고리즘

 

---

먼저 MOD 연산에 대하여 이해하고 있어야 한다.

 

나머지 연산(modulo)

 

컴퓨터 프로그래밍 언어에서는

나머지 연산을 나타내는 기호로 사용한다.

 

ex)

mod 연산

14 mod 3 = 2	14 % 3 = 2
10 mod 5 = 0	10 % 5 = 0
2 mod 7 = 2	2 % 7 = 2

 

---

MOD 연산을 활용한 유클리드 호제법

 

1. 큰 수를 작은 수로 나누는 MOD연산 수행

 

2. 이전 단계의 작은 수와 MOD연산 결과 나온 나머지로

MOD연산 수행

 

3. 앞단계를 반복하며 나머지가 0이 될 때의 작은 수가 최대 공약수

 

---

최대공약수

(Greatest Common Divisor, GCD)

 

유클리드 호제법을 적용하여 최대공약수를 구해보자

 

 

유클리드 호제법 구현

큰 수	작은 수	나머지
320	172	148
172	148	24
148	24	4
24	4	0

 

나머지가 0일때의 작은수는 4이다.

 

따라서 320과 172의 최대 공약수는 4가 된다.

 

 

자바 재귀함수로 구현

class Main {
    public static void main(String[] args) {

        int a = 320;
        int b = 172;

        System.out.println(gcd(a, b));
    }
    static int gcd(int a, int b) {
        //b가 0이면 a가 최대공약수
        if (b == 0) return a;
       else return gcd(b, a%b);
    }
}

-------------------------------------------------------

4

Process finished with exit code 0

---

최소공배수

(Least Common Multiple, LCM)

 

A * B / gcd(최대공약수)

 

lcm(320, 172) = 320 * 172 / gcd(320, 172)

 

따라서 lcm(320, 172)는

 

13760

 

gcd활용하여 최고공배수 구하기

class Main {
    public static void main(String[] args) {

        int a = 320;
        int b = 172;

	//최소공배수 출력
        System.out.println(a * b / gcd(a, b));
    }
    static int gcd(int a, int b) {
        //b가 0이면 a가 최대공약수
        if (b == 0) return a;
       else return gcd(b, a%b);
    }
}
-----------------------------------------------------------------

13760

Process finished with exit code 0

 

---

유클리드 호제법을 이용하여

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

어렵지않게 구할 수 있게 되었다.