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

 

프로그래머스 - N개의 최소공배수난이도

 

 

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

난이도 : Level 2
정답률: 67%

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

▶ 문제

 

▶ 풀이

function solution(arr) {
    let answer = 0;
    

    let n = 1
    let flag = true;
    while(flag)
    {
        n++;
        for(let i = 1; i < arr.length; ++i){
            if((arr[0] * n) % arr[i]  === 0){
                flag = false;
            } else {
                flag = true;
                break;
            }
        }
    }
    answer = arr[0] * n;
    return answer;
}

한 숫자를 곱하고 남은 나머지의 값이 모두 0으로 떨어지면 모든 값의 최소공배수가 구해질 거라고 생각하고 코드를 짰다.

이렇게 짤 경우 최소공배수의 값이 클수록 while 루프가 오래 반복되므로 시간이 기하급수적으로 증가할 수 있다.

▶ 다른 사람의 풀이(좋은 풀이)

// 또 다른 풀이
function getGcd(a, b) {
  if (b === 0) return a;
  return getGcd(b, a % b);
}

function solution(arr) {
  return arr.reduce((a, b) => (a * b) / getGcd(a, b));
}

(유클리드 호제법을 이용한 풀이)

이 풀이의 빅오표기는 O(N log M) 이다.

 

알기 쉽게 내가 짠 코드와 비교하면 다음과 같다.

입력 배열	유클리드 방법	내가 짠 코드
[2, 3]	O(1)	O(6)
[2, 3, 4]	O(1)	O(12)
[2, 3, 5, 7, 11]	O(log M)	O(2310[모든 수의 곱]) (매우 비효율적)
[10, 15, 20, 25, 30]	O(log M)	O(300) (매우 비효율적)

유클리드 방법은 log 시간에 해결 가능 (훨씬 빠르다!)

 

▶ 📌 유클리드 호재법이란?

 

유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 알고리즘이다. 그 성능이 어마어마하게 떠오

유클리드 호재법의 원리

두 자연수 AAA와 BBB (A>BA > BA>B)가 있을 때,

1. AAA를 BBB로 나눈 나머지를 구한다.
2. 만약 나머지가 0이면 BBB가 최대공약수(GCD)이다.
3. 나머지가 0이 아니라면, AAA를 BBB로, BBB를 나머지로 바꾸고 1번 과정을 반복한다.

example)
1071과 1029의 최대공약수를 구한다고 하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ==> 나머지는 42 이다.

나머지가 42 니까 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ==> 나머지는 42 이다.
나머지가 21 이면 42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.

이제 당신도, 최대공약수 마스터이다!

 

▶ 느낀점

 

유클리드 호재법의 시작은 기원전 300년경 고대 그리스 수학자 유클리드부터라고 한다. 그 얘길 듣고 고등학교 선생님이 이제 된 친구의 얘기가 떠올랐다. 우리나라에 수포자가 많은 이유는 수학이란 과목만은 지름길이 없기 때문이라고 한다.

국어나 사회, 과학, 영어는 중간부터 공부한다고 해도 따라갈 순 있지만, 수학의 경우에는 덧셈을 모를 경우 곱셈을 알려줄 수 없고, 곱셈을 모르는 아이한테 방정식을 알려줄 수 없다고 한다. 

그 말이 참 맞는 말이라는 생각이 들었던 게 내가 개포자(개발포기자) 라고 스스로 생각했던 시기가 그랬던 것 같다.

JS의 동작 원리도 제대로 모르는 상태로 리액트와 vue 부터 접했으니, 새로운 기술이 생긴 배경도 모른체 따라하는 코더가 되며 개발에 흥미를 잃었던 것이다.

평생 가야할 길에서는 지름길이 더 느릴 수도 있다는 생각이 든다. 탄탄하게 나아가자.