개발의 흔적

알고리즘 테스트# 5. 최대공약수와 최소공배수 본문

코딩테스트 연습

알고리즘 테스트# 5. 최대공약수와 최소공배수

남들에게 도움을 주는 백엔드 개발자가 되자 2020. 7. 20. 11:40

안녕하세요.

 

프로그래머스에 있는 "최대공약수와 최소공배수" 알고리즘 문제를 풀어보겠습니다.

 

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

 

출력 : 

 

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

 

코드 :

 

 

 

* 문제 해설 *

 

최대공약수 : 두가지의 값중 0으로 나누어떨어지는 공통적인 값중 가장 큰값

최소공배수 : 두가지의 값을 곱한값중 공통된 곱한값

 

 

* 코드 해설 *

최대공약수를 구하기 위해 바깥쪽 for문에 가장작은 값을 반복 시킨다.

반복을 시키는 도중 0으로 나누어 떨어지고 가장 큰값을 gcd값에 넣어 최대공약수를 구한다.

최소공배수를 구하기위해 두값이 같은 값이 될때까지 while문을 통하여 비교한다.

만약에 둘중 값이 다를경우 가장 작은값의 반복 횟수를 늘린다.

그후 계속 반복하다보면 같은 값이 나올때 빠져나온 후 n * i 를 리턴하여 최소 공배수를 구한다.

 

좋은 코드가 있을시 말씀해주세요.

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

Comments