(24.05.09)[4주차] 유클리드 호세법 최대공약수, 최소공배수

팀 과제가 마무리 되어가고 있고,

추가로 개인 학습으로

쓰레드 Thread 관련하여 개인적으론 학습을 하고 있었기 때문에 CODE KATA나 개인 과제에 활용을 하려고 했지만,

아직 부족하여.. 추후 Spring 에 들어가기 전에 빠르게 CODE KATA에 기휘가 있다면 활용할 수 있도록

 

---

CODE KATA 정리

 

유클리드 호세법 최대공약수, 최소공배수 구하기 알고리즘

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int n = 16;
        int m = 8;

        int gcd = getGCD(n, m);
        int lcm = n * m / gcd;
        int[] answer = {gcd, lcm};
        System.out.println(Arrays.toString(answer));
    }

    public static int getGCD(int n, int m) {
        //작은값 큰값 구분
        int min = Math.min(n, m);
        int max = Math.max(n, m);

        while (min != 0) {
            int remain = max % min;
            max = min;
            min = remain;
        }
        return max;
    }
}

• 유클리드 호세법으로 최대공약수(GCD, Greatest Common Divisor), 최소공배수(LCM, Least Common Multiple)을 구하는 알고리즘을 혼자서 구현해보기 (단, 매개변수 int 값들은 1이상의 정수라 가정)
  • 유클리드 호세법을 사용하지 않을 경우,  for문을 입력된 두 정수를 각각 사용해서 1부터 자기 자신까지 나눠봐서 약수를 각각 구한후, 비교를 통해 최대 공약수를 구해야 했을 것.

 

• 유클리드 호세법에 의한 GCD , LCM
  • GCD : 두 자연수중 큰 수를 작은 수로 나누고, 작은 수를 그 나머지로 나누는 것을 나머지가 0일 때까지 반복 -> 0으로 떨어지게 하는 그 나머지가 최대공약수
  • LCM : 최소공배수는 두 자연수의 겹치지 않은 모든 약수를 곱한 값이기 때문에, 두 자연수의 곱에서 GCD를 나눈 값이 최소공배수
• 대부분의 알고리즘에ㅓ는 두 자연수가 무조건 작은 수가 앞에 있을 것이라고 가정을 했지만, getGCD메서드에서  Match 패키지 min max 메서드를 사용해서 따로 지정을 해줬음
  
  • 추가로 for문을 통해서 계속 나누는 min = remain이 0이 될때까지 진행하고 그 진행하는 동안 변경된 변수 max가 최대공약수가 됨
• 최대공약수를 구하는 메서드를 main 메서드 안에 기능 자체를 구현할 수 있었지만, 어차피 Main 클래스 안에 있는 두개의 메서드이기 때문에 또다른 메서드를 만들어서 활용하는 방법을 연습하기 위해 작성
  • static인 main 메서드 이기 때문에 getGCD는 static 메서드, 최소공배수는 1이상의 양의 정수이기 때문에, 출력값은 int 타입

---