알고리즘 문제 정리 (최대공약수와 최소공배수)

최대공약수와 최소공배수

 

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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]을 리턴해야 합니다.

 

- 내가 푼 풀이

function solution(n, m) {
    var answer = [];
    
    let GCD = 1;
    for(let i=1; i <= Math.min(n, m); i++){
        if(n%i ===0 && m%i===0){
            GCD = i
        }
    }
    const LCM = n * m / GCD
    
    
    return [GCD, LCM];
}

 

- 함수 내에서 반환할 결과를 저장할 빈 배열을 선언
- GCD = 1 - 두 숫자 `n`과 `m`의 최대공약수(GCD)를 저장할 변수 선언
- for 반복문을 사용하여 1부터 두 숫자 `n`과 `m` 중 작은 값까지 순회(최대공약수는 두 숫자 중 작은 숫자까지의 범위에서 결정되기 때문)
- if 조건문을 통해 현재 순회 중인 숫자 `i`가 두 숫자 `n`과 `m`의 공통 약수인지 확인(`n`과 `m`을 `i`로 나눈 나머지가 모두 0이라면 `i`는 두 숫자의 공통 약수)
- 현재 순회 중인 숫자 `i`가 두 숫자 `n`과 `m`의 공통 약수이므로, 최대공약수 `GCD`를 `i`로 업데이트
- `const LCM = n * m / GCD`: 두 숫자 `n`과 `m`의 최소공배수(LCM)를 계산 (최소공배수는 두 숫자의 곱을 최대공약수로 나눈 값으로 구할 수 있음)

 

 

- 다른 풀이

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

 

 

유클리드 호제법(Euclidean Algorithm)을 이용한 풀이이다. 

유클리드 호제법
최대공약수를 구하는 알고리즘 중 하나로, 두 수의 최대공약수를 빠르게 구하는 방법

유클리드 호제법은 두 수 a와 b의 최대공약수를 구할 때, a를 b로 나눈 나머지 r을 구하고, b를 r로 대체하는 과정을 반복하여 최대공약수를 찾습니다. 이 과정에서 나머지가 0이 되는 순간에 그 때의 b가 최대공약수가 됩니다.

 

- 와 b의 곱을 ab에 저장 - 최소공배수를 계산할 때 사용

- a를 b로 나눈 나머지를 계산하여 r에 저장 - 이후 b로 r을 업데이트

- a를 b로, b를 r로 업데이트 - 이러한 과정을 나머지가 0이 될 때까지 반복

- 나머지가 0이 되면 b에는 최대공약수가, a * b / b는 최소공배수가 저장

 

 

어려운 문제는 아닌데 기억 저편으로 사라져버린 수학적 지식때문에 헤맨 문제이다. 종종 알고리즘 문제를 풀다보면 수학 공식을 잘 알 경우 쉽게 풀 수 있는 경우가 있는데(위의 유클리드호제법..) 그럴때마다 수학 공부를 해야하나 고민 된다. 그럴 시간은 없으니 복습하며 푼 문제의 공식만큼은 잘 기억해두자. 분명 실제로 개발할 때도 용이할 것이다.