- [JS] 자바스크립트 약수 구하기 (Math.sqrt로 시간 복잡도 줄이기)2024년 08월 02일
- 주사위 clice
- 작성자
- 2024.08.02.오후02:43
반응형코테 문제를 풀다 보면 인자에 대해 약수를 구해야 하는 경우가 자주 나온다
그때마다 약수 구하는 함수를 새로 짰는데, 계속 반복해서 같은 코드를 관리하다 보니 너무 귀찮아져서 블로그에 기록해두고 필요할 때 마다 복사해서 사용하려고 한다 😊
일반적인 코드-1부터 n까지 나머지가 0인 값을 더하기
const findDivisors = (n) => { var answer = [1]; //1은 모든 수의 약수니까 약수 배열을 1 포함해 만든다 for(let i = 2; i <= n; i++){ //1은 했으니까 2부터 고려한다. 2부터 본인까지 차례로 검사한다 if(n % i === 0) answer.push(i); //나눠진다면(나머지가 없다면, 나머지가 0이라면) 약수배열에 추가한다 } return answer; }
사람의 사고 방식으로 작성된 코드이다
하지만 1부터 n까지 모든 숫자를 검사하기 때문에 시간 복잡도가 O(n)이라 비효율적이다.
더 효율적인 코드- 1부터 √n까지만 검사하기
const findDivisors = (n) => { let answer = [0]; for (let i = 1; i <= Math.sqrt(n); i++) { if (n % i === 0) { answer.push(i); if (i !== n / i) answer.push(n / i); } } return answer; }
약간 생각만 하면 시간 복잡도를 O(√n)으로 줄일 수 있다.
약수는 대칭성을 가지기 때문에 n의 제곱근까지만 검사하면 된다!예를 들어 16의 경우, 1 로 나눴을때 나머지가 0이니까 약수인데, 이때 몫인 16도 같이 배열에 넣는다
그 다음 2 를 검사하고 통과했을때 2와 8을 배열에 함께 넣는다
그리고 3은 안 되니까 패스하고
마지막으로 루트 16의 값인 4를 검사하면 된다!
-> 그러면 16의 약수 1,2,4,8,16을 4번(√n)만에구할 수 있다
이 코드는 프로그래머스 12928 120897 에서 쓰일 수 있다 (계속 추가 예정)
Ⓒ clice lee
clice의 개발일지 입니다
반응형'프론트 > Javascript Typescript' 카테고리의 다른 글
[JS로 코테 정복하기] 자주 나오는 함수 정리 + 관련 프로그래머스 문제들 (0) 2024.06.06 [JS] 머쓱이보다 키 큰 사람-프로그래머스 120585 filter함수 사용법 (1) 2024.05.24 [JS]배열의 평균값 -프로그래머스120811 sort 함수의 동작 원리에 대해 (0) 2024.05.21 [JS] 배열인지 아닌지 판단하는 메서드 Array.isArray() (1) 2024.05.03 [Javascript] 프론트 개발자라면 알아야 할 호이스팅의 핵심 개념(호스팅 아니고 Hoisting) (1) 2024.01.23 다음글이전글이전 글이 없습니다.댓글
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)