배열 요소 최대공약수 구하기

안녕하세요! 오늘은 유클리드 호제법을 활용한 배열 요소의 최대 공약수 구하기 문제를 해결해보려합니다. 

X라는 값을 Y로 나눌 때 나눈 값이 X%Y라면 이걸 Y로 다시 나누고 이 과정을 반복해서 하면 됩니다.

예를 들어, 10과 25의 최대 공약수를 구한다고 할 때 25의 길이 만큼의 상자를 10인 상자로 채우다가 남은 5만큼의 

공간을 다시 5로 채우고 더이상 채울 곳이 없을 때 나눴던 5를 반환하는 것이다.

가령 22와 8이라는 숫자로 비교한다면, 길이 22만큼의 공간을 차지하는 상자에 8만큼의 공간을 차지하는 상자를 넣었을 때

6만큼의 공간이 남을 것이다. 

즉, 8x6만큼의 공간이 남을테고, 이를 6x6 상자로 채웠을 때 2x6만큼의 공간이 남을 것이다.

따라서 2x2인 상자로 채워서 빈 공간이 없도록 만들 수 있기 때문에 최대 공약수는 2가된다.

따라서 gcd코드는 아래와 같습니다. 

---

static int gcd(int x,int y){

if(y==0)

return x;

else 

return gcd(y,x%y);

}

다음처럼, 나누는 값이 더이상 없을 때, 즉, 딱 떨어질 때 나누는 값을 반환하면 최대 공약수입니다.

그렇지 않다면, 나누려는 몫을 나머지로 계속해서 나누는 작업을 반복하면 됩니다.

gcdArray함수는 함수내의 모든 요소를 다음과 같은 gcd 함수 작업을 진행하면 됩니다.

각 요소들을 비교하면서 최대공약수를 구하고, 또 각 요소들을 비교하면서 최대공약수를 구합니다.

다음과 같은 작업을 배열 요소의 길이만큼 진행합니다. 

그렇게 구한 전체의 최대 공약수 값을 한 번 더 구하면 배열 요소의 최대공약수 값과 같아집니다.

따라서 코드는 아래와 같습니다. 

---

static int gcdArray(int[] a,int start,int no){

if(no == 1){

return a[start]; // 배열 요소가 하나일 때 해당 값 반환 

} else if(no == 2){

return gcd(a[start] , a[start+1]); // 비교 대상이 두 개일 경우, 처음 요소와 그 다음 요소의 최대 공약수를 구해서 반환 

} else {

return gcd(a[start] , gcdArray(a,start+1,no-1));  

// 처음 요소는 그대로 둔 채, 다음 요소부터 배열 요소들을 하나씩 계속 파악, 배열 갯수는 하나씩 

// 줄어들면서 재귀적 호출 --> 배열 요소를 싹 다 gcd 작업을 거친 뒤에 마지막에 a[start]와도 gcd 작업을 통해 

// 배열 요소의 최대 공약수를 구한다.  

}

}

---

다음 유클리드 호제법을 활용한 최대 공약수 구하는 것은 많이 나오는 패턴이기 때문에 

익혀두고, 배열 요소 내의 최대 공약수 구하는 것도 재귀적 호출을 통해 컴팩트하게 구하는 것이므로 

익혀두는 것이 좋습니다.  감사합니다.