20. 프로젝트 오일러 #20 : 100!의 모든 자릿수 합 구하기

알고리즘에서 가장 큰 알고리즘을 분류하는 것 중에, 기하급수보다 더 큰 것이 있다면, 모든 경우의 수를 조사하는 팩토리얼(factorial)일겁니다.  뭐 이것보다 더 큰 것도 있을 수 있는데요.  예를 들면, 연제곱승(제곱승에 제곱승이 이어나가는)이 있지만, 이런 알고리즘은 거의 보기 힘듭니다.  연제곱승과 반대되는 것으로는 연로그(로그 안에 로그가 있는 형태)이거나, 연로그가 일정한 값이 되는 로그의 갯수 등입니다.  정확한 용어는 제가 모르지만, 힙정렬에서 힙을 만드는 과정에 이런 개념이 나옵니다.

사실 정렬에서 우리는 일반적으로 이라고 알고 있지만요.  사실 더 본격적으로 들어가면, n개가 배열될 수 있는 경우의 수를 매번 2가지 경우로 나누어져서 찾아서 정렬하는 방법이기 때문에, 최적의 정렬 알고리즘의 한계는 이 된다는 것입니다.

실제 그래프를 그려보면, 둘 사이에는 차이가 생기는 것을 알 수가 있습니다.  그래서인지 더 좋은 정렬 알고리즘은 현실적으로도 이론적으로도 나오기 힘듭니다.  이론적으로 더 좋은 알고리즘이 있다하더라도 비재귀적으로 만들지 않으면 별 소용이 없는 일이니까요.

대학에 가면 C언어 수업에서 1부터 100까지 더하기나 1부터 10까지 곱하기 등을 for 루프를 이용해서 많이 하는 것으로 압니다.  뭐 알고리즘 자체는 어려울 것은 없지만요,  워낙 팩토리얼이 기하급수로 늘어나는 것이라서요.  10! 이 백만단위라면, 100!은 10의 150승 이상이 됩니다.  그래서 Big Integer를 이용할 수밖에 없습니다.  저는 제가 만든 라이브러리를 이용해서 만들었습니다.

#include <stdio.h>
#include "NxBigInt.h"

int main()
{
    NxBigInt z = 1;

    for( int i = 1 ; i <= 100 ; i++ )
        z *= i;

    unsigned char arr[1000];

    int len = z.ConvertToArrayLE(arr, 1000);

    int sum = 0;
    for( int i = 0 ; i < len ; i++ )
        sum += arr[i];

    printf("Ans = %d\n", sum);
}