유클리드 호제법

오늘은 백준 알고리즘 1735번을 풀면서 접하게 된 유클리드 호제법에 대하여 정리해보겠습니다.

 

유클리드 호제법(Euclidean Algorithm)은 두 개의 자연수의 최대공약수를 구하는 알고리즘이다.

 

유클리드 호제법의 핵심은 두개의 자연수 a, b에 대하여 a를 b로 나눈 나머지를 r이라고 한다면, a와 b의 최대공약수와 b와 r의 최대공약수는 같다는 것이다. 이 핵심에 따라 b를 r로 나눈 나머지를 r`라고 한다면 다시 r를 r`로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나눈 수가 최대공약수가 되는 것이다.

 

유클리드 호제법을 사용하여 최대공약수를 구하는 과정을 설명하면 좋겠으나 귀찮기도 하고 핵심만 안다면 코드로 구현하는 것은 어렵지 않다고 생각한다. 반복문으로 a, b 자리에 r과 r`로 계속 교체하며 나머지가 0이 될 때까지 반복하면 된다.

 

아래의 코드는 내가 처음 사용한 최소공배수, 최대공약수 구하는 알고리즘

백준 알고리즘을 풀고 챗GPT로 코드 리팩토링을 부탁하는데, 공부에 도움이 되는 거 같다.

	public static int getLCM(int A, int B) {
		int multiple = A;
		while(true) {
			if(A % B == 0) {
				return A;
			}else {
				A += multiple;
			}
		}
	}
	
	public static int getGCD(int A, int B) {
		int min = Math.min(A, B);
		int max = Math.max(A, B);
		int multiple = min;
		while(true) {
			if(max % multiple == 0 && min % multiple == 0) {
				return multiple;
			}else {
				multiple--;
			}
		}
	}

 

그리고 아래의 코드는 유클리드 호제법을 사용한 코드

유클리드 호제법을 사용하여 최소공배수는 a, b를 곱한 수에 최대공약수로 나눈 값이다.

    // 최소공배수 계산 메서드
    public static int getLCM(int a, int b) {
        return a * b / getGCD(a, b);
    }

    // 최대공약수 계산 메서드 (유클리드 호제법)
    // 1. a % b = r
    // 2. b % r = r'
    // 3. r % r' = r''
    // 나머지가 0일때, b가 최대공약수(아래에서는 temp를 a에 저장하여 a를 리턴함)
    public static int getGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

 

시간이 거의 9배 차이...

 

1735번: 분수 합 (acmicpc.net)'

1735번: 분수 합

아래는 위의 문제의 코드 전문

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

public class Number_1735 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] AB = br.readLine().split(" ");
		String[] CD = br.readLine().split(" ");
		
		int A = Integer.parseInt(AB[0]); // 분수 1 - 분자
		int B = Integer.parseInt(AB[1]); // 분수 1 - 분모
		int C = Integer.parseInt(CD[0]); // 분수 2 - 분자
		int D = Integer.parseInt(CD[1]); // 분수 2 - 분모
		
		int LCM = getLCM(B, D);
		int numerator = (A * (LCM / B)) + (C * (LCM / D));
		
		int GCD = getGCD(LCM, numerator);
		bw.write(String.valueOf(numerator / GCD) + " " + String.valueOf(LCM / GCD));
		
		br.close();
		bw.flush();
		bw.close();
	}
	
//	public static int getLCM(int A, int B) {
//		int multiple = A;
//		while(true) {
//			if(A % B == 0) {
//				return A;
//			}else {
//				A += multiple;
//			}
//		}
//	}
//	
//	public static int getGCD(int A, int B) {
//		int min = Math.min(A, B);
//		int max = Math.max(A, B);
//		int multiple = min;
//		while(true) {
//			if(max % multiple == 0 && min % multiple == 0) {
//				return multiple;
//			}else {
//				multiple--;
//			}
//		}
//	}
	
    // 최소공배수 계산 메서드
    public static int getLCM(int a, int b) {
        return a * b / getGCD(a, b);
    }

    // 최대공약수 계산 메서드 (유클리드 호제법)
    // 1. a % b = r
    // 2. b % r = r'
    // 3. r % r' = r''
    // 나머지가 0일때, b가 최대공약수(아래에서는 temp를 a에 저장하여 a를 리턴함)
    public static int getGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}