[프로그래머스] 최대공약수와 최소공배수

초등학교 때 배운 최대공약수와 최소공배수를 코드로 쓰라니까 엄청 당황스럽네요.

어떻게 쓸지 막막해서... 검색해 봤더니 "유클리드 호제법"이라는 게 있더라고요.

설명을 아무리 읽어봐도 이해가 안되서 유클리드 호제법을 사용 안 하고 그냥 풀었습니다.

(물론 다른사람꺼 베꼈습니다...😓)

https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98GCD-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98LCM-%EA%B5%AC%ED%95%98%EA%B8%B0

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기

 

아마 최대공약수와 최소공배수에 대해 완벽하게 이해했으면 혼자 풀었을 것 같습니다.

쓸데없이 내장함수에 최대공약수와 최소공배수 기능이 있지 않을까의 의문을 품고 찾은 제 잘 못 같아요.😂

 

---

해결방안

function solution(n, m) {
    var answer = [];
    
    // 최대공약수
    let gcd = 1;
    for(let i=2; i<=Math.min(n, m); i++){
        if(n%i===0 && m%i===0) gcd = i
    }
    answer.push(gcd);
    
    // 최소공배수
    let lcm = Math.max(n, m);
    while(true){
        if((lcm % n === 0) && (lcm % m === 0)){
            break;
        }
        lcm++;
    }
    answer.push(lcm);
    
    return answer;
}

해결방안 순서

1. 최대공약수
2. 최소공배수

 

최대공약수

먼저 공약수에 대해 설명하자면

• 공약수 : 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻

 

그래서 최대공약수는

• 최대공약수 : 공약수 중 가장 큰 것

12, 18의 최대공약수를 구하자
12의 약수 : 1, 2, 3, 4, 6, 12
18의 약수 : 1, 2, 3, 6, 9, 18

여기서 12, 18의 공통 약수는 1, 2, 3, 6입니다.
그중 최대공약수는 6입니다.


3, 12의 최대공약수를 구하자
3의 약수 : 1, 3
12의 약수 : 1, 2, 3, 4, 6, 12

여기서 3, 12의 공통 약수는 1, 3입니다.
그 중 최대공약수는 3입니다.


2, 5의 최대공약수를 구하자
2의 약수 : 1, 2
5의 약수 : 1, 5

여기서 2, 5, 의 공통 약수는 1입니다.
그중 최대공약수는 1입니다.

위에 예시를 보면 최대공약수의 특징은

1. 두 수 중에서 작은 값보다는 클 수가 없다.
2. 약수는 1부터 시작한다.

 

최대공약수 코드

// 최대공약수
let gcd = 1;
for(let i=2; i<=Math.min(n, m); i++){
    if(n%i===0 && m%i===0) gcd = i
}
answer.push(gcd);

 

gcd = 1

약수는 1부터 시작하기 때문에 초기 값으로 1을 넣어주었습니다.

 

for(let i=2; i<=Math.min(n, m); i++)

• let i = 2 : gcd=1을 넣어 주었기 때문에 2부터 시작해주었습니다. (두 수에 2부터 나누어 나머지값을 확인하기 위해)
• i<=Math.min(n, m); : 최대공약수 특징 중에서 두 수의 작은 값보다는 클 수 없기 때문에 i는 두 수 중 작은수보다 작거나 같게 했습니다.

 

MDN Web Docs
Math.min() 함수는 주어진 숫자들 중 가장 작은 값을 반환합니다.

문법 : Math.min([value1[, value2[, ...]]])

• value1, value2, ... : 숫자형

// Math.min()함수 예제
var x = 10, y = -20;
var z = Math.min(x, y);

 

if(n%i===0 && m%i===0) gcd = i

약수를 구해야 됨으로 n, m의 약수를 구하기 위해 %를 써주었습니다.

• n%i === 0 : n 나누기 i의 나머지가 0
• m%i === 0 : m 나누기 i의 나머지가 0

이 두 개의 조건이 맞는다면 (&& and연산자 사용) gcd = i을 실행

 

gcd = 1 : 최대공약수의 초기값

테스트 1 (n=3, m=12)
for(let i=2; i<=Math.min(n, m); i++) -> for(let i=2; i<=3; i++) -> (i=2, i=3) 2번 반복
if(n%i===0 && m%i===0) gcd = i -> if(3%i===0 && 12%i===0) gcd = i
i = 2이면
3%2 === 0 -> false
12%2 === 0 -> true
하나만 true임으로 조건 false 다음 반복문(i=3) 실행

i = 2이면
3%3 === 0 -> true
12%3 === 0 -> true
둘다 true임으로 조건 true gcd = i 실행 -> gcd = 3

gcd = 3임으로 최대공약수는 3입니다.


테스트 2 (n=2, m=5)
for(let i=2; i<=Math.min(n, m); i++) -> for(let i=2; i<=2; i++) -> (i=2) 1번 반복
if(n%i===0 && m%i===0) gcd = i -> if(2%i===0 && 5%i===0) gcd = i

i = 2이면
2%2 === 0 -> true
5%2 === 0 -> false
하나만 true임으로 조건 false -> gcd = 1

gcd = 1임으로 최대공약수는 1입니다.

 

최소공배수

먼저 공배수에 대해 설명하자면

• 공배수 : 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻

그래서 최소공배수는

• 최소공배수 : 공배수 중에서 가장 작은 것.

10, 12의 최소공배수를 구하자
10의 배수 : 10, 20, 30, 40, 50, 60, 70, ...
12의 배수 : 12, 24, 36, 48, 60, 72, ...

여기서 10, 12의 공통 배수는 60, 120...입니다.
그중 최소공배수는 60입니다.


3, 12의 최소공배수를 구하자
3의 배수 : 3, 6, 9, 12, 15, 18, 21, 24...
12의 배수 : 12, 24, 36, 48, 60, 72, ...

여기서 3, 12의 공통 배수는 12, 24...입니다.
그중 최소공배수는 12입니다.


2, 5의 최소공배수를 구하자
2의 배수 : 2, 4, 6, 8, 10, 12, 14, 16, 18, 20...
5의 배수 : 5, 10, 15, 20....

여기서 3, 12의 공통 배수는 10, 20...입니다.
그 중 최소공배수는 10입니다.

위에 예시를 보면 최소공배수의 특징은

1. 최소공배수는 두 수가 약수이다.
2. 두 수 중 큰 수보다 같거나 크다.

 

최소공배수 코드

// 최소공배수
let lcm = Math.max(n, m);

while(true){
    if((lcm % n === 0) && (lcm % m === 0)){
        break;
    }
    lcm++;
}
answer.push(lcm);

let lcm = Math.max(n, m);

최소공배수는 두 수 중 큰 것보다 크거나 같기 때문에 최소공배수의 초기값을 두 수 중 큰 수로 했습니다.

 

MDN Web Docs
Math.max() 함수는 입력값으로 받은 0개 이상의 숫자 중 가장 큰 숫자를 반환합니다.

문법

Math.max()
Math.max(값0)
Math.max(값0, 값1)
Math.max(값0, 값1, ... , 값N)

• 값1, 값2, ... : 가장 큰 값을 선택하고 반환할 0개 이상의 숫자입니다.

// Math.max 예제
Math.max(10, 20);   //  20
Math.max(-10, -20); // -10
Math.max(-10, 20);  //  20

 

while(true){}

조건이 true이면 만나면 무조건 반복문을 돌리라는 소리입니다.

 

if((lcm % n === 0) && (lcm % m === 0)){break;}

lcm++;
최소공배수는 두 수가 약수여야 됨으로 최소공배수 % 숫자 === 0을 해주었습니다.

• lcm % n == 0 : 최소공배수가 n으로 나누었을 때 0
• lcm % m == 0 : 최소공배수가 m으로 나누었을 때 0

두 개의 조건이 true이면 lcm++;해주어서 현재 lcm값에 +1해 주기

 

let lcm = Math.max(n, m); : 최소공배수의 초기값
while(true) : 반복문 실행

테스트 1 (n=3, m=12)
let lcm = Math.max(n, m); lcm = 12;

let lcm = 12이면
if((lcm % n === 0) && (lcm % m === 0)) -> if((12 % 3 === 0) && (12 % 12 === 0))
12 % 3 === 0 -> true
12 % 12 === 0 -> true
둘 다 true임으로 break 해주기

let lcm = 12 임으로 최소공배수는 12입니다.


테스트 2 (n=2, m=5)
let lcm = Math.max(n, m); lcm = 5;

let lcm = 5이면
if((lcm % n === 0) && (lcm % m === 0)) -> if((5 % 2 === 0) && (5 % 5 === 0))
5 % 2 === 0 -> false
5 % 5 === 0 -> true
하나만 false임으로 lcm++해주기 -> lcm = 6

let lcm = 6이면
if((lcm % n === 0) && (lcm % m === 0)) -> if((6 % 2 === 0) && (6 % 5 === 0))
6 % 2 === 0 -> false
6 % 5 === 0 -> false
둘 다 false임으로 lcm++해주기 -> lcm = 7
.
.
.
let lcm = 10이면
if((lcm % n === 0) && (lcm % m === 0)) -> if((10 % 2 === 0) && (10 % 5 === 0))
10 % 2 === 0 -> true
10 % 5 === 0 -> true
둘다 true임으로 break 해주기

let lcm = 10 임으로 최소공배수는 10입니다.

---

여기까지 프로그래머스 최대공약수와 최소공배수 해결방안에 대해 설명해보았습니다.