[알고리즘] 유클리드 호제법 Euclidean Algorithm

유클리드 호제법/유클리드 알고리즘(Euclidean Algorithm)

• 2개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘
• 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같음
  • 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수
• 시간복잡도 O(logN)
  • 기존의 하나씩 나누어서 구하는 방식으로 최대공약수를 구하게 될 경우 시간복잡도 O(N)

 

예시) 78696과 19332의 최대공약수

78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 ＋ 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2 ＋ 0

 

 호제법

• 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘

 

최소공배수(LCM, Least Common Multiple)

최소공배수 = 두 자연수의 곱 /  최대공약수

 

---

1934번: 최소공배수

나의 풀이

package level16_greedyAlgorithm;

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

//백준 1934번 문제] 최소공배수
public class Backjoon1934 {
    static int gcd = 0;

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

        int t = Integer.parseInt(br.readLine()); //테스트케이스의 수
        int aNb[][] = new int[t][2];

        for(int i=0; i<t; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<2; j++) {
                aNb[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //입력 끝

        //최소공배수 구하기 : 최소공배수 = 두 수의 곱 / 최대공약수
        for(int i=0; i<t; i++) {
            int a = aNb[i][0];
            int b = aNb[i][1];
            gcd(a, b);
            int lcm = a * b / gcd;
            System.out.println(lcm);
        }
    }

    //두 수의 최대공약수 구하기
    //유클리드 호제법 사용
    public static void gcd(int a, int b) {
        if(b == 0) {
            gcd = a;
            return;
        }
        gcd(b, a % b);
    }
}

 

출처) 위키백과 - 유클리드 호제법