[알고리즘] 약수들의 합 구하기

문제: 정수 n의 약수들을 찾고 그 약수들의 합을 구하시오

문제 접근

1. 약수란 무엇인가?
   몸에 좋은 물 약수는 정수 n을 나머지 없이 나눌 수 있는 자연수다. 예를 들어, 8의 약수는 1, 2, 4, 8이다.

8 / 1 = 8
8 / 2 = 4
8 / 4 = 2
8 / 8 = 1

해당 문제는 이 수들의 합을 요구한다. 필자는 처음에 문제를 접근할 때, 재귀 함수 또는 For Loop로 1부터 n의 모든 수를 하나 하나 찾는 것으로 접근했다. 코드가 작동은 했으나, 처리 속도 면에선 그닥 효율적이라고 생각되진 않아서, 전지전능한 chatGPT에게 물었더니, 무릎 탁! 치는 답을 알려 주었다.

2. 약수의 특징
   약수의 특징은 바로 정수의 제곱근(Sqrt)을 기준으로 대칭적으로 존재한다는 것이다. 위의 8을 예시로 보면, 8의 제곱근은 대략 2.828이다. 우리는 정수를 다루기에, 소수점을 제외시키면 2가 된다. 2를 기준으로 8의 약수를 나타낼 떄 대칭이 생긴다는 것을 알 수 있다.

8 / 1 = 8
8 / 2 = 4
---------
8 / 4 = 2
8 / 8 = 1

따라서, For Loop의 탐색 영역을 n의 제곱근까지만 찾고, n의 약수를 찾게 되면 그 수를 변수에 더하고, 그 약수의 결과값 또한 약수 이기에 더하여 주면 된다. 정말 기똥 찬다.

function solution(n) {
   let sum = 0;
   const sqrtN = Math.sqrt(n);

   for (let i = 1; i <= sqrtN; i++) {
       if (n % i === 0) {
           sum += i; // i는 n의 약수입니다.
           if (i !== n / i) {
               sum += n / i; // n / i도 n의 약수입니다.
           }
       }
   }

   return sum;
}

// 예시 사용법
console.log(solution(36)); // 출력: 91 (1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 + 36)
console.log(solution(12)); // 출력: 28 (1 + 2 + 3 + 4 + 6 + 12)