[내배캠 TIL 260324] C++ 약수 개수 구하기 (완전탐색 vs √N 최적화)

1. 문제 접근

어떤 수 i의 약수 개수를 구해야 하는 문제였다.
가장 먼저 떠올릴 수 있는 방법은 완전탐색이다.

---

2. 기존 풀이 (완전탐색)

방법

• 1 ~ i까지 모든 수를 확인
• i % j == 0이면 약수로 판단

코드 형태

for(int j = 1; j <= i; ++j)
{
    if(i % j == 0) count++;
}

문제점

• 시간복잡도: O(N²)
• number가 커질수록 매우 비효율적
• 불필요하게 많은 연산 수행

---

3. 개선 아이디어 (약수의 성질)

약수는 항상 쌍(pair)으로 존재한다.

예:

• i = 12
  • (1, 12)
  • (2, 6)
  • (3, 4)

즉,

• 어떤 수 j가 약수라면
• i / j도 반드시 약수

---

4. 핵심 최적화

√i까지만 탐색하면 모든 약수를 구할 수 있다.

이유

• √i를 기준으로 약수가 대칭 구조를 가짐
• √i 이후는 이미 이전에서 처리된 값

---

5. 주의할 점 (중복 처리)

• j * j == i인 경우 (완전제곱수)
• 같은 값이므로 1번만 카운트

---

6. 개선된 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int number, int limit, int power) {
    int answer = 0;
    
    for(int i = 1 ; i <= number ; ++i)
    {
        int divisorCount = 0;
        int root = sqrt(i);
        
        for(int j = 1; j <= root ; ++j)
        {
            if(i % j == 0)
            {
                if(j * j == i) divisorCount++;
                else divisorCount += 2;
            }
        }

        if (divisorCount > limit) answer += power;
        else answer += divisorCount;
    }
    
    return answer;
}

---

7. 시간복잡도 비교

방식시간복잡도

완전탐색	O(N²)
√N 최적화	O(N√N)

큰 입력에서 성능 차이가 크게 발생한다.

---

8. 배운 점

• 단순 반복문도 수학적 성질을 활용하면 크게 최적화할 수 있다
• 약수 문제는 항상 √N 최적화를 먼저 떠올리는 것이 중요하다
• 완전제곱수에서의 중복 처리 로직이 핵심이다

---

9. 추가로 생각해볼 점

• 약수 개수를 미리 구하는 방식 (에라토스테네스 응용)
• 시간복잡도를 O(N log N)까지 줄일 수 있음

---

이번 문제는 단순 구현에서 시작해 수학적 최적화로 개선하는 흐름을 연습하기에 좋은 문제였다.