🎆유클리드 호제법

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

호제법을 수행하려면 MOD 연산을 이해하고 있어야 한다. MOD 연산은 두 값을 나눈 나머지를 구하는 연산이다. MOD 연산을 이해하면 다음의 3가지 단계로 유클리드 호제법을 구현할 수 있다.

1. 큰 수를 작은수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MDO 연산 결과값(나머지)으로 MOD 연산을 수행한다.
3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

풀어서 설명하면, 자연수 2개 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이를 반복하는 과정에서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.

예시

두 자연수 24와 18의 최대공약수는?
24 > 18 이므로, 24를 18로 나눈다.
24 % 18 = 6(나머지)
그 다음으로, 18 > 6 이므로, 18을 6으로 나눈다.
18 % 6 = 0(나머지)
18이 6으로 나누어 떨어지므로, 24와 18의 최대공약수는 6이 된다.

자바 코드

public static int gcd(int p, int q){
	if(q == 0) return p;
    return gcd(q, p%q);
}

내가 짠 로직

private static void getMaxDiv(int n1, int n2){
        int r = Integer.MAX_VALUE;
        while(true){
            if(n1 > n2){
                r = n1 % n2;
                if(r ==0){
                    maxDiv = n2;
                    break;
                }
                n1 = r;
            }else{
                r = n2 % n1;
                if(r ==0){
                    maxDiv = n1;
                    break;
                }
                n2 = r;
            }
        }
    }

🎆BAEKJOON: 17087번 - 숨바꼭질6

기존의 문제들은 두 수의 최대 공약수 를 구하는 문제였지만, 이번 문제는 갯수가 N(1 ≤ N ≤ 10^5) 이므로, 반복문을 사용하여 N개의 수를 유클리드 호제법에 대입해준다.

	int[] Ds = { N개의 수 };
	int result = Ds[0];
    
	for(int i=0; i < Ds.length; i++){
		result = gcd(result, Ds[i]);
	}