약수 구하는 알고리즘에 대해 알아보자.
기본적으로 약수란 인수를 나누어 떨어지게 하는 수를 의미하는데,
약수를 구하는 여러 가지 방법에 대해 하나씩 알아보자.
(아래 예제 코드는 약수들을 구하는 알고리즘이기 때문에 약수의 합을 구하거나 등의 상황에 맞춰 바꿔 사용하면 된다.)
1. 단순하게 모든 수를 나눠서 약수 구하기
const getDivisors = (num) => {
const divisors = [];
for(let i = 1 ; i <= num ; i++){
if(num % i === 0) divisors.push(i);
}
return divisors;
}가장 일반적으로 생각하는 약수 구하는 방법이다.
1부터 주어진 수 까지 반복해가면서 나머지가 0 인 값들을 구해주는 것이다.
하지만 역시 이런 식으로 구현을 한다면 시간 복잡도에 있어 그렇게 좋은 코드는 아니다.
좀 더 다양한 방법에 대해 배워보자.
2. 주어진 수의 절반을 대상으로만 확인하기
const getDivisors = (num) => {
const divisors = [];
for(let i = 1 ; i <= num/2 ; i++){
if(num % i === 0) divisors.push(i);
}
return [...divisors, num];
}
아주 간단한 논리이다. 약수는 본인을 제외하고 n/2 보다 클 수 없기 때문에 절반값까지만 체크를 해주는 것이다.
이렇게만 해도 1번 예제보다 더 좋은 성능을 낼 수 있다.
이제 여기까지 왔으면 다음에 뭐가 나올지 어느 정도 예상이 가능한데,
소수 판별 알고리즘과 마찬가지로 제곱근을 활용할 수 있다.
3. 제곱근(Math.sqrt) 사용하기(★)
const getDivisors = (num) => {
const divisors = [];
for(let i = 1 ; i <= Math.sqrt(num) ; i++){
if(num % i === 0) {
divisors.push(i);
if(num / i != i) divisors.push(num / i);
}
}
// divisors.sort((a, b) => a - b);
return divisors;
}
제곱근을 이용하는 방식은 좀 이해가 필요하다.
num 을 100이라고 가정하자.
Math.sqrt(100) = 10이라는 값이 도출된다.
그러면 어떻게 10까지만 숫자를 체크하는데 나머지 약수 값들을 구할 수 있는 걸까?
코드를 보면 알겠지만 해당 약수를 가지고 입력받은 값을 나누게 될 경우 나오는 결과 값 역시 약수이기 때문이다.
100의 약수를 10 이하의 숫자만 나열하면 [1, 2, 4, 5, 10]이다.
하나씩 나누어 본다면
100 / 1 = 100
100 / 2 = 50
100 / 4 = 25
100 / 5 = 20
100 / 10 = 10
이런 식으로 값이 이루어진다.
그래서 최종적으로 100의 약수는 다음과 같다.
[1, 2, 4, 5, 10, 20, 25, 50, 100]
위 예제 1과 예제 2를 동시에 사용해 검증해보는 것을 추천한다.
예제 3번을 실행하게 되면 코드 로직 상 [1, 100, 2, 50, 4, 25, 5, 20, 10] 이런 식의 배열을 가지게 되는데,
순서대로 뽑아야 한다면 당연히 정렬을 한번 실행해 주어야 한다.
(중간에 if 구문 안에 또다시 if구문을 한 이유는 중복된 값을 제외시켜준 것이다. new Set을 통해 중복을 제거해주어도 좋고 아니면 그냥 예제처럼 제외시켜줘도 좋다.)
댓글