[알고리즘 기초 100제] 6. 최대공약수 구하기

✔️문제

- 입력된 두 수의 최대공약수를 구하시오
- 12 18
- 정답: 6

---

📍정답

1. 유클리드 호제법 (반복문)

package _06_GCD;

public class Main_GCD {

  public static void main(String[] args) {
    int num1 = 12;
    int num2 = 18;

    int gcd = findGCD(num1, num2);
    System.out.println("최대공약수: " + gcd);
  }

  // 유클리드 호제법을 사용한 최대공약수(GCD) 계산
  public static int findGCD(int a, int b) {
    while (b != 0) {
      int temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }

}

유클리드 호제법 (GCD 구하는 알고리즘
- 알고리즘 원리
      1. GCD(a, b) = GCD(b, a % b)를 반복
      2. 나머지가 0이 되면, 나누는 값(b)이 최대공약수(GCD)
- 예제: findGCD(12, 18) 계산 과정
      1. 12 % 18 = 12 → findGCD(18, 12)
      2. 18 % 12 = 6 → findGCD(12, 6)
      3. 12 % 6 = 0 → GCD = 6
- 결과: GCD(12, 18) = 6

 

2. 반복문(브루트 포스)

package _06_GCD;

public class Main_Loop {

  public static void main(String[] args) {

    int num1 = 12;
    int num2 = 18;

    int small;
    int big;

    if (num1 > num2) {
      big = num1;
      small = num2;
    } else {
      big = num2;
      small = num1;
    }

    int gcd = 1; // 최대공약수

    for (int i = 1; i <= small; i++) { // Math.min(a, b)
      if (big % i == 0 && small % i == 0) {
        gcd = i;
      }
    }
    System.out.print(small + "과 " + big + "의" + " 최대공약수는:" + gcd);

  }
}

 

3. 유클리드 호제법 (재귀)

package _06_GCD;

public class Main_Recursive {

  public static void main(String[] args) {
    int num1 = 12;
    int num2 = 18;

    int gcd = findGCD(num1, num2);
    System.out.println("최대공약수: " + gcd);
  }

  // 재귀를 이용한 최대공약수 계산
  public static int findGCD(int a, int b) {
    if (b == 0) {
      return a;
    }
    return findGCD(b, a % b);
  }

}

📍비교

방법	장점	단점	추천 상황
유클리드 호제법 (반복문)	빠르고 효율적	없음	일반적인 경우(추천!)
유클리드 호제법 (재귀)	코드가 간결	재귀 호출이 많으면 스택 오버플로우 가능	코드 단순화가 필요할 때
반복문 (브루트 포스)	이해하기 쉬움	성능이 느림	숫자가 작을때