[프로그래머스] N개의 최소공배수

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

 

https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=java

프로그래머스

---

Think🤔

 

1. 최대공약수 구하는 방법 
2. 유클리드 호제법 이용
3. 최대공약수를 구한 후 최소공배수 = ( a * b ) / 최대공약수

 

- 유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 두 개의 자연수의 최대공약수를 구하는 방법 중 하나입니다. 이름은 그리스의 수학자 유클리드에게 영감을 받아 지어졌습니다. 이 방법은 두 수를 나누고 나머지를 이용하여 계속해서 나누어가면서 두 수의 최대공약수를 찾아내는 간단하고 효율적인 알고리즘입니다. 여기에는 두 가지 과정이 있습니다:

두 수 중 큰 수를 작은 수로 나눕니다.
나머지가 0이 아니라면, 작은 수를 큰 수로, 나머지를 작은 수로 대체합니다.
나머지가 0이 되면, 그 때의 큰 수가 최대공약수가 됩니다.
이 방법은 반복적으로 나누기 연산을 통해 최대공약수를 찾기 때문에 효율적이며, 재귀적으로 구현할 수도 있습니다. 최대공약수를 구하는데 유클리드 호제법은 매우 효율적이며 널리 사용되는 방법 중 하나입니다.

---

Solution✍

 

최소공배수를 구하긴 위해서 최대공약수를 이용한다

먼저 최대공약수는 보통 gcd , 최소공배수는 lcm으로 표현

 

import java.lang.Math;

// 최대공약수 gcd
// 최소공배수 lcm

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for(int i=1; i<arr.length; i++){
            answer = lcm(answer,arr[i]);
        }
        
        return answer;
    }
    
    public int gcd(int a,int b){
        
        int big = Math.max(a,b);
        int small = Math.min(a,b);
        
        // 작은 값으로 큰 값을 나눴을 때 0이되면 작은 값이 최대공약수가 됨
        if(big % small == 0){ 
            return small;
        }
        
        // 아닐경우 작은 값을 앞 , 나머지를 뒤
        return gcd(small,big % small);
    }
    
    public int lcm(int a,int b){
        return (a * b) / gcd(a,b);
    }
}

---

Review🤩

 

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

 

최대공약수를 구할때 이렇게도 가능한데, 작은값이 왜 b인지 a == 0 return b는 왜 안되는지 이해가 안됨.

 

2 , 4일 경우

gcd(4, 0)이 들어가고 뒤에는 자동적으로 작은 값이 들어감

---