[알고리즘] 3. 최대공약수 알고리즘

최대 공약수

• 4와 24의 최대 공약수를 구하시오.

문제 분석

• 4의 약수, 24의 약수를 저장해야 함 - 배열 사용
• 약수를 구하는 방법은 이전 예제에서 참고

• 각 배열 중 공통된 수만 뽑아서 저장 - 공약수

• 공통된 수 중 제일 큰 수를 찾기 위해 수를 비교

1. Sampling & Hard Coding

package algo;

public class Gcd {
    public static void main(String[] args) {
        // 4와 24의 최대 공약수를 구하시오.

        // 1. Sampling : 2와 10의 최대 공약수를 구하시오.

        // 1-1. 2의 약수를 구하시오. (배열 저장)
        int a = 0;
        int N1 = 2;
        int[] d1 = new int[N1];
        for (int i = 0; i < N1; i++) {
            a++;
            if (N1 % a == 0) {
                d1[i] = a;
                System.out.println(N1 + "의 약수 : " + d1[i]);
            } else {
                d1[i] = 0;
            }
        }
        // 1-2. 10의 약수를 구하시오. (배열 저장)
        a = 0;
        int N2 = 10;
        int[] d2 = new int[N2];
        for (int j = 0; j < N2; j++) {
            a++;
            if (N2 % a == 0) {
                d2[j] = a;
                System.out.println(N2 + "의 약수 : " + d2[j]);
            } else {
                d2[j] = 0;
            }
        }

        // 1-3. 2와 10의 공약수를 구하시오. (배열 내 공통된 수만 저장)
        // 1-3-1. 두 배열 중 더욱 작은 배열을 찾는다.
        // N1 < N2

        // 1-3-2. 작은 배열의 길이를 저장하고, 반복문을 통해 약수를 비교한다.
        // 1-3-3. 수가 같으면 배열에 저장한다.
        int[] d3 = new int[N2];
        for (int k = 0; k < N1; k++) {
            for (int l = 0; l < N2; l++) {
                int num = d1[k] == d2[l] ? d1[k] : 0;
                if (num != 0) {
                    d3[k] = num;
                    System.out.println("2와 10의 공약수 : " + d3[k]);
                } else d3[k] = 0;
            }
        }
        // 1-4. 2와 10의 최대 공약수를 구하시오. (내부에서 제일 큰 수 비교)
        int result = d3[0];
        for (int m = 0; m < N2; m++) {
            if (d3[m] >= result) {
                result = d3[m];
            }
        }
        System.out.println("2와 10의 최대 공약수 : " + result);
    }
}

결과

유클리드 호제법 : 최대공약수를 구할 수 있는 공식

• 2개의 자연수 a, b에 대하여 a를 b로 나눈 나머지가 r일 때(a>b일 때), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

문제 재분석

• 두 수만 있으면 나머지 연산을 통해 반복문을 사용해서 구할 수 있음

• 나눌 수 없거나 나머지가 0일 경우 : 더 작은 수가 최대 공약수 (공약수는 더 작은 수의 약수)

1. 코드 작성 : Hard Coding

 package algo;

public class Uc {
    public static void main(String[] args) {
        // 4와 24의 최대공약수를 구하라. (유클리드 호제법 사용)
        // 유클리드 호제법 : a와 b (a > b)를 나눈 나머지가 r일 때, 최대공약수는 b와 r의 최대공약수와 같다.
        // r이 0이거나 더이상 나눌 수 없을 때 (div 0), 더 작은 수 (0 제외)가 최대 공약수이다.

        // 1. 4와 24의 크기 비교
        int a = 4, b = 24;
        int l = 0; // 큰 수(large)
        int s = 0; // 작은 수(small)
        l = a > b ? a : b;
        s = a < b ? a : b;

        System.out.println("a, b 중 더 큰 수는 " + l + ", 더 작은 수는 " + s + "입니다.");

        // 2. a를 b로 나눈 나머지 r을 구하기
        int r = l % s;
        int r2;
        // 2-1. 나머지가 0일 경우, 최대 공약수는 s
        if (r == 0) System.out.println("최대 공약수는 " + s);
            // 2-2. 아닐 경우, b와 r을 나머지 연산을 통해 또 다른 나머지 구하기
            // 언제까지? 나머지가 0이 될 때 까지 : 조건반복문 while
            // 변수 무한정 확장 불가 : 계산되는대로 대입하기, 나머지 변수 초기화 필요
        else {
            while (true) {
                r2 = s % r;
                if (r2 == 0) break;
                s = r;
                r = r2;
                r2 = 0;
            }
            System.out.println("최대 공약수는 : " + s);
        }
    }
}

2. Moduling

package algo;

public class Uc {
    public static void main(String[] args) {
        // 4와 24의 최대공약수를 구하라. (유클리드 호제법 사용)
        // 유클리드 호제법 : a와 b (a > b)를 나눈 나머지가 r일 때, 최대공약수는 b와 r의 최대공약수와 같다.
        // r이 0이거나 더이상 나눌 수 없을 때 (div 0), 더 작은 수 (0 제외)가 최대 공약수이다.

        // 1. 4와 24의 크기 비교
        int a = 4, b = 24;
        int l = 0; // 큰 수(large)
        int s = 0; // 작은 수(small)
        int r = 0;
        l = a > b ? a : b;
        s = a < b ? a : b;

        System.out.println("a, b 중 더 큰 수는 " + l + ", 더 작은 수는 " + s + "입니다.");

        // 2. a를 b로 나눈 나머지 r을 구하기
        // r이 0이면 최대 공약수 출력하고 break
        while (true) {
            r = l % s;
            if (r == 0) {
                System.out.println("최대 공약수는 " + s);
                break;
            }
            l = s;
            s = r;
        }
    }
}

결과

Functioning

package algo;

class GCD {
    int gcd(int a, int b) {
        int l = 0; // 큰 수(large)
        int s = 0; // 작은 수(small)
        int r = 0;
        l = a > b ? a : b;
        s = a < b ? a : b;

        System.out.println("a, b 중 더 큰 수는 " + l + ", 더 작은 수는 " + s + "입니다.");

        while (true) {
            r = l % s;
            if (r == 0) {
                break;
            }
            l = s;
            s = r;
        }
        return s;
    }
}

public class Uc {
    public static void main(String[] args) {
        // 4와 24의 최대공약수를 구하라. (유클리드 호제법 사용)
        // 유클리드 호제법 : a와 b (a > b)를 나눈 나머지가 r일 때, 최대공약수는 b와 r의 최대공약수와 같다.
        // r이 0이거나 더이상 나눌 수 없을 때 (div 0), 더 작은 수 (0 제외)가 최대 공약수이다.

        // 1. 10과 24의 크기 비교
        int x = 10, y = 24;
        // 2. 클래스 호출
        GCD f = new GCD();
        // 3. 결과값 출력 = gcd 호출
        System.out.println("최대 공약수는 " + f.gcd(x, y));

    }
}

결과

최종 코드

package algo;


public class Uc {
    static int gcd(int a, int b) {
        int l = a > b ? a : b;
        int s = a < b ? a : b;

        // System.out.println("a, b 중 더 큰 수는 " + l + ", 더 작은 수는 " + s + "입니다.");
        // div 0 : 나눌 수 없으므로 l이 최대 공약수
        if (s == 0) return l;
            // 그 외 : 유클리드 호제법
        else {
            // 1. 나머지가 0인 경우 : s를 반환
            int r = l % s;
            if (r == 0) return s;
            l = s;
            s = r;
            // 2. 그 외 : 반복
            return gcd(l, s);
        }
    }

    public static void main(String[] args) {
        // 4와 24의 최대공약수를 구하라. (유클리드 호제법 사용)
        // 유클리드 호제법 : a와 b (a > b)를 나눈 나머지가 r일 때, 최대공약수는 b와 r의 최대공약수와 같다.
        // r이 0이거나 더이상 나눌 수 없을 때 (div 0), 더 작은 수 (0 제외)가 최대 공약수이다.

        // 1. 두 수 대입
        int x = 13, y = 17;
        // 2. 클래스 호출
        // 3. 결과값 출력 = gcd 호출
        System.out.println("최대 공약수는 " + gcd(x, y));
    }
}

결과

1. 두 수가 5, 0일 경우 (div 0)

1. 두 수가 서로소일 경우 (13, 17)

1. 일반적인 경우 (4, 24)