최대 공약수 구하기

프로그래머스 0단계 57.분수의 덧셈

https://js0616.tistory.com/75

 

 

최대 공약수란?

두 수를 나누었을때 나누어 떨어지는 공통의 수 중에서 가장 큰 수 이다. 

 

예를들어 12와 18의 경우

2, 3 , 6 으로 각각 나누면 나머지가 없이 나누어 떨어진다. 

그 중에서 가장 큰 수인 6이 최대 공약수가 된다.

 

코드로 이걸 어떻게 해결할까 ? 

 

2-1. num1 의  약수들을 구해 배열로 만들고

2-2. 그 배열의 원소가 num2 를 나누었을때 나머지가 없다면 그 원소는 num1, num2 의 공약수가 된다.

2-3. 그리고 그 공약수 중에서 가장 큰 수가 최대 공약수가된다.

 

// 최대공약수

const divlist = function(n,m){

    let arr = [] // 2-1) n의 약수가 들어가는 배열

    let ans = 1

    // n 의 약수를 구하는 for 문

    for (let i = n ; i>=2 ; i--){

        if(n%i == 0){

            arr.push(i)

        }

    }

    // 2-2)  n 의 약수가 m 의 약수인지 확인

    for (i of arr){

        if(m%i ==0){

            // 2-3)

            ans = i

            return ans

        }

    }

    return ans

}

 

 

for 문의 i 값을 n 부터 감소하도록 한 이유는

 

우리가 필요한 값은 최대 공약수 한개이므로 가장 큰값부터 비교할수있도록 배열에 담았다.

 

arr 의 가장 큰 값부터 m의 약수인지 (공약수) 인지 판단하는 두번째 for 문을 이용하고

 

arr의 원소가 m의 약수라면 최대 공약수만 구하면 되므로 더이상 진행할 필요없이

그 원소값을 retrun 하도록 ans 값에 담아주었다.

 

그리고 공약수가 없다면 즉 이미 기약분수 상태라는 의미이므로 1을 return 하도록 하였다.

 

---

두번째 방식

 

function fnGCD(a, b){

    return (a%b)? fnGCD(b, a%b) : b;

}

위의 식과 같은 기능을 하지만 굉장히 간략하다.

 

삼항연산자에 재귀함수 형태인데 코드를 해석하자면

 

(a%b)?  -> 참이면 fnGCD(b,a%b) 

거짓이면 b를 return 한다.

 

 

1. js 에서 0 은 false 거짓을 의미한다. 는 성질을 이용하여

a%b ==0 이다. -> 거짓이다 -> b 이다.

 

즉 a를 b 로 나눴을때 나머지가 0 이면 b가 최대 공약수 라는 의미이다.

예를 들면 fnGCD(12,4) 라고 하면 12 의 최대공약수는 4가 된다는 뜻이다.

 

그렇다면 a%b 가 0이 아니라면 (나누어 떨어지지 않는다면) 

-> 참이라면 -> fnGCD(b, a%b) 를 다시 수행하게된다.

 

예를 들면 fnGCD(18,12) 의 경우

18 % 12 == 6 으로 -> fnGCD(12 , 6 ) 이 되고

12 % 6 == 0 으로 -> 6 이 retrun 되게 된다.

 

 

조금 더 큰 숫자로 한번 더 해보면

 

420 , 108 -> 108 , 96 -> 96 12 -> 12 가 나오며

console.log(fnGCD(420,108)) 의 결과도 12가 나온다.

 

약수를 구하는데 나머지를 이용한다는점이 독특한 풀이인거같다.

 

납득이 안가서 조금 더 찾아보니 유클리드 알고리즘 , 유클리드 호제법 이라고 부른다.

 

이부분은 정수론의 영역이라고 생각되며

 

궁금하다면 아래의 링크에서 더 확인 할 수 있다.

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95#s-3.1