최소 공배수 코드 - choeso gongbaesu kodeu

위 알고리즘은 유클리드 호제법을 나타낸 알고리즘이다.
예를 들어, 10과 8의 최대 공약수를 구한다고 하면 b(a를 b로 나눈 나머지)가 0보다 클동안 반복한다.
1. a = 10, b = 8, 나머지 2 => a = 8, b = 2
2. a = 8, b = 2, 나머지 0 => a = 2, b = 0

최소 공배수 (Least Common Multiple)

사진과 같이 이 수로 나누면 나누어질 것 같은데? 라고 생각드는 숫자를 넣어 두 숫자를 나눠보면 나눠질 때도 있고 나누어지지 않을 때도 있다. 이렇게 해서 계속 나누다 보면 1로 밖에 나누어지지 않을 때가 나오는데, 그 때 두 수를 서로소라고 하며 서로소는 최대공약수가 1인 수다. 그리고 왼쪽에 나열했던 수를 나눴던 수는 두 수의 공약수가 된다. 나눈 수들을 전부 곱하면 그 수가 최대공약수가 된다.

최대공약수와 최소공배수를 알고리즘을 통해 구하고 내용을 정리한다.

최대공약수를 구하기 위해 매우 쉬운 공식이 있다. 바로 유클리드 호제법이다. 에우클레이데스라는 그리스의 수학자가 만든 호제법이란 소린데 호제법의 호는 서로 호(互)와 나누다, 덜다라는 뜻의 덜 제(除)를 써 서로 즉 두 수를 나눈다는 뜻이다.

2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

(이게 무슨 소리야?) 이 성질을 이용해서 위의 과정을 계속 반복해 나머지가 0이 나올 때까지 나누면 그 수가 바로 최대공약수라는 소리다.

계산 과정

예를 들어 두 수 648과 232을 입력받는다고 했을 때, 두 수에서 더 큰 수는 648이기 때문에 a를 648로 두고 위의 과정에 대입해서 계산해본다. 648을 232로 나눴을 때 나누어 떨어지지 않기 때문에 나머지를 구한다.

• 648 % 232 = 184, 232는 184로 나누어 떨어지지 않음 다시 나눔
• 232 % 184 = 48, 184은 48로 나누어 떨어지지 않음 다시 나눔
• 184 % 48 = 40, 48은 40으로 나누어 떨어지지 않음 다시 나눔
• 48 % 40 = 8, 40은 8로 나누어 떨어지므로 최종적으로 r은 0이 되므로 계산 종료 최대공약수는 8

구현

위의 과정과는 비슷하지만 조금 다르게 함수로 구현할 수 있다. 두 수를 입력으로 받고 작은 수가 0이 될때 까지 나눈다.

function gcd(a, b) {
  let r
  while (b != 0) {
    r = a % b
    a = b
    b = r
  }
  return a
}

구현은 매우 간단하다. 나누어 떨어질 때까지 나누어서 최대공약수를 구한다. 두 수가 만약 거대하고 최대공약수가 반드시 1인 두 수라면 시간이 걸릴진 몰라도 빠르게 최대공약수를 구할 수 있다.

최소공배수보다 최대공약수를 먼저 서술한건 최소공배수의 성질을 이용해 쉽게 구할 수 있기 때문이다. 비교적 적은 최소공배수의 성질 중에 이런 성질이 있다. 두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다. 이 성질을 이용해서 위의 최대공약수를 구하는 함수와 함께 최소공배수를 쉽게 구할 수 있다.

최대 공약수 구하는 방법

1. 숫자가 2개인 경우 

1) 두 수를 공약수로 계속 나눈다. 

2) 공약수로 나눈 몫이 서로소가 되면 stop 

3) 왼쪽 공약수를 모두 곱한다. 

∴ 60 과 48의 최대 공약수 : 2 ✕ 2 ✕ 3 = 12

2. 숫자가 3개 이상인 경우

- 코드에서 배열이 매개변수로 주어지는 경우

1. 모든 수를 동시에 반드시 나눌수 있는 수로 나눈다. 

2. 더이상 동시에 나눌 수 없으면 stop 

3. 왼쪽 공약수를 모두 곱한다. 

∴ 60, 48, 40 의 최대공약수 : 2 ✕ 2 = 4

최소 공배수 구하는 방법

1. 숫자가 2개인 경우

1) 두 수의 공약수로 나눈 몫이 서로소가 될 때까지 나눈다. 

2) 왼쪽 공약수들과 아래 서로소까지 모두 곱한다. 

∴ 60 과 48의 최소 공배수 : 2 ✕ 2 ✕ 3 ✕ 5 ✕ 4= 240

2. 숫자가 3개 이상인 경우 

- 코드에서 배열이 매개변수로 주어지는 경우

1) 서로소가 아닌 수가 2개라도 있으면 그 수들의 공약수로 나눈다.
   나누어 떨어지지 않는 수는 그대로 밑에 내려온다. 

2) 모든 몫이 서로소이면 stop 

3) 왼쪽 공약수와 아래 서소로를 모두 곱한다.

∴ 60, 48, 40 의 최소 공배수 : 2 ✕ 2  ✕ 2 ✕ 3 ✕ 5 ✕ 1 ✕ 2 ✕ 1= 240

유클리드 호제법 

2개 수의 최대 공약수를 구하는 알고리즘이다. 

원리는 다음과 같다. 

자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면 a,b의 최대공약수와 b,r의 최대공약수는 같다. 

이 성질에 따라 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구한다.  

나머지가 0이 될때 나눈 수가 a,b의 최대공약수가 된다. 

유클리드 호제법으로 최대 공약수를 구한 다음, 최소 공배수는 다음 식에 의해 구할 수 있다. 

최소 공배수 : (a ✕  b) / (최대 공약수)

ex) 60, 48 의 최대공약수 :
     60 % 48 = 12
     48 % 12 = 0 // 최대 공약수 : 12

// 최소 공배수 : (60 ✕ 48) / 12 = 240

만약 수가 여러개라면 최소 공배수를 어떻게 구하면 될까?

숫자 A,B,C 가 있을 경우

1) A,B의 최소 공배수를 구한다. 
2) 1에서 구한 A,B의 최소 공배수와 C의 최소공배수를 구한다. 

[JAVA code]

유클리드 호제법을 이용한 코드이다. 

1. 숫자가 2개인 경우

package com.algorithm.level2;

import java.util.Arrays;
import java.util.Stack;

public class Test12 {
    public static void main(String[] args) {
        int num1 = 60;
        int num2 = 48;

        int gcd = getGCD(num1, num2);
        System.out.println("the greatest common denominator : " + gcd);
        System.out.println("the lowest common multiple : " + (num1 * num2) / gcd);
        
    }

    public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1%num2);
    }
}

2. 숫가 여러개일 때  (매개변수 배열)

package com.algorithm.level2;

public class Test12 {
    public static void main(String[] args) {
        int[] arr = {2, 6, 8, 14};

        System.out.println("the lowest common multiple : " + getLCM(arr));
    }

    public static int getLCM(int[] arr) {
        if (arr.length == 1) {
            return arr[0];
        }

        int gcd = getGCD(arr[0], arr[1]);
        int lcm = (arr[0] * arr[1]) / gcd;

        for (int i = 2; i < arr.length; i++) {
            gcd = getGCD(lcm, arr[i]);
            lcm = (lcm * arr[i]) / gcd;
        }

        System.out.println("the greatest common demoniator : " + gcd);

        return lcm;
    }

    public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1 % num2);
    }
}

공유하기

게시글 관리

'코딩 테스트 > TIP' 카테고리의 다른 글