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

1. 개념

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

+ 두 수의 곱을 최대 공약수로 나누면 최소공배수도 구할 수 있다.

 

2. 방법

• 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
• 위의 작은 수와 MOD 연산의 결과로 MOD 연산을 수행한다.
• 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

MOD연산은 큰 수를 작은 수로 나눈 나머지를 구하는 연산이다.

 

3. 코드

// 반복문으로 구현

public static int gcd(int num1, int num2){
    int small = num1 < num2 ? num1 : num2;
    int big = num1 > num2 ? num1 : num2;
    int temp = 0;
    while(small != 0){
        temp = big % small;
        big = small;
        small = temp;
    }
    return big;
}

// 재귀로 구현

public static int gcd(int num1, int num2){
    // num1 > num2 라고 가정
    if(num2 == 0){
        return num1;
    }else{
        return gcd(num2, num1%num2);
    }
}

 

3. 관련 문제

백준 1934

GitHub - Lee-Min-Jung/coding_test_practice

백준 1850

GitHub - Lee-Min-Jung/coding_test_practice

백준 1033

GitHub - Lee-Min-Jung/coding_test_practice