-
#AIL_23.12.17 // Programmers_최대공약수와 최소공배수*****AIL( Algorithm I Learned) 2023. 12. 17. 15:01
## AIL_ 최대공약수와 최소공배수
*** 문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
*** 제한 사항
두 수는 1이상 1000000이하의 자연수입니다.
*** 입출력 예
n m return 3 12 [3, 12] 2 5 [1, 10]
입출력 예 #1_위의 설명과 같습니다.
입출력 예 #2_자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
## solution.JavaScript
1. 문제의 접근 방식
주어진 문제는 두 수의 최대공약수(GCD)와 최소공배수(LCM)를 찾는 것입니다. 주어진 두 수를 활용하여 최대공약수와 최소공배수를 계산하는 다양한 방법이 있습니다. 위에서 소개한 것처럼 주로 유클리드 호제법이나 반복문을 사용하는 방법이 있습니다.
1. 최대공약수(GCD) 계산:
유클리드 호제법을 사용하여 재귀 함수나 반복문으로 최대공약수를 찾습니다.
최대공약수를 찾는 알고리즘은 큰 수를 작은 수로 나눈 나머지를 반복해서 구하는 것입니다.
나머지가 0이 될 때, 나누는 수가 최대공약수가 됩니다.
2. 최소공배수(LCM) 계산:
최소공배수는 주어진 두 수의 곱을 최대공약수로 나누어 구할 수 있습니다.
LCM(a, b) = (a * b) / GCD(a, b) 공식을 활용합니다.
2. 문제풀이
function solution(n, m) { // 최대공약수 계산 function gcd(a, b) { // 두 수 중 작은 수부터 1까지 반복하며 최대공약수 찾기 for (let i = Math.min(a, b); i > 0; i--) { // a와 b가 i로 나누어 떨어지는 경우 i가 최대공약수 if (a % i === 0 && b % i === 0) { return i; } } return 1; // 1은 모든 수의 공약수이므로 최소값으로 설정 } // 최소공배수 계산 function lcm(a, b) { // 두 수 중 큰 수부터 시작하여 계속해서 큰 수를 더해가며 최소공배수 찾기 for (let i = Math.max(a, b); ; i += Math.max(a, b)) { // i가 a와 b로 나누어 떨어지는 경우 i가 최소공배수 if (i % a === 0 && i % b === 0) { return i; } } } // 결과 배열에 최대공약수와 최소공배수 추가 const gcdResult = gcd(n, m); const lcmResult = lcm(n, m); return [gcdResult, lcmResult]; } /* 테스트 1 입력값 〉 3, 12 기댓값 〉 [3, 12] 실행 결과 〉 테스트를 통과하였습니다. 테스트 2 입력값 〉 2, 5 기댓값 〉 [1, 10] 실행 결과 〉 테스트를 통과하였습니다. */
1.주어진 두 수의 최대공약수와 최소공배수를 계산하는 함수를 정의합니다.
function solution(n, m) { ... }
2. 최대공약수를 계산하는 함수입니다. 유클리드 호제법을 사용하여 두 수의 최대공약수를 찾습니다.
function gcd(a, b) { ... }
3. b가 0이 될 때까지 반복합니다. 이 때, a를 b로 나눈 나머지가 새로운 b가 되며, b는 a가 되도록 합니다.
while (b !== 0) { ... }
4. 임시 변수 temp를 사용하여 값을 교환합니다. 이 부분은 유클리드 호제법의 핵심 부분입니다.
const temp = b; b = a % b; a = temp;:
5. return a;: 반복이 끝난 후의 a가 최대공약수입니다.
return a;
6. 최소공배수를 계산하는 함수입니다.
function lcm(a, b) { ... }
7. 최소공배수는 두 수의 곱을 최대공약수로 나눈 값입니다.
return (a * b) / gcd(a, b);:
8. 주어진 두 수의 최대공약수를 계산합니다.
const gcdResult = gcd(n, m);:
9. 주어진 두 수의 최소공배수를 계산합니다.
const lcmResult = lcm(n, m);:
10. 최대공약수와 최소공배수를 포함한 결과 배열을 반환합니다.
return [gcdResult, lcmResult];:
3. 다른사람의 문제풀이 및 접근방식 분석 *****
function solution(a, b) { var r; for(var ab= a*b;r = a % b;a = b, b = r){} return [b, ab/b]; } /* 테스트 1 입력값 〉 3, 12 기댓값 〉 [3, 12] 실행 결과 〉 테스트를 통과하였습니다. 테스트 2 입력값 〉 2, 5 기댓값 〉 [1, 10] 실행 결과 〉 테스트를 통과하였습니다. */
이 함수는 주어진 두 수 a와 b의 최대공약수와 최소공배수를 계산하는 방법을 사용하고 있습니다. 코드의 핵심은 반복문을 사용하여 유클리드 호제법을 통해 최대공약수를 찾고, 이를 활용하여 최소공배수를 계산하는 것입니다.
1. var r;: 임시 변수 r을 선언합니다. 이 변수는 최대공약수를 계산하는 과정에서 사용됩니다.
2. for(var ab = a * b; r = a % b; a = b, b = r) {}: 유클리드 호제법을 사용한 반복문입니다. 여기서 ab는 입력된 두 수 a와 b의 곱입니다.
- r = a % b: 현재의 a를 b로 나눈 나머지를 r에 대입합니다.
- for 루프의 조건은 r의 값이 0이 아닌 동안 반복됩니다. 나머지가 0이 되면 반복이 종료됩니다.
- a = b, b = r: 각 반복에서 a를 b로, b를 r로 갱신합니다.
이렇게 반복문이 종료되면 b에는 최대공약수가 저장되어 있습니다. 그리고 ab / b를 통해 최소공배수를 계산하고, 최대공약수와 최소공배수를 담은 배열을 반환합니다.
'AIL( Algorithm I Learned)' 카테고리의 다른 글
#AIL_23.12.21 // Programmers_호텔 대실********** (0) 2023.12.21 #AIL_23.12.19 // Programmers_이상한 문자 만들기** (0) 2023.12.19 #AIL_23.12.15 // Programmers_직사각형 별찍기 (0) 2023.12.15 #AIL_23.12.13 // Programmers_행렬의 덧셈*** (0) 2023.12.13 #AIL_23.12.12 // Programmers_문자열 다루기 기본 (0) 2023.12.12