TIL : Javascript로 최대공약수(Greatest Common Divisor, GCD) 구하는 함수 만들기

TIL : Javascript로 최대공약수(Greatest Common Divisor, GCD) 구하는 함수 만들기

 

산수문제 하나 해결하고 뿌듯한게.. / picture by 캡틴.

 

최대공약수? 언제 배웠는지도 기억이 없는 산수 개념을 가지고 함수를 만들게 되었다.

'두 가지 숫자가 주어지면, 두 숫자의 최대공약수를 반환하는 기능' 을 구현하는 것이 오늘의 목표.

 

먼저, 최대공약수의 정의와 알고리즘 구상을 위해 계산법을 참고하였다.

 

 

---

1) 최대공약수 : 두 가지 숫자가 공통으로 갖는 공약수 중에 가장 큰 값.

 

2) 계산법 : 

  2) - ① 소인수분해법

             :  주어진 두 숫자를 더 이상 나눌 수 없는 소인수 단위로 각각 분해한 후에,

                공통된 소인수의 곱을 구하는 방법.

 

               * 예시 : 192와 72의 최대공약수 구하기

                 192 = 2 X 2 X 2 X 2 X 2 X 2 X 3

                 72  = 2 X 2 X 2 X 3 X 3

                  →　공통된 소인수의 곱 = 2 X 2 X 2 X 3 = 24 (최대공약수)

 

  2) - ② 유클리드 호제법

             : 큰 수와 작은 수를 구별한 후, 작은 수로 큰 수를 나누고 나머지를 확인한다.

               

               나머지가 남는 경우에는, 작은 수와 나머지 값을 가지고 한 번 더 나눗셈으로 나머지 값을 확인한다.

               (작은 수 ÷ 첫 계산의 나머지)

               

               이렇게 나눗셈을 반복해 나가다가, 나머지가 0이되는(= 종료) 시점을 기준으로

               전 단계의 나머지 값이 최대공약수가 된다. 

 

               * 예시 : 192와 72의 최대공약수 구하기 (나머지 표기에서 추억이 새록새록)

                 192 ÷ 72 = 2…48

                 72 ÷ 48 = 1…24

                 48 ÷ 24 = 2…0   ← 나머지가 0이 되는 계산 전의 나머지 값(= 24)가 192와 72의 최대공약수.

---

 

 

소인수분해는 코드로 구현해보려니 머리가 복잡해서, 설명도 상대적으로 간단한 '호제법'을 가지고

코드를 작성해보기로 했다. 마침 재귀(recursion) 함수를 공부하고 있기도 해서 활용해보기로 했다.

* 재귀함수 포스팅

 

 

 

⭐️알고리즘

1) 두 가지 숫자가 함수에 주어졌을 때, 인자(큰 수와 작은 수)를 거꾸로 배치해도 바른 계산이 되도록 한다.

2) 큰 수를 작은 수로 나누어서 나머지가 0이 되면, 작은 수가 바로 최대공약수가 된다.
    (쓰고 보니, 호제법의 설명보다 이 쪽이 더 이해가 쉽다.)  

3) 나머지가 남는 결과가 나오면, 작은수와 나머지 값의 나눗셈을 실행한다.
    (나머지 값이 0이 될 때까지. → 재귀 함수 활용)

 

 

⭐️작성 코드(in Javascript)

function getGCD(param1, param2) {
  let maxNum = Math.max(param1, param2); // 큰 수 찾기, 변수에 할당
  let minNum = Math.min(param1, param2); // 작은 수 찾기, 변수에 할당
  let remainder = maxNum%minNum;         // 큰 수 ÷ 작은 수의 나머지를 변수로 할당 
  if (remainder === 0) {                 
    return minNum;       // 나머지가 0이면, 작은 수가 최대공약수로 출력.
  }else{
    return getGCD(minNum, remainder); // 나머지가 0이 아니면, 작은 수와 나머지값으로 재귀함수 실행.
  }
}

console.log(getGCD(72, 192)); // 24
console.log(getGCD(36, 150)); // 6

 

 

함구 구현중에 사용한, Math.max( ) / Math.min( )은 MDN 문서를 보고

가장 큰 수, 가장 작은 수를 찾아 출력하는 기능으로서 활용하였다.

 

 

경우에 따라 if (param1 > param2){ } 와 같은 조건문을 사용해도 좋겠다는 생각이 들었지만,

코드 줄 수가 늘어나고, else 이후에 같은 계산코드를 반복해서 적어야 할 것 같은 생각이 든다.

 

 

먼저 알고리즘을 구상하고 코드를 써내려가는게 순서에 맞지만,

작성을 완료한 후에 처음에 생각했던 기능들에 대한 정의를 수정하면서

더 좋은 코드로 만들어가는 과정도 보람을 느낀다.

 

갈 길이 아직도 멀다.