Java/Short 개발

[Java/Short] 최대공약수, 최소공배수 구하는 방법 : 두 수 또는 N개의 수

adjh54 2023. 5. 9. 23:04
반응형
해당 글에서는 최대공약수와 최소공배수를 구하는 방법에 대해서 짧게 이해하는 방법에 대해서 공유합니다.



💡 해당 글을 이해하기 전에 상세하게 이해하고 싶다하시면 아래의 글이 큰 도움이 됩니다.
 

[Java/알고리즘] 유클리드 호제법 : 최대공약수, 최소공배수

해당 글에서는 최대공약수, 최소공배수에 대해서 이해하고 두 개의 수가 주어질 때 구하는 방법과 N개의 수가 주어질 때 최대공약수, 최소공배수를 구하는 방법에 대해서 공유합니다. 1) 유클리

adjh54.tistory.com

 

 

1) 두수의 최대공약수, 최소공배수 구현방법

1. 최대공약수(GCD) 구현

💡 유클리드 호제법 이용하여서 “최대공약수(GCD)”를 구하는 방식입니다.

💡 이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될때까지 작동하여 최대공약수를 구하는 방식입니다.

 

1. 재귀 방식으로 구현

💡 b가 0이라면 a가 최대공약수가 되며, 그렇지 않으면 b와 a % b의 최대공약수를 구합니다.
💡 이를 재귀적으로 반복하여 최대공약수를 구할 수 있습니다.
// 재귀 방식
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

 

 

2. 반복문 방식으로 구현

💡 먼저, b가 0이 될 때까지, a를 b로 나눈 나머지를 b에 대입하고, a와 b의 값을 교환합니다.
💡 이를 반복하여 최대공약수를 구할 수 있습니다.
// 반복문 방식
public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

 

2. 최소공배수(LCM) 구현

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

 

 

 

2) N수의 최대공약수, 최소공배수 구현방법

1. 최대공약수(GCD) 구현

💡 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 “최대공약수”를 구합니다.

1. result 변수를 배열의 첫 번째 값으로 초기화합니다
2. 반복문을 통해 배열의 나머지 값들과 최대공약수를 구하여 result 변수에 저장합니다.
3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최대공약수가 됩니다.
public static int gcd(int[] arr) {
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = gcd(result, arr[i]);
    }
    return result;
}

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

 

 

2. 최소공배수(LCM) 구현

 💡 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든수의 “최소공배수”를 구합니다.

1. result 변수를 배열의 첫 번째 값으로 초기화합니다
2. 반복문을 통해 배열의 나머지 값들과 최소공배수를 구하여 result 변수에 저장합니다.
3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최소공배수가 됩니다.
public static int lcm(int[] arr) {
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = lcm(result, arr[i]);
    }
    return result;
}

public static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

 

 

 

 

오늘도 감사합니다. 😀

 

 

 

반응형