Lv_1 : 약수의 합

문제

 

 

내 풀이

class Solution {
    public int solution(int num) {
        int sum = 0;
        // 약수 : 어떤 수를 나누어 떨어지게 하는 수
        
        // 1~절반
        for(int i=1; i<=num/2; i++) {
            if(num%i==0) sum+=i;
        }
        
        // 자기 자신
        sum+=num;
        
        return sum;
    }
}

• 완전 탐색 (Brute-force) 방식 : 모든 가능성을 다 시도해보는 완전 탐색이다. 
• num/2 : 불필요한 탐색의 범위를 줄여, 반복이 줄어들어 효율적이다. (그나마 효율적인 것이지 수가 커지면 비효율적이다.)

 

 

num / 2 예시

// 불필요한 반복을 줄임
1, 2, 3, 4, 6, 12

• 12/2 = 6 → 1~6만 확인하면 된다.
• 7, 8, 9, 10, 11은 12를 나눌 수 없다. → 검사할 필요가 없다.

 

---

 

 

 

# 다른 풀이

어떤 수 n의 약수는 보통 두 수의 곱으로 만들어진다.

예를 들어 `n = 36`일 때:

1 x 36  
2 x 18  
3 x 12  
4 x 9  
6 x 6 ← 여기서부터 대칭

즉, `i`가 약수이면 `n / i` 도 반드시 약수이다.

그래서 `i` 만 감사하고, 그 짝 `n / i`를 같이 더해주면 된다.

이렇게 하면 √n까지만 보면 끝이다.

 

 

class Solution {
    public int solution(int num) {
        int sum = 0;

        for(int i = 1; i <= Math.sqrt(num); i++) {
            if(num % i == 0) {
                int pair = num / i;
                sum += i;

                // i와 pair가 다르면 pair도 더함
                if(i != pair) sum += pair;
            }
        }

        return sum;
    }
}

• 제곱근 탐색 : 어떤 수 n의 약수를 찾을 때, `1 ~ √n` 까지만 탐색하는 방식이다.
• i != pair : 36을 예로 들었을 때, i는 6일 때, pair도 6이된다. 이는 6×6과 같은 상황이다. 중복으로 더해지는 것을 방지하는 것이다.