🔙뒤로가기

기본 알고리즘 O(n)

public int solution(int number){
		int count = 0;
		for(int i = 1; i <= number; i++){
				if(number % i == 0){
						count++;
				}
		}
		return count;
}

해설

• 이 알고리즘은 number의 모든 약수를 찾는 알고리즘이다.
• 1부터 number까지의 모든 정수 i에 대해, number를 i로 나누었을 때 나머지가 0이면, 즉 number가 i로 완전히 나누어 떨어지면, i는 number의 약수이다.
• 약수를 찾을 때마다 count를 1씩 증가시키므로, 반복문이 종료될 때 count는 number의 약수의 개수와 같다.
• 이 알고리즘의 시간복잡도는 **O(n)**이다. 왜냐하면 최악의 경우 number까지의 모든 정수에 대해 나눗셈을 수행해야 하기 때문이다.

더 나은 방법 O(√n)

public int solution(int number) {
    int count = 0;
    for(int i = 1; i * i <= number; i++){
        if(number % i == 0){
            if (i * i == number)
                count++;
            else
                count += 2;
        }
    }
    return count;
}

해설

• 이 알고리즘은 number의 제곱근 만큼의 탐색 횟수를 갖는 알고리즘이다.
• 모든 약수는 쌍을 이룬다. 가령 36이라는 수가 주어졌을 때 약수는 다음과 같다.
  • $1 * 36 = 36$→ 1과 36 모두 약수 ⇒ 총 2개
  • $2 * 18 = 36$ → 2와 18 모두 약수 ⇒ 총 4개
  • $3 * 12 = 36$ → 3과 12 모두 약수 ⇒ 총 6개
  • $4 * 9 = 36$ → 4와 9 모두 약수 ⇒ 총 8개
  • $6 * 6 = 36$ → 6은 약수 ⇒ 총 9개
• 조건식을 보면 i * i ≤ number 이다. 따라서 탐색의 횟수는 제곱근까지이므로 오버헤드를 줄일 수 있다. 만약 number가 소수일 경우에도 유효하다.
  • 예를 들어 number가 7일 경우, i = 1일때 쌍을 구해 count += 2로 약수의 수를 구하고, i = 3일때 3 * 3 > number가 되므로 반복문은 종료된다.
  • 소수의 경우에도 이 알고리즘은 정확하게 약수의 개수를 찾아낸다. 소수는 정의상 1과 자기 자신 외에는 약수가 없는 수이다.
  • number가 7인 경우를 가정해보자. 7은 소수이다.
    1. i = 1일 때: 7 % 1 == 0이므로 count를 2 증가시킨다. (1과 7이 약수이다.)
    2. i = 2일 때: 7 % 2 != 0이므로 count를 증가시키지 않는다.
    3. i = 3일 때: 이 시점에서 i * i (9)가 이미 7보다 크므로 루프를 종료한다.
  • 루프가 종료된 후 count는 2이다. 이는 정확하게 7의 약수 개수(1과 7)와 일치한다. 이 알고리즘은 number가 소수인 경우에도 올바르게 작동하며, 제곱근이 정수가 아닌 경우에도 정확한 결과를 반환한다.
• 결론적으로, 향상된 알고리즘은 기존 알고리즘보다 훨씬 적은 연산을 수행하여 효율성이 높다. 특히, number가 매우 큰 경우에는 연산 수가 기하급수적으로 줄어들어 성능 향상이 상당히 크다.