공log/[JAVA]

[JAVA] 자바 #1 - 최대 공약수와 최소 공배수

ming_OoO 2023. 9. 4. 01:04
728x90

1. 유클리드 호제법(Euclidean Algorithm)

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘입니다.

두 수의 최대공약수란, 두 수를 모두 나누어 떨어지는 가장 큰 수를 말합니다.

유클리드 호제법은 다음과 같은 과정으로 이루어집니다.

  1. 두 수 중에서 큰 수를 A, 작은 수를 B라고 합니다.
  2. A를 B로 나눈 나머지를 R이라고 합니다. 즉, A를 B로 나눈 나머지를 구합니다.
  3. R이 0이 되면, B가 두 수의 최대공약수입니다.
  4. R이 0이 아니면, 이제 B를 R로 대체합니다.
  5. 다시 R을 B로 나누고 나머지를 구합니다.  
  6. 위 과정을 나머지가 0이 될 때까지 반복합니다. 
  7. 나머지가 0이 되면, 그 때 B가 최대공약수(GCD)가 됩니다.
💡 유클리드 호제법/알고리즘(Euclidean Algorithm) 이란?
     - 두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘을 의미합니다.
     - 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될때까지 작동하는 방법을 의미합니다.
     - 그때 작은 수가 최대공약수입니다.

2. 두 수의 약수와 배수 구현

2. 1 약수 구하기

for 문을 통해 1부터 n까지 반복하며 n을 i로 나누어 나머지가 0인 경우, 즉 약수일 때마다 i를 출력

int n = 약수를 구할 수;
for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
        System.out.println(i);
    }
}

2. 1 배수 구하기

int n = 배수를 구할 수;
for (int i = 1; i <= 10; i++) {
    System.out.println(n * i);
}

3. 두 수의 최대 공약수와 최소 공배수 구현

3.1 최대 공약수(GCD) 구현

위의 유클리드 호제법 이용하여서 “최대공약수(GCD)”를 구하는 방식을 구현

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

1. 재귀 함수로 구현

  • B가 0이라면 A가 최대공약수가 되며, 그렇지 않으면 B와 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(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;
}

3.2 최소 공배수(LCM) 구현

최대공약수의 함수를 기반으로 “최소공배수”를 구합니다.

해당 방식은 함수 내부에서 두 수 A와 B의 최대 공약수를 이용하여 최소 공배수를 계산

최소 공배수두 수의 곱에 최대 공약수를 나눈 값과 같습니다.

예를 들어, 12와 18의 최대공약수는 6 -> 12와 18의 최소공배수는 12 x 18 / 6 = 36

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

 

728x90

'공log > [JAVA]' 카테고리의 다른 글

[JAVA] 자바 #5 - 정규식  (1) 2023.10.23
[JAVA] 자바 #4 - 투 포인터  (0) 2023.09.25
[JAVA] 자바 #3 - 제네릭  (1) 2023.09.25
[JAVA] 자바 #2 - 진법 변환하기  (0) 2023.09.04