네이버에 올라온 모 회사 입사 테스트 문제 풀이 2/4

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번 문제를 그대로 출제한 것이다.