TEUS.me

 
 


3. 삼각수의 약수의 개수


문제 중에 처음 호기심을 자극한 문제가 이것이다.

이 문제는 언뜻 보면 기초적인 문제 같지만, 동작 성능을 고려하면 상당히 고난이도 문제다.


물론, 단순무식하게 아래와 같이 만들어도 동작은 한다…


#include <stdio.h>
#include <stdlib.h>

int countOfDivisors(int num)
{
    if (num < 2) return 1;

    // 1과 자신은 무조건 약수이므로 2부터 시작
    int ret = 2;
    for (int i = num / 2; i >= 2; i--) {
        if (num % i == 0) ret++;
    }
    return ret;
}

int main(int argc, char* argv[])
{
    printf("-= count of divisors of triangular numbers =-\n");

    int triangularnumber = 0;
    int n = 1;
    while (true) {
        triangularnumber += (n++);
        int count = countOfDivisors(triangularnumber);
       
        if (count >= 500) {
            printf("sum of 1..%d = %d\n", n - 1, triangularnumber);
            printf("count of dividors of %d = %d\n", triangularnumber, count);

            break;
        }
    }
    return 0;
}


위 코드에서는 약수의 개수를 세는 함수에 아주 최소한의 최적화만 했다.

물론, 이렇게 만들어도 동작은 아무 이상 없이 한다. 조금 느릴 뿐이다.

내 컴퓨터(AMD A8-8870 3GHz)에서 44분 16초 걸렸다…



이건 좀 너무한 것 같으니, 살짝 최적화를 해보기로 한다.

중학교 때쯤 소인수분해라는 걸 배우는데. 여기서 우리는


\(d = a^m \cdot b^n \cdot c^o\)


형태로 인수분해되는 d의 약수의 개수는 아래와 같다는 것을 배웠다.


\((m+1) \cdot (n+1) \cdot (o+1)\)


그렇다면, 일단 2로 몇번 나눌 수 있는 지를 확인한 뒤에 그 부분만 적용해보기로 한다.


#include <stdio.h>
#include <stdlib.h>

int countOfDivisors(int num)
{
    // a^n*b^m 으로 소인수분해되는 수의 약수 갯수는
    // (n+1)*(m+1)임
    // 2^n 쪽은 쉽게 계산 가능함
    int two = 0;
    while ((num & 1) == 0) {
        num >>= 1;
        two++;
    }

    int ret;
    if (num < 2) ret = 1;
    else {
        ret = 2;
        for (int i = num / 2; i >= 2; i--) {
            if (num % i == 0) ret++;
        }
    }
    return ret*(two + 1);
}

int main(int argc, char* argv[])
{
    printf("-= count of divisors of triangular numbers =-\n");

    int triangularnumber = 0;
    int n = 1;
    while (true) {
        triangularnumber += (n++);
        int count = countOfDivisors(triangularnumber);
       
        if (count >= 500) {
            printf("sum of 1..%d = %d\n", n - 1, triangularnumber);
            printf("count of dividors of %d = %d\n", triangularnumber, count);

            break;
        }
    }
    return 0;
}


단지 약수 중에 2에 대해서만 최적화했을 뿐인데, 조금 빨라졌다.

29분 17초로 34% 정도 빨라진 것이다.


그렇다면, 아예 소인수분해의 개념을 제대로 적용해보기로 한다.

단, 모든 약수를 다 뽑아내는 것이 아니라 약수의 개수만 세는 것이라 약수 자체를 뽑아낼 필요는 없다.


#include <stdio.h>
#include <stdlib.h>

int countOfDivisors(int num)
{
    if (num < 2) return 1;
    int half = num / 2;
    int ret = 1;

    for (int i = 2; i <= half; i++) {
        int now = 0;
        while (num % i == 0) {
            now++;
            num /= i;
        }
        if (now) {
            ret *= (now + 1);
            half = num / 2;
        }
    }

    if (num > 1) {
        ret *= 2;
    }

    return ret;
}

int main(int argc, char* argv[])
{
    printf("-= count of divisors of triangular numbers =-\n");

    int triangularnumber = 0;
    int n = 1;
    while (true) {
        triangularnumber += (n++);
        int count = countOfDivisors(triangularnumber);
       
        if (count >= 500) {
            printf("sum of 1..%d = %d\n", n - 1, triangularnumber);
            printf("count of dividors of %d = %d\n", triangularnumber, count);

            break;
        }
    }
    return 0;
}


이렇게 최적화된 결과는 소요 시간이 ms 단위로 나온다.

제대로 최적화된 것이다.


-= count of divisors of triangular numbers =-
sum of 1..12375 = 76576500
count of dividors of 76576500 = 576


덧. 이 문제는 이 회사에서 창작한 오리지널 문제가 전혀 아니다.

프로젝트 오일러 12번 문제를 그대로 출제한 것이다.



공유하기

facebook twitter kakaoTalk kakaostory naver band

본문과 관련 있는 내용으로 댓글을 남겨주시면 감사하겠습니다.

비밀글모드

  1. bumsook
    프로젝트 오일러 문제가 입사 테스트로 나온다니 신기하네요.

    저 문제를 프로젝트 오일러에서 봤을때 저같은경우 최적화를 "1~sqrt(n)까지 약수를 세되, sqrt(n)이 아닌 값들에선 2씩 증가시킨다 (d와 n/d를 한번에 세 주는 식으로)" 했었는데 어떤 쪽이 더 빠른지 문득 궁금하네요. 이것도 사실 n까지 셀걸 sqrt(n)까지 세는거니 상당히 빠른 코드긴 하겠지만 그래도 소인수분해 optimization쪽이 정말 큰 숫자들에 대해서는 더 빠를 것 같기도 하구요. Java에서 저 sqrt(n) optimization으로 400ms쯤 걸리던데 소인수분해는 얼마나 걸리나요?
    2014.10.13 11:52
    • 제 PC에선 187ms 걸리네요. 이 방법이 최적인 것 같습니다. ^^
      2014.10.13 19:54 신고