AIL( Algorithm I Learned)

#AIL_23.12.17 // Programmers_최대공약수와 최소공배수*****

k0z 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를 통해 최소공배수를 계산하고, 최대공약수와 최소공배수를 담은 배열을 반환합니다.

 

저작자표시 비영리 변경금지 (새창열림)