유클리드 호제법 Euclidean algorithm (JAVA)

📍 유클리드 호제법이란?

: 두 수의 최대공약수를 구하는 알고리즘이다.

두 양의 정수 a,b(a>b)에 대하여 a=bq+r(0≤r<b)이라 하면,
a,b의 최대공약수는 b,r의 최대공약수와 같다.
즉, gcd(a, b)=gcd(b,r)
r=0이라면, a,b의 최대공약수는 b가 된다

정리하면, r = a % b 이다.

1. 예시

예시로 12와 9의 최대공약수를 구하는 과정을 알아보자

(1) 12 = 9 × 1 + 3
여기서 12를 9로 나눈 몫
q는 1이고, 나머지 r는 3이다.

a,b의 최대공약수는 b,r의 최대공약수와 같기 때문에
이제 9와 3의 최대공약수를 구한다.

(2) 9 = 3 × 3 + 0
여기서 나머지 r는 0이기 때문에, 최대공약수는 b인 3이다.
따라서, 12와 9의 최대공약수는 3이 된다.

2. 구현 JAVA

public class GCD {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a; // b가 0이면 a가 최대공약수
        }
        return gcd(b, a % b); // 유클리드 호제법
        // r = a % b 이기 때문에 b와 r 의 최대 공약수를 구하는 걸 의미한다.
    }

    public static void main(String[] args) {
        int a = 12;
        int b = 9;

        int result = gcd(a, b);
        System.out.println("최대공약수: " + result);
    }
}

3. 백준 문제 JAVA

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

백준 2485번 가로수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[] interval = new int[N-1];
        for (int i=0; i<N-1; i++) {
            interval[i] = arr[i+1] - arr[i];
        }

        int gcdValue = interval[0];
        for (int i = 1; i < interval.length; i++) {
            gcdValue = gcd(gcdValue, interval[i]);
        }

        int count = 0;
        for (int gap : interval) {
            count += (gap / gcdValue) - 1;
        }

        System.out.println(count);
    }

    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}