[Algorithm] 유클리드 호제법이 뭔데. . (ft. BOJ2485_가로수)

민지·2023년 12월 15일

Algorithm

목록 보기

4/8

들어가며

반복문을 두번 돎리며 백준 문제를 하나 풀었는데,
알고리즘 분류를 보니 수학, 그리고 유클리드 호제법이 적혀있었다.
분명 언젠가 한 번 들었을텐데 뭔지 모르겠어서 찾고 정리해본다.

유클리드 호제법

2개의 자연수 또는 다항식의 최대공약수를 구하는 알고리즘.
두 정수의 최대공약수를 쉽게 알아내는 방법.

알고리즘

A와 B의 최대공약수 GCD(A,B)를 알아내보자.

A=0, GCD=(0,B)=B 이므로 GCD(A,B)=B. 탈출.
B=0, GCD=(A,0)=A 이므로 GCD(A,B)=A. 탈출.
A를 A = B * Q + R 이라고 표현. (A>=B)
GCD(A,B) = GCD(B,R) 이므로 다시 GCD(B,R)을 찾는다.
GCD(A,B) = GCD(B,R) = GCD(R,R') = ... = GCD(R'',0) = R''

실제 수를 가지고 한 예제

여기참고

이해

큰 문제를 작게 쪼개나가면서 하나의 수가 0이 되면 다른 하나의 수가 최대공약수가 되는 특징을 이용해 최대공약수를 찾아내는 알고리즘이다.

더 작고 쉬운 문제로 줄여나간다? = 재귀로 풀 수 있다.

예시 코드

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

// a가 더 크다고 가정한다. 
int result = gcd(a,b);

BOJ2485 가로수

문제링크

나는 처음에 중첩반복문을 통해 풀었다고 했다.

기존풀이

package solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class BOJ2485_가로수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Integer> trees = new ArrayList<>();
        int minGap = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());
            trees.add(input);
            if(i != 0) minGap = Math.min(minGap, input - trees.get(i-1));
        }
        int cnt = 0;
        boolean isSuccess = false;
        for (int i = minGap; i > 0; i--) {
            cnt = 0;
            int j=0, tmp = trees.get(0);
            while(true) {
                tmp += i;
                int next = trees.get(j+1);
                if(next < tmp) break;   // 다음값이 더 작다면 해당 간격이 맞지 않으니 탈출.
                if(next > tmp) cnt++;
                if(next == tmp) j++;
                if(tmp == trees.get(N-1)) {
                    isSuccess = true;
                    break;
                }
            }
            if(isSuccess) break;
        }
        System.out.println(cnt);
    }
}

풀이 방법

입력값을 받으면서 가장 차이가 작은 값을 갱신했다.
문제에서 가로수를 심는 최솟값을 찾으라고 했으므로 간격을 넓혀 심는게 최솟값.
즉 얘부터 1씩 줄여나가면서 다 통과되면 탈출해서 결과값을 출력할 생각이었다.
그리고 tmp 라는 변수로 현재값을 두어, 간격을 더해가는 변수랑,
next 라는 변수로 이미 가로수가 있는 리스트를 순회하는 값을 비교해가며 문제를 풀었다.

결과

통과는 했는데 시간이 빠르게 푼사람들에 비해 2.5배 정도 걸림.

재귀를 통해 유클리드 호제법 적용 풀이

적용할 수 있는 문제인가?

여기에서 최대공약수가 무슨 의미가 있는지 고민했다.
아.!

입력값으로 온 모든 아이들의 간격들의 최대공약수가 결국 간격의 최솟값

오 ... 그러네 ..
그럼 이걸 구하고 해당 값이 존재하지 않으면 카운팅 해서 결과 리턴.
내 풀이처럼 하나씩 줄여나가는 필요가 줄어지겠구나.

풀이 코드

package solution;

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


public class BOJ2485_가로수 {
    public static int gcd(int a, int b) {
        if(b==0) return a;
        return gcd(b, a%b);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] trees = new int[N];
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(br.readLine());
        }
        int gcd = 0;
        for (int i = 0; i < N-1; i++) {
            int gap = trees[i+1] - trees[i];
            gcd = gcd(gap, gcd);
        }
        int cnt = (trees[N-1]-trees[0]) / gcd + 1 - trees.length;
        System.out.println(cnt);
    }
}