## 알고리즘 결정 체크리스트
- 음의 약수를 포함하는지?
- 정렬이 필요한지?
- 개수만 필요한지, 목록도 필요한지?
## 방법 1. √n 탐색
### 아이디어 : 약수는 쌍으로 존재한다
`n % i === 0` 이면 `i`은 `n`의 약수이고 동시에 n `/ i` 도 `n`의 약수이다. 즉 `(i, n / i)` 처럼 곱해서 n이 되는 쌍으로 묶이는 것. 이 때 두 수 중에 작은 쪽은 항상 `√n` 이하가 될 것이므로 `√n` 까지만 탐색하면 자연스럽게 쌍이 되는 약수를 찾게 되어 전체 약수를 구할 수 있다.
n = k<sup>2</sup>인 경우 약수 쌍 `(k, n / k)`가 `(k, k)`로 겹친다. 그래서 `i * i === n`이 되는 경우를 걸러서 `i`를 한번만 넣어야 한다.
### 구현
```javascript
function getDivisors(n) {
const divisors = [];
for (let i = 1; i * i <= n; i++) {
if (n % i === 0) {
divisors.push(i);
if (n / i !== i) {
divisors.push(n / i);
}
}
}
return divisors;
}
```
- 루프 조건은 `i * i <= n` 이면 충분하다. `Math.sqrt(n)`은 좀 과한 느낌 (개인적느낌,,)
- 매번 `n % i === 0` 을 확인해서 약수 쌍인지를 판단한다.
- 이 구현은 `i`와 `n / i`를 번갈아서 넣기 때문에 정렬된 결과가 아니다. 정렬이 필요한 경우에는
- `sort`로 정렬하거나
- 큰 약수를 따로 저장해서 다 구한 뒤에 반전해서 이어 붙여주는 방법
### 복잡도
- 시간: O(√n)
- 공간: 약수 개수만큼
### 코드
```javascript
function getDivisors(n) {
const divisors = [];
for (let i = 1; i * i <= n; i++) {
if (n % i === 0) {
divisors.push(i);
if (n / i !== i) {
divisors.push(n / i);
}
}
}
return divisors;
}
```
### 노트
- 약수는 항상 쌍으로 존재하기 때문에 √n (i * i <= n) 까지만 탐색하면 된다는 점을 잊지 말기
- n이 완전제곱수일수도 있기 때문에 `i * i === n` 인 경우를 꼭 체크해줘야 한다.
- 문제에서 "정렬된 약수 리스트"가 필요하지 않은 경우라면 리스트 생성 자체가 낭비일수도 있음