최대 공약수를 구할 때 유클리드 호제법을 사용할 수 있다
유클리드 호제법 출처
https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95
유클리드 호제법
💡 유클리드 호제법을 이해하기 위해서는 MOD연산에 대해 알고 있어야 한다.
MOD연산이란?
두 값을 나눈 나머지를 구하는 연산!
-
먼저, 큰 수를 작은 수로 나눈 나머지를 구한다. 즉, MOD 연산을 한다.
1112 mod 695 = 417 -
그 다음, 나눴던 수와 나머지로 또 MOD 연산을 한다.
695 mod 417 = 278 -
이 과정을 계속 반복한다.
417 mod 278 = 139
278 mod 139 = 0 -
나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수가 된다.
=> 간단하게 말하면, 유클리드 호제법은 MOD연산을 반복하면 된다!
유클리드 호제법 원리
어떻게 유클리드 호제법으로 최대공약수(GCD)를 구할 수 있을까?
1112와 695가 최대공약수 N의 배수라는 것은 알고 있다.
위에서 한 대로, 1112와 695를 반복해서 MOD 연산한다.
1)큰 수를 작은 수로 나눴을 때 나머지로 나누는 수(작은 수)를 나눈다
2)1)의 나머지로 큰수의 나머지를 나눈다
//이때 나누는 수와 큰 수 모두 N의 배수이므로
// NMax % NMin = Nsth 나머지도 N의 배수다
//그러므로 작은 수를 (큰 수%작은 수)로
마찬가지로 NMin % N*sth으로 나누면 나머지도 N의 배수다
나누어 떨어지면 그게 최대공약수 N
이 그림을 통해 연산 중에 나온 나머지
417, 278, 139도 모두 N의 배수인 수라는 것과 같은 최대공약수를 가진다는 것을 알 수 있다.
278은 139로 나누어지므로 나머지가 0이 된다.
이때, 최대공약수 N이 139라는 것을 알 수 있다.
문제
오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 M개와 누드 빼빼로 N개를 구매하여 아침 일찍 출근길에 나섰습니다.
팀장은 자신보다 먼저 출근해 있는 직원들에게 구매한 빼빼로를 전부 나누어 주려고 합니다.
단, 서로 질투하는 경우를 만들지 않기 위해 모든 직원들에게 공평하게 빼빼로를 나누어 주려고 합니다.
직원들은 각각의 빼빼로를 똑같은 개수만큼 받아야 합니다. 빼빼로를 쪼개서 줄 수는 없습니다.
하지만 회사에 도착하기 전이라 몇 명의 직원들이 있는지 모르는 상황입니다.
팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.
출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.
출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.
출근한 직원이 3명이라면 빼빼로를 남기지 않고 공평하게 주는 방법은 없습니다.
출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각 줄 수 있습니다.
팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다.
여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.
입력
인자 1: M
Number 타입의 양의 정수 (1 ≤ M ≤ 1,000,000,000)
인자 2: N
Number 타입의 양의 정수 (1 ≤ N ≤ 1,000,000,000)
출력
2차원 배열 output을 리턴해야 합니다.
output[i]은 다음과 같은 순서를 가진 길이 3의 배열입니다.
[빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]
output은 output[i][0], 즉 '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬합니다.
입출력 예시
let M = 4;
let N = 8;
let output = divideChocolateStick(M, N);
console.log(output);
// [[1, 4, 8], [2, 2, 4], [4, 1, 2]]
내 풀이
문제 : 시간 초과
function divideChocolateStick(M, N) {
// TODO: 여기에 코드를 작성합니다.
// 아몬드 : M, 누드 : N
// 각각 same
//M과 N의 최대공약수 : 공통 약수가 있을 때마다 배열로 만들어서 앞에 넣는다
//for문 돌리고 i를 2부터, i로 나눈 나머지가 M,N 둘다 0이면 [0]에, [1]: M/i, [2]: N/i
let min = Math.min(M, N);
let result=[[1, M, N]];//직원이 1명일 때
for(let i=2; i<=min; i++){
//작은 수가 최대공약수일 수도 있어서 min까지 해야한다
//내 풀이 : 시간 초과
//이유 : for문을 Math.sqrt 사용한 제곱근까지만 사용하도록 함 (시간 절반)
//=> left로 for문 도는 동시에 right 구하는 것
if((M % i===0) && (N % i===0)){ //&&쓰려면 양 옆 조건에 ()써야
let m = M/i;
let n = N/i;
result.push([i, m, n]);
//..arr로 쓰니까 시간 초과(이게 그렇게 큰 차이인가?)
}
}
return result;
}
레퍼런스
// 최대 공약수(유클리드 호제법: Euclidean algorithm)
function gcd(m, n) {
if (m % n === 0) return n;
return gcd(n, m % n);
// m,n은 최대공약수의 배수이기 때문에 나머지도 배수
// 나머지로 나누어 떨어질 때까지 한다 : 이때 n이 최대공약수
}
function divideChocolateStick(M, N) {
const result = [];
// 최대공약수를 구한다.
// M, N의 순서는 상관없다.
const GCD = gcd(M, N);
let temp = 0; //
// 약수는 대칭적이므로 제곱근까지만 반복해도 된다.
// 예) 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다.
// 제곱근을 기준으로 양쪽의 값 하나씩 곱했을 때 36이 되기 때문에
// 제곱근 보다 큰 약수는 제곱근보다 작은 약수에서 구할 수 있다.
const sqrt = Math.floor(Math.sqrt(GCD));
for (let left = 1; left <= sqrt; left++) {
if (GCD % left === 0) {
// 최대공약수의 약수인 경우 중 제곱근 보다 작은 약수의 경우
result.push([left, M / left, N / left]);
if (left * left < GCD) {
// 제곱근보다 작은 경우
right = GCD / left;
// 최대 공약수를 제곱근이 아닌 수로 나누면
//제곱근 보다 큰 약수를 구할 수 있다.
result.push([right, M / right, N / right]);
}
}
}
// '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬
result.sort((op1, op2) => op1[0] - op2[0]);
return result;
}