두 개 이상의 숫자(또는 배열에 담긴 여러 숫자)의 최대공약수(GCD, Greatest Common Divisor)를 구하는 것은 알고리즘 문제에서 자주 등장하는 기본 주제입니다. 아래 예제는 유클리드 호제법(Euclidean Algorithm)을 재귀 함수로 구현한 뒤, 배열의 모든 요소에 순차적으로 적용하여 전체 배열의 GCD를 계산하는 자바 프로그램입니다.
예제 코드
public class Demo{
static int gcd_of_nums(int val_1, int val_2){
if (val_1 == 0)
return val_2;
return gcd_of_nums(val_2 % val_1, val_1);
}
static int find_gcd(int arr[], int no){
int result = arr[0];
for (int i = 1; i < no; i++){
result = gcd_of_nums(arr[i], result);
if(result == 1){
return 1;
}
}
return result;
}
public static void main(String[] args){
int my_arr[] = { 7, 49, 177, 105, 119, 42};
int no = my_arr.length;
System.out.println("배열 요소들의 최대공약수(GCD)는 ");
System.out.println(find_gcd(my_arr, no));
}
}실행 결과
배열 요소들의 최대공약수(GCD)는 1
코드 동작 원리
1. 두 수의 GCD 계산 — gcd_of_nums 메서드
클래스 Demo에는 두 개의 정수 값을 받아 최대공약수를 계산하는 정적(static) 메서드 gcd_of_nums가 정의되어 있습니다. 이 메서드는 유클리드 호제법을 재귀 방식으로 구현한 것으로, 첫 번째 값이 0이면 두 번째 값이 곧 최대공약수이므로 그대로 반환합니다. 그렇지 않은 경우에는 나머지 연산(%)을 활용해 첫 번째 인자와 두 번째 인자의 나머지를 재귀적으로 호출하며 GCD를 구합니다.
2. 배열 전체의 GCD 계산 — find_gcd 메서드
다음으로 정의된 find_gcd 메서드는 정수 배열과 배열의 길이를 매개변수로 받습니다. 먼저 배열의 첫 번째 요소를 변수 result에 저장하고, for 루프가 인덱스 1부터 배열 끝까지 반복하면서 각 요소와 현재 result 값에 대해 GCD 함수를 호출합니다. 그 결과는 다시 result에 누적 저장됩니다.
여기서 중요한 최적화 포인트가 하나 있습니다. 최대공약수는 절대 1보다 작아질 수 없으므로, 중간에 result 값이 1이 되면 더 이상 반복할 필요가 없습니다. 따라서 즉시 1을 반환하여 불필요한 연산을 줄일 수 있습니다.
3. main 메서드의 실행 흐름
main 메서드에서는 정수형 배열 my_arr를 선언·초기화하고, 배열의 길이를 length 속성으로 구해 변수 no에 할당합니다. 이후 find_gcd 함수에 배열과 길이를 전달하여 결과를 얻고, 콘솔에 출력합니다.
정리
이 프로그램은 유클리드 호제법의 재귀 구현과 배열 순회를 결합하여, 두 개 이상의 임의 개수 숫자에 대해서도 확장 가능한 GCD 계산 방식을 보여줍니다. 시간 복잡도는 각 GCD 계산이 O(log(min(a, b)))이므로, n개의 요소에 대해 대략 O(n log M)(M은 최댓값) 수준으로 효율적입니다. 실무에서도 여러 수의 공통 약수나 분수 약분, 주기 계산 등에 널리 활용되는 패턴이니 꼭 익혀두시기 바랍니다.