-
[프로그래머스] 최대공약수와 최소공배수Algorithm 2021. 3. 10. 19:15
programmers.co.kr/learn/courses/30/lessons/12940
코딩테스트 연습 - 최대공약수와 최소공배수
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의
programmers.co.kr
더보기문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
입출력 예
n m return 3 12 [3, 12] 2 5 [1, 10] 풀이
최대공약수: 둘 이상의 자연수의 약수 중 가장 큰 수
유클리드 호제법: 두 수의 최대공약수를 구하는 알고리즘
- a를 b로 나눔. 만약 나누어 떨어진다면 b가 최대공약수이다.(a > b)
- 나누어 떨어지지 않는다면 b를 a % b(a를 b로 나눈 나머지)로 나눔
- 나누어 떨어진다면 a % b가 최대공약수, 나누어 떨어지지 않는다면 2~3 반복
최소공배수: 둘 이상의 자연수의 배수 중 공통적으로 겹치는 최초의 배수
- 두 수의 곱하기 / 두 수의 최대공약수
function solution(n, m) { // 최대공약수 function greatestCommonDivisor (a, b) { if(b === 0) return a; return greatestCommonDivisor(b, a % b) } // 최소공배수 function leastCommonMultiple (a, b) { return (a * b) / greatestCommonDivisor(n, m) } return [greatestCommonDivisor(n, m), leastCommonMultiple(n, m)]; }
'Algorithm' 카테고리의 다른 글
[Codewars] Which are in? (0) 2021.03.15 [프로그래머스] 예산 (0) 2021.03.11 [프로그래머스] 2016년 (0) 2021.03.10 [프로그래머스] 자연수 뒤집어 배열로 만들기 (0) 2021.03.09 [프로그래머스] 시저 암호 (0) 2021.03.09