48일차 TIL

오늘은 약수의 개수와 덧셈이라는 프로그래밍 문제를 풀었다. 문제는 주어진 두 정수 left와 right 사이의 숫자 중, 약수의 개수가 짝수면 더하고 홀수면 빼는 방식으로 결과를 구하는 것이다. 최종적으로 함수는 이렇게 동작한다:

function solution(left, right) {
    let answer = 0;

    for (let i = left; i <= right; i++) {
        let divisorCount = 0;

        for (let j = 1; j <= Math.sqrt(i); j++) {
            if (i % j === 0) {
                divisorCount += 1;
                if (j !== i / j) {
                    divisorCount += 1;
                }
            }
        }

        if (divisorCount % 2 === 0) {
            answer += i;
        } else {
            answer -= i;
        }
    }

    return answer;
}

---

왜 이렇게 접근했을까? (Why?)

1. 약수의 개수를 어떻게 구할까?
   • 모든 숫자를 1부터 n까지 순회하면 비효율적이다. 그래서 Math.sqrt(i)까지만 반복해서 짝이 되는 약수를 동시에 찾는 방식을 선택했다.
   • √n 범위까지만 순회하면 시간 복잡도가 줄어들기 때문에 더 효율적이다.
2. 왜 약수의 개수를 홀수/짝수로 구분했을까?
   • 문제에서 약수의 개수가 짝수면 더하고, 홀수면 빼라는 조건이 있었다.
   • 여기서 약수의 개수가 홀수가 되는 경우는 완전제곱수일 때만 발생한다는 점을 고려했다.
3. 왜 짝수면 더하고 홀수면 뺀 결과를 최종적으로 반환했을까?
   • 문제 요구사항을 정확히 구현하기 위해 각각의 숫자에 대한 계산을 누적해야 했다. 따라서 answer 변수를 사용해 최종 값을 저장하도록 했다.

     ---

     새로 배운 점
     1. 효율적인 약수 구하기
        • 약수를 찾을 때 √n까지만 계산하고, 짝을 통해 남은 약수를 동시에 찾는 방법을 배웠다.
     2. 수학적 성질 활용
        • 약수의 개수가 홀수인 경우는 완전제곱수에서만 발생한다는 사실을 깨달았다. 이 성질을 더 잘 활용하면 코드가 더 간결해질 가능성이 있다.

     ---

     개선할 수 있는 점
     • 완전제곱수를 활용한 코드 단축
       • 완전제곱수인지 확인하는 방식을 사용하면 약수의 개수를 직접 구하지 않고도 결과를 계산할 수 있다. 개선된 버전은 다음과 같다:

function solution(left, right) {
    let answer = 0;

    for (let i = left; i <= right; i++) {
        if (Math.sqrt(i) % 1 === 0) {
            answer -= i; // 완전제곱수면 빼기
        } else {
            answer += i; // 나머지는 더하기
        }
    }

    return answer;
}

• 이 방식으로 약수 개수를 계산하지 않고도 더 효율적으로 결과를 구할 수 있다.

---

오늘의 결론

이번 문제를 풀면서 약수 계산의 효율적인 방법과 수학적 성질을 활용하는 방법을 배웠다. 앞으로 비슷한 문제를 풀 때 더 빠르고 간결하게 접근할 수 있을 것 같다!

 

오늘 하루도 고생했고 내일 하루도 힘내보자!