최소공배수와 최대공약수에 관해서

사실 이전에, 최소 공배수와 최대 공약수 풀이가 어려워서 정리를 하고 기계적으로 쓰는 연습을 해본적이 있었다.

이번에는, 생각을 하며, 알아보자. 우선은, 테스트케이스를 만드는 것이 중요하다. 테스트케이스로 나올 수 있는 경우의 수는 3가지이다.

Case1. [6, 12]와 같이 바로 나누어지는 경우

Case2. [6, 8]과 같이 부분으로 나누어지는 경우

Case3. [6,7]과 같이 나누어지는 것이 없는 경우

수학문제 풀드시 푼다면야, array의 순서와 상관없이 풀 수 있겠지만, 지금 풀이 같은경우 어디서 어디로 나누는지가 중요하기 때문에 순서가 중요하다. 예를들면, 6에서 12를 나눌 때와 12에서 6을 나눌 때 결과 값이 다르기 때문이다. 그러기 때문에 두위치를 바꿔주기 위해서 나누어 떨어지지 않으면 위치를 바꿔준다.

const gcd = (a,b) => a%b===0? b : gcd(b, a)

요렇게 만들면, 6, 12 순서가 바뀌더라도 상관이 없다.

1. [12,6]을 넣으면 6이 바로나오고,

2. [6,12]를 넣으면 gcd(12, 6%12)가 실행되어 1번의 결과인  6이 나온다.

Case1은 해결되었다, 하지만 Case2, Case1을 해결하기 위해, a를 넣어야하는 위치에 a%b를 입력한다. 최대 공약수란 원래, 서로 나누어 지는 숫자를 찾는 것이기 때문에 다음과 같이 해둔다면, 서로 나누어떨어지는 숫자를 찾을 수 있다.

const gcd = (a,b) => a%b===0? b : gcd(b, a%b)

Case2

1-1 [6, 8]을 넣으면 [8, 6%8]이 실행된다

1-2 [8, 6]의 결과 값으로 [6, 8%6]이 실행된다

1-3 [6, 2]의 결과 값은 2이다. 

Case3

1-1 [6, 7]을 넣으면 [7, 6%7]이 실행된다

1-2 [7, 6]의 결과 값으로 [6, 1]이 실행된다. 

1-3 결과 값이 1이다.

 

그리고 lcm은 gcd를 이용하여

const lcm = (a,b) => a*b/gcd(a,b)

 

예전보다는, 이해를 하면서 풀 수 있는것 같아서 좋은것 같다. 무의식적으로 암기를 하면서 풀이한 것이 있다면 내가 직접 테스트케이스를 짜서 풀이를 해봐야겠다