[JS] 최대공약수와 최소공배수

[풀이]

function solution(n, m) {
  const gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));
  const lcm = (a, b) => (a * b) / gcd(a, b);

  return [gcd(n, m), lcm(n, m)];
}

1. 이 문제는 유클리드 호제법으로 풀어야한다. (나는 중첩 함수를 이용해 풀었다.)

 

[유클리드 호제법]

유클리드 호제법은 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘이다.

- 임의의 두 자연수 a, b가 있을 때 (둘 중 큰 값이 a라고 가정)

- a 를 b 로 나눈 나머지를 r 이라고 하면 (a % b = r)

- r이 0일 때, b가 최대공약수(GCD)이다.

- 만약 n이 0이 아니라면 a에 b를 넣고 n을 b에 대입해 다시 반복하면 된다.

예) n = 3,  m = 12 일 때

a	b	r
3	12	3
12	3	0

a % b 에서 a < b 일 때 a를 반환한다. 

r = 0 일 때 b가 최대공약수이므로 이 예제에서 최대공약수는 3이 된다.

 

최소공배수 구하기

최대공약수를 응용해서 구할 수 있다.

두 수의 최대공약수를 gcd 라고 했을 때 최소공배수는 두 수를 곱한 값 / gcd 이다.

결론 : n * m / gcd

 

 

[코드 리뷰]

재귀를 이용한 최대공약수 도출 방법.

function solution(n, m) {
  return [greatestCommonDivisor(n, m), leastCommonMultiple(n, m)];
}
//최대 공약수
function greatestCommonDivisor(num1, num2) {
  const remainder = num1 % num2;
  return num2 === 0 ? num1 : greatestCommonDivisor(num2, remainder);
}
//최소 공배수
function leastCommonMultiple(num1, num2) {
  return (num1 * num2) / greatestCommonDivisor(num1, num2);
}

재귀 함수를 이용해야 하는 경우는 보통 브루트포스(완전 탐색), DFS, 백트랙킹, 분할 정복 등 대표적으로 사용된다.

대표적인 예로 피보나치 수열이 있다. (추후에 많이 활용 됨)

피보나치 수열
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

function fibonacci(n) {
  if ( n <= 1 ) {
    return n;
  }
   
  return fibonacci(n-1) + fibonacci(n-2);
}

 

+ 재귀 함수를 쓰는 이유

1. 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때 사용한다. (가독성)

2. 변수 사용을 줄여준다.

 

이 때, 변수 사용을 줄여준다는 것은 변수가 잡는 메모리에 대한 이야기가 아니라

mutable state (변경 가능한 상태)를 제거해 프로그램 오류 발생 가능성을 낮춰준다!

하지만, 단점도 크다. 

재귀 함수를 쓰지 않는 이유는 메모리를 많이 차지하고 성능이 반복문에 비해 느리다.

함수를 호출 할 때 함수의 매개변수, 지역변수, 리턴값, 함수 종료 후 돌아가는 위치가 스택 메모리에 저장된다.

재귀 함수를 쓰면 함수를 반복적으로 호출해 스택 메모리가 커지고 호출 횟수가 많아지면 스택오버플로우가 발생할 수 있다.

또한 스택 프레임을 구성하고 해제하는 과정에서 반복문보다 오버헤드가 들어 성능이 느려진다. 

 

꼬리 재귀는 기존 재귀의 위와 같은 문제점을 해결 할 수 있다. 꼬리 재귀의 장점을 얻으려면,

1. 프로그래머가 재귀함수를 꼬리 재귀 방식으로 개발한다.

2. 컴파일러가 꼬리 재귀 최적화를 지원해야 한다. (컴파일러가 지원하지 않으면 개발자가 꼬리 재귀 방식으로 개발해도 이점 얻을 수 없음)

 

코드로 보면 다음과 같은 형태를 가진다.

int Recursive(int n) 
{
 if(n==1) return 1;
 return n + Recursive(n-1);
}
int Tail_Recursive(int n, int acc)
{
 if(n==1) return acc;
 return Tail_Recursive(n-1, n + acc );
}

일반 재귀는 함수 마지막 return에 연산이 필요하다. (n + Recursive(n-1))

꼬리 재귀는 return에 연산이 필요없다. 매개변수로 필요한 연산을 전달한다.

이때 컴파일러가 꼬리 재귀를 최적화 할 수 있으면 최적화 과정에서 꼬리 재귀를 반복문으로 변경한다.

따라서, 기존 재귀의 문제인 메모리와 성능 문제가 제거된다.

 

[출처]

https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0

재귀함수를 쓰는 이유

https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98GCD-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98LCM-%EA%B5%AC%ED%95%98%EA%B8%B0

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기

https://blockdmask.tistory.com/53

[유클리드 알고리즘] GCD 최대공약수 (반복문, 재귀)