[Java] 유클리드 호제법은 주로 최대공약수(GCD)와 최소공배수(LCM)을 구하는 유형에 쓰인다.

유클리드 호제법은 큰 수를 작은 수로 나누고, 그 나머지를 계속 나누어 나가면서
 나머지가 0이 될 때의 수가 최대공약수가 되는 방법이다.

이걸 반복해서 계산하면 최대공약수를 빠르게 구할 수 있다.

 

유클리드 호제법은 두 수의 최대공약수(GCD) 를 빠르게 구하는 방법이다.

이 방법은 나눗셈을 반복해서 사용하는 간단한 원리로 동작한다.

 

 

왜 유클리드 호제법이 필요한가?

 

두 수의 최대공약수를 구하려면 처음부터 약수를 다 찾아 비교하면 너무 시간이 오래 걸린다.

그래서 더 효율적으로 최대공약수를 구하기 위해 유클리드 호제법이 만들어졌다.

---

유클리드 호제법의 원리

두 수 a와 b가 있을 때 (단, a > b라고 가정):

1. a를 b로 나눈 나머지를 구한다.

   이 나머지를 r이라고 하자.

 

2. a를 b로 바꾸고, b를 r로 바꿔.

다시 말해, 더 작은 수와 나머지의 관계로 바꾸는 것이다.

 

3. 나머지가 0이 될 때까지 이 과정을 반복한다.

나머지가 0이 되는 순간, 그때의 b가 최대공약수(GCD)가 된다.

 

예시로 이해하기

12와 18의 최대공약수를 구해 보자.

1. 큰 수 18을 작은 수 12로 나눈 나머지를 구한다.

    그래서 나머지 6이다.

2. 이제 18을 12로 바꾸고, 12를 나머지 6으로 바꾼다.

다시 나눈다: 

3. 나머지가 0이 되었다!

 

이때의 값 6이 바로 최대공약수(GCD)이다.

 

코드로 보면 이렇게 된다. 

public int gcd(int a, int b) {
    if (b == 0) return a; // 나머지가 0이면 a가 GCD
    return gcd(b, a % b); // b와 나머지(a % b)로 다시 GCD 함수 호출
}

 

 

유클리드 호제법의 재귀 개념

유클리드 호제법은 재귀 함수의 구조를 활용해서 최대공약수를 구한다
재귀 함수란 자기 자신을 호출하는 함수를 말한다.

유클리드 호제법의 원리
두 수 a와 b(a > b)가 있을 때:
• GCD(a, b)는 GCD(b, a % b)와 같다.
• a % b는 a를 b로 나눈 나머지다.
• 나머지가 0이 되면, 그때의 b가 최대공약수(GCD)다.

재귀 함수 실행 과정 예시

예를 들어, gcd(12, 18)를 구해 보자:
1. 첫 호출:
gcd(12, 18) → 나머지 12 % 18 = 12
다음 호출: gcd(18, 12)
2. 두 번째 호출:
gcd(18, 12) → 나머지 18 % 12 = 6
다음 호출: gcd(12, 6)
3. 세 번째 호출:
gcd(12, 6) → 나머지 12 % 6 = 0
나머지가 0이므로 6을 반환.

최종 결과: GCD(12, 18) = 6

---

1. 기본 유형 - 최대공약수 구하기

 

문제

두 정수 a와 b가 주어졌을 때, 이 둘의 최대공약수(GCD) 를 구하는 프로그램을 작성하시오.

 

풀이 과정

1. 두 수를 입력받는다.

2. 유클리드 호제법을 사용해 최대공약수를 구한다:

• 큰 수를 작은 수로 나눈 나머지를 계속 계산한다.

• 나머지가 0이 되는 순간, 작은 수가 최대공약수다.

 

import java.util.Scanner;

public class Main {
     // 유클리드 호제법으로 최대공약수 구하기
     public static int gcd(int a, int b) {
         if (b == 0) return a; //나머지가 0이면 a가 최대공약수
         return gcd(b, a % b); // 재귀적으로 호출
     }
     
     public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int a = sc.nextInt();
       int b = sc.nextInt();
       
       System.out.println("최대공약수: " + gcd(a, b));
     }
}

---

2. 응용 유형 - 최소공배수 구하기

 

문제

두 수 a와 b의 최소공배수(LCM) 를 구하는 프로그램을 작성하시오.

풀이 과정

1. 최소공배수는 최대공약수를 사용해 구할 수 있다:

 

2. 유클리드 호제법으로 먼저 최대공약수를 구한 후, 위의 식을 통해 최소공배수를 계산한다.

 

import java.util.Scanner;

public class Main {
   // 최대공약수 구하기
   public static int gcd(int a, int b) {
     if (b == 0) return a;
     return gcd(b, a % b);
   }
   
   // 최소공배수 구하기
   public static int lcm(int a, int b) {
      return (a * b) / gcd(a, b); //LCM공식
   }
   
   public staic void main(String[] args) {
     Scanner sc = new Scanner(System.in);
     int a = sc.nextInt();
     int b = sc.nextInt();
     
     System.out.println("최소공배수: " + lcm(a, b));
   }
}

---

 

3. 문제 유형 - 배열의 최대공약수와 최소공배수 구하기

 

문제

여러 개의 수가 담긴 배열이 주어질 때, 배열의 모든 수의 최대공약수 와 최소공배수 를 구하시오.

 

풀이 과정

1. 최대공약수:

  배열의 첫 번째 값부터 순차적으로 GCD를 구하면 된다.

   • 예: GCD(GCD(1번, 2번), 3번) … 이렇게 반복한다.

2. 최소공배수:

  배열의 첫 번째 값부터 순차적으로 LCM을 구하면 된다.

   • 예: LCM(LCM(1번, 2번), 3번) … 이렇게 반복한다.

 

public class Main {
   // 최대공약수 구하기
   public static int gcd(int a, int b) {
     if (b == 0) return a;
     return gcd(b, a % b);
   }
   
   // 최소공배수 구하기
   public static int lcm(int a, int b) {
       return (a * b) / gcd(a, b);
   }
   
   public static void main(String[] args) {
      int [] arr = {12, 18, 24}; // 입력 배열
      
      // 배열의 최대공약수 구하기
      int resutlGCD = arr[0];
      for (int i = 1; i < arr.length; i++) {
          resultGCD = gcd(resultGCD, arr[i]);
      }
      
      // 배열의 최소공배수 구하기
      int resultLCM = arr[0];
      for (int i = 1; i < arr.length; i++) {
          resultLCM = lcm(resultLCM, arr[i]);
      }
      
      System.out.println("배열의 최대공약수: " + resultGCD);
      System.out.println("배열의 최소공배수: " + resultLCM);
   }
}

코드 해석

• 목표: 배열 {12, 18, 24}와 같은 여러 수의 최대공약수를 구하는 것.

• 과정: 배열의 모든 원소에 대해 두 수의 GCD를 차례로 구해나간다.

 

단계별 동작

1. resultGCD를 배열의 첫 번째 원소로 초기화한다.

   예: resultGCD = arr[0] = 12

2. for 반복문을 사용해서 배열의 나머지 원소들을 차례대로 순회한다.

3. resultGCD = gcd(resultGCD, arr[i])를 통해 현재 GCD와 다음 원소의 최대공약수를 계산하고, 그 값을 resultGCD에 저장한다.

     예:

     • 첫 번째 반복 (i = 1): gcd(12, 18) → 6

         → resultGCD = 6

     • 두 번째 반복 (i = 2): gcd(6, 24) → 6

         → resultGCD = 6

4. 반복이 끝나면 resultGCD에 배열 전체의 최대공약수가 저장된다.

 

재귀가 배열 전체에 적용되는 과정

앞서 설명한 배열 전체 최대공약수 구하기 코드에서는 gcd 함수를 계속 호출해서 각 원소를 순차적으로 비교한다.

1. 초기값: resultGCD = arr[0]

2. 첫 반복:

• gcd(resultGCD, arr[1]) → 두 원소의 최대공약수를 구함.

3. 다음 반복:

• 이전까지의 최대공약수(resultGCD)와 다음 원소(arr[i])를 비교해서 다시 GCD를 구함.

4. 반복 끝:

• 최종 resultGCD는 배열 전체의 최대공약수다.

 

---

 

유클리드 호제법은 최대공약수를 빠르게 구하는 핵심 알고리즘이다. 이를 활용해 최소공배수 문제도 해결할 수 있다. 시험에서는 두 수를 다루는 기본 문제부터 배열 전체를 다루는 고급 문제까지 출제될 수 있으니 원리를 이해하고 차근차근 적용하면 된다.