[프로그래머스]최대공약수와 최소공배수(유클리드 호제법 & 재귀함수)

✔최대 공약수와 최소 공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

입출력 예

nmreturn

3	12	[3,12]
2	5	[1,10]

풀이

최대공약수와 최소공배수를 구하는 문제이다. 둘의 공식은 아래와 같다.

• 최대공약수 : 유클리드 호제법
• 최소공배수 : a * b / 최대공약수

---

유클리드 호제법이란?
쉽게 설명하자면,
a > b 일 때,
a % b = r (나머지)
b % r = r2
r % r2 = r3
..
..
나머지가 0이 될 때 까지 반복한다.
이 때, 나머지를 0으로 만든 나눈 수가 최대공약수가 된다.

https://jaypedia.tistory.com/43

https://www.youtube.com/watch?v=aPYE0anPZqI 

<My solution>

👉

 최대 공약수 = G

 최소 공배수 = L 을 선언해주고 

최대 값과 최소값을 구하기 위해 num을 선언해주고 for문을 사용해 n(최댓값) % i 의 나머지가 0 이 거나 m(최솟값) % i 의 나머지가 0이되면 그 i의 값을 G에 할당해주고

n*m/G 공식을 사용해 최소 공배수를 구해주었다.

<Other solution>

👉최대 공약수는 유클리드 호제법을 사용해 주었고

      최소 공배수는  a*b / 최대공약수 를 해주었다.

나머지가 0이 될기 전까지 나누는수 / 나머지가 재귀적으로 실행된다.

=>처음에 b의 위치에 있던 값ㅇ a 로 이동함

나머지가 0 이 되면 나눈 수(a)를 반환하고 이것이 최대 공약수가 되고

나머지가 0 이 아니면 재귀로 함수를 실행한다 .