유클리드 호제법(Euclidean Algorithm)

유클리드 호제법

유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 고통된 소수둘의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다.

 

핵심이론

유클리드 호제법을 수행하려면 MOD연산을 이해하고 있어야 한다. 

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

 

MOD 연산으로 구현하는 유클리드 호제법

1) 큰수를 작은수로 나누는 MOD 연산을 수행한다.

2) 앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD연산을 수행한다.

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

 

 

손으로 풀어보기

 

코드로 구현하기

 

	 public int Euclidean(int N, int M){
        //초기화
        int [] list = new int[2];
        //N,M 비교하여 값 넣어주기 오름차순
        if(N<M){list[0]=N;list[1]=M;}
        else{list[0]=M;list[1]=N;}
        
        int r = list[1]%list[0];
        list[1]=list[0];
        list[0]=r;
        if(list[0]!=0){
           return Euclidean(list[0],list[1]);}
        return list[1];
    }

더 좋은 코드

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

활용 문제

[백준] 1934번 최소 공배수 구하기