유클리드 호제법 -1 자바 백준 BOJ 1934 1850

유클리드 호제법

유클리드 호제법(Euclidean-algorithm) 은 두 수의 최대 공약수를 구하는 알고리즘입니다.

일반적으로 최대공약수를 구할 때는 소인수분해를 이용하지만 유클리드 호제법을 사용하면 더 간단하게 가능합니다.

 

유클리드 호제법 원리

먼저 최대 공약수를 구하는 데 사용하는 핵심 연산인 MOD 을 알아야 합니다.

연산	기능	예
MOD	두 값을 나눈 나머지를 구하는 연산	10 MOD 4 = 2 // 10 % 4 = 2

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

2. 앞 단계에서의 작은 수와 MOD 연산 결과 (나머지값)으로 MOD 연산 수행.

3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택.

 

270 과 192 의 최대공약수를 유클리드 호제법으로 구하는 그림을 통해 구체적으로 알아봅시다.

 

백준 1934 최소공배수

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

1. 문제 분석

최소 공배수를 구하는 방법은 최대 공약수를 구한 후 A * B / 최대공약수 입니다.

결국 유클리드 호제법을 이용해서 최대 공약수를 구하는 것이 핵심입니다.

2. 손으로 풀기

1.  위에서 유클리드 호제법의 원리를 설명한 것과 같은 방식으로 최대공약수를 구합니다.

2. A 와 B 를 곱한 후 최대공약수로 나눕니다.

3. 슈도코드

T: 테스트 케이스 개수
A: 큰 수
B: 작은 수 // 순서가 다르면 바꾸기
최대공약수 x
for(T){
	gcd(A, B)
    결과 res = A * B / x
    res 출력
}

// gcd 메소드
gcd(int A, int B){
    temp = A % B
    if(temp == 0){ // A 가 B 로 나누어 떨어지면
        x = B;
        return;
    }
    A = B;
    B = temp;
    gcd(A, B)
}

4. 코드

public class BaekJun1934 {

    static int A;
    static int B;
    static int x;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            swap();

            gcd(A, B);
            int res = A * B / x;
            bw.write(res + "\n");
        }
        bw.flush();
        br.close();
        bw.close();
    }

    static void gcd(int A, int B) {
        int temp = A % B;
        if (temp == 0) {
            x = B;
            return;
        }
        A = B;
        B = temp;
        gcd(A, B);
    }

    private static void swap() {
        if (A < B) {
            int temp = A;
            A = B;
            B = temp;
        }
    }
}

 

 

백준 1850 최대공약수

https://www.acmicpc.net/problem/1850

1850번: 최대공약수

 

1. 문제 분석

문제에서 A 와 B 가 최대 2⁶³ 입니다. 그렇다면 1이 2⁶³ 개가 있을 수 있다는 의미이므로 단순히 수 111111...1 과 111....1 을 MOD 연산하여 푼다면 시간 제한 2초를 훌쩍 넘길 것입니다. 즉, 입력과 출력에서의 규칙성을 찾아내야 합니다.

규칙성을 찾기 위해서는 직접 MOD 연산의 결과를 알아내야 합니다. 이를 위해서 시간 제한을 고려하지 않은 코드를 만들어서 입력에 따른 출력을 얻은 후에 그것을 가지고 정답 코드를 도출해내는 방식으로 구현해보겠습니다.

2. 손으로 풀기

1. 먼저 시간 제한을 고려하지 않은 코드를 만들고 입력에 따른 출력을 얻습니다.

A가 3일 때 -> 111 B 가 4 -> 1111.

그리고 B 와 A 에 대해  유클리드 호제법을 이용해서 출력을 얻는 코드를 만듭니다.

단순히 입력에 따른 출력을 얻기 위한 코드이므로 최적화 없이 로직에만 맞게 대충 만들면 됩니다.

public class BaekJun1850 {

    static int A;
    static int B;
    static int x;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken()); // 3 -> 111
        B = Integer.parseInt(st.nextToken()); // 4

        int one = 1;
        for (int i = 0; i < A-1; i++) {
            one = one * 10 + 1;
        }
        A = one;
        one = 1;
        for (int i = 0; i < B-1; i++) {
            one = one * 10 + 1;
        }
        B = one;

        System.out.println("A: " + A);
        System.out.println("B: " + B);

        swap();
        gcd(A, B);
        br.close();
        System.out.println(x);
    }

    static void gcd(int A, int B) {
        int temp = A % B;
        if (temp == 0) {
            x = B;
            return;
        }
        A = B;
        B = temp;
        gcd(A, B);
    }

    private static void swap() {
        if (A < B) {
            int temp = A;
            A = B;
            B = temp;
        }
    }
}

입력에 따른 출력을 얻었습니다.

입출력을 정리해보면 아래와 같습니다.

A	B	출력(최대공약수)
2 -> 11	3 -> 111	1
	4 -> 1111	11
	5 -> 11111	1
	6 -> 11111	11
3 -> 111	4 -> 1111	1
	5 -> 11111	1
	6 -> 111111	111
	9 -> 111111111	111

 

몇 가지 입력을 테스트 해보니 A 와 B 의 최대공약수의 자리만큼 출력이 되는 것처럼 보입니다. 이것이 맞는지를 확인해보기 위해서 다른 입력도 넣어봅시다.

A	B	출력(최대공약수)
4 -> 1,111	8 -> 11,111,111	1111
	9 -> 111,111,111	1
	7 -> 1,111,111	1
5 -> 11,111	8 -> 11,111,111	1
	9 -> 111,111,111	1
	10 -> 1,111,111,111	11,111

테스트 결과 A 와 B 의 최대 공약수를 구하고 digits 을 구하고 digits 자리수만큼의 111..1 이 정답이 되는 것이 맞는 것 같네요.

 

2. 이제 어렵지 않습니다. 유클리드 호제법으로 A 와 B 의 최대 공약수를 구합니다.

3. 최대공약수만큼 1을 반복해서 출력합니다.

 

3. 슈도코드

A, B : 자연수
digits: A, B 의 최대공약수
gcd(A, B) // A,B 에 대해 유클리드 호제법

digits 만큼 1을 반복해서 붙여서 출력.

// gcd 메소드
gcd(A, B){
    temp = A % B
    나머지가 0 이면{
        digits = B;
        return;
    }
    아니면 나눈 수를 큰 수로 바꾸고
    나머지를 작은 수(나누는 수)로 바꿔서
    gcd(큰수, 작은수)
}

4. 코드

public class BaekJun1850 {

    static long A;
    static long B;
    static long digits;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());
        swap();

        gcd(A, B);
        br.close();
        for (int i = 0; i < digits; i++) {
            sb.append(1);
        }
        System.out.println(sb);
    }

    static void gcd(long A, long B) {
        long temp = A % B;
        if (temp == 0) {
            digits = B;
            return;
        }
        A = B;
        B = temp;
        gcd(A, B);
    }

    private static void swap() {
        if (A < B) {
            long temp = A;
            A = B;
            B = temp;
        }
    }
}