약수란 어떠한 수를 나눴을때 나머지가 0이되는 수들의 집합이다
모두 반복해서 찾기
function solution(n) {
const divisors = [];
for (let i = 1; i <= n; i++) {
if (n % i === 0) divisors.push(i);
}
return divisors;
}
1부터 n까지 모두 순회해야하기때문에 시간복잡도가 n임
절반까지 찾기
function solution(n) {
const divisors = [];
for (let i = 1; i <= n / 2; i++) {
if (n % i === 0) divisors.push(i);
}
return [...divisors, n];
}
예를들어 100의 약수는
1, 2, 4, 5, 10, 20, 25, 50, 100이다
본인인 100말고 제일큰 약수는 본인/2을 초과할 수 없으므로 반까지만 순회해도 된다
처음 방식 속도의 2배이다
제곱근 사용하기
function solution(n) {
const divisors = [];
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
divisors.push(i);
if (n / i != i) divisors.push(n / i);
}
}
divisors.sort((a, b) => a - b);
return divisors;
}
약수의 특성상 약수를 나눠서 나온값도 약수이다
1, 100
2, 50
4, 25
5, 20
10, 10
번외
제곱근이 정수면 약수의 개수가 홀수이며
정수가 아니면 약수의 개수가 짝수다
'코딩 테스트 > 알고리즘 공부' 카테고리의 다른 글
피보나치 수열 (0) | 2022.09.09 |
---|---|
수학적 지식 모음 (0) | 2022.09.08 |
최소공배수(lcm) (0) | 2022.09.05 |
병합 정렬 (Merge Sort) (0) | 2022.06.17 |
셸 정렬 (Shell Sort) (0) | 2022.06.16 |