[프로그래머스/코틀린(Kotlin)] 최대공약수와 최소공배수

n과 m의 최대공약수와 최소공배수를 배열로 리턴 시키기

예시)

 

풀이

• 최대공약수 = (큰 수) / (작은 수)를 반복, (큰 수) 대신 나머지를 대입하다가 한 개의 수가 0이 되는 순간, 나머지의 수
• 최소공배수 = (두 수의 곱) / (최대공약수)
• 유클리드 호제법

 

제출 코드

(코드 해석해 보기)

최대공약수(gcd)는 재귀함수로 구하며, 최소공배수(lcm)는 (두 수의 곱) / (최대공약수)로 구할 수 있다

(재귀함수는 자기 자신을 호출하는 함수,

똑같은 구조의 함수를 반복해서 사용할 필요가 있을 때 사용되며 탈출조건이 있어야 무한루프에 빠지지 않는다)

7) gcd함수를 만들고 (n < m)인 경우에는 n이 0이 아닐 때 gcd(n, m%n)을 이용해서 최대공약수를 구해주고

         그 외(n이 0일 때)는 m을 리턴하도록 한다

7) (return문은 그냥 공식인 듯..? if (n==0) m, else gcd(n,m%n)을 해도 된다 

    그런데, 제한 사항에 두 수다 1 이상이라고 해서 0일 순 없으니까 else에 0을 넣어도 답에는 영향이 없을 것 같아서 넣어봤는데

    오류가 뜬다.. 그래서 그냥 공식인 걸로 받아들였다..)

8) (m>n)인 경우에는 반대로 리턴한다

 

 

 

 

---

 

 

 

 

유클리드 호제법

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다

호제법이란, 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지 과정을 반복하다가 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다

 

예를 들어 a= 54, b = 42이면

• 54%42 = 12
• 42%12 = 8
• 12%8 = 4
• 8%4 = 0, 즉 4가 54와 42의 최대공약수인 것이다

 

 

최소 공배수

최소 공배수는 (두 수의 곱) / (최대공약수)이다 그냥 외우도록 하자