알고리즘

효욜적인 약수 개수 구하기 알고리즘 :: 마이구미

mygumi 2017. 2. 9. 18:06
반응형

이번 글은 약수를 구하는 알고리즘을 다뤄본다.

약수 구하는 방법은 어렵지 않다.

하지만 조금만 응용된 약수 관련 문제라면 순수한 방법으로는 시간이 너무 오래걸린다.

더 효율적인 방법을 알아볼 것이다.


약수(約數, divisor)는 어떤 수를 나누었을 때 나머지가 0인 수를 말하며, 배수 관계와 서로 반대되는 개념이다. 약수는 보통 정수에 대해 정의되지만, 일반화하여 정역에 대해 정의하기도 한다.


관련 문제를 보자. (약수 문제)

기본적인 문제로써, 주어진 수(N)의 약수의 개수를 구하는 문제이다.

가장 순수한 방법으로는 1부터 N까지 N의 나머지를 구해 0이라면 약수라고 판단한다.


int n = sc.nextInt();
int cnt = 0;

for(int i = 1; i <= n; i++) {
    if (n % i == 0) {
        cnt++; // 약수 개수
        // i 약수
    }
}

System.out.println(cnt);


코드로는 위와 같이 구현할 수 있다.

여기서 조금만 수정한다면 조금 더 효율적일 수 있다.

N의 가장 큰 약수는 N을 제외하면 최대 N의 절반인 것을 이해하면 된다.


int n = sc.nextInt();
int cnt = 0;

for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        cnt++;
        if (i * i < n) {
            cnt++;
        }
    }
}

System.out.println(cnt);


조금 더 효율적으로 풀 수 있게 되었다.


이번엔 응용된 문제를 보자 (응용된 약수 문제)

주어진 범위 안의 수들 중에서 가장 많은 약수의 개수를 찾는 문제다.


가장 순수한 방법으로 접근한다면, 위의 약수 구하는 방법을 활용하면 된다.

범위 안의 각각의 수에 대해 약수의 개수를 구한 후, 가장 큰 약수 개수를 찾으면 된다.


// 1 10000000

int n = sc.nextInt();
int cnt = 0;
int[] count = new int[10000001];

for (int k = 1; k <= 10000000; k++) {
    for (int i = 1; i * i <= k; i++) {
        if (k % i == 0) {
            cnt++;
            if (i * i < k) {
                cnt++;
            }
        }
    }    
    count[k] = cnt;
}


위의 코드로 각 수에 대한 약수의 개수를 구할 수 있다.

하지만 이 코드로는 위와 같은 문제를 해결할 수 없다.

시간이 너무 오래 걸리기 때문이다.

시간복잡도로 n*(n/2) 표현된다면, 1억번의 연산에 1초라고 가정한다면, 무려 10000000 * 5000000 어마어마한 시간이 걸리게 된다.


다른 방법을 통해 접근해보자.

이 방법은 시간복잡도가 nlogn 으로 표현된다.

배수를 활용하는 방법이다.



각 수에 대해 배수를 확인한다면 약수의 개수를 더해나가면서 총 개수를 구할 수 있다.

코드로 나타내면 아래와 같다.


 for (int i = 1; i <= 10000000; i++) {
    for (int j = 1; j <= 10000000 / i; j++) {
        count[i * j]++;
    }
}


1억에 1초라고 가정하면 약 2초에 가까운 시간이 걸리게 되어 문제를 간신히 해결할 수 있다.

이 방법이 아니라도 다른 효율적인 방법이 많이 존재한다.

가장 쉽게 이해할 수 있는 방법이라고 생각한다.

문제에 대한 전체 소스는 Github URL을 참고하길바란다.


2015 AIPO Preliminary Round 출제 문제 , 백준 13225번, 13226번

Divisor - https://www.acmicpc.net/problem/13225

Divisor Again - https://www.acmicpc.net/problem/13226


13225번 - https://github.com/hotehrud/acmicpc/blob/master/algorithm/English/13225.java

13226번 - https://github.com/hotehrud/acmicpc/blob/master/algorithm/English/13226.java

반응형