[C/C++] 프로젝트 오일러 #101 Optimum Polynomial(다항식)

이 문제는 수학적 규칙을 따르는 점열(sequence)을 생성하는 다항식(polynomial)과 관련이 있습니다. 문제를 해결하기 위해 주어진 점열을 분석하고, 다항식의 특성을 활용하여 최적의 다항식을 찾는 것이 핵심입니다.

문제 이해

1. 점열의 생성
문제는 특정한 다항식 $U(n)$을 통해 생성된 점열이 주어질 때, 이 점열을 근사하는 최적의 다항식을 찾는 것입니다. 점열의 각 항은 다음과 같은 형태를 가집니다:

 

$u(n)=U(n)$

 

여기서 $U(n)$ 은 n-차 다항식입니다.
예를 들어, $U(n)=n^3-2n^2+n$ 일 경우, $u(1)=0,u(2)=6,u(3)=24,\dots$ 와 같은 점열이 생성됩니다.

 

2. 부분 점열
문제는 $n=1$ 부터 시작하는 점열의 일부만 주어진 상태에서, 이를 통해 다항식 $U(n)$ 을 근사해야 합니다.
예를 들어, 주어진 점열의 첫 3개의 값이 $u(1)=1,u(2)=8,u(3)=27$ 이라면, 이는 $U(n)=n^3$ 을 포함할 가능성이 있습니다.

 

3. 근사 다항식 (Fitting Polynomial)
k-차 다항식을 사용하여 점열을 근사하는 다항식을 $F_k(n)$ 이라고 정의합니다.
• k = 1 일 때는 선형 다항식,
• k = 2 일 때는 2차 다항식,
• k = 3 일 때는 3차 다항식,
… 등의 형태를 갖습니다.
점열의 일부를 사용해 최적화된 $F_k(n)$ 를 구하는 것이 목표입니다.

 

4. BEST (BOP) 값
$F_k(n)$ 를 사용하여 예측된 점열 $u(n)$ 값과 실제 값의 차이를 확인합니다. 특히, $F_k(n)$ 를 통해 “잘못된 예측(Best OP)” 값을 계산해야 합니다. 이 과정에서 최적화와 오차 분석이 중요합니다.

1. 1차 다항식의 경우라면, $U(n)=2n+3$ 이라 가정합시다.
• 점열: $u(1)=5,u(2)=7,u(3)=9,\dots$
• k = 1 로 가정하고 $F_1(n)=a\cdot n+b$ 형태의 다항식을 찾아 근사합니다.
2. 2차 다항식 $U(n)=n^2+n+1$이라면, 주어진 점열 일부 $u(1)=3,u(2)=7,u(3)=13$ 에서 k=2 로 가정하여 $F_2(n)$ 를 찾습니다.
3. 오차 계산
$u(4)=21$ 인데, $F_2(4)$ 에서 19로 예측했다면 오차는 2입니다.

이 문제의 핵심은 점열을 분석하여 점진적으로 $U(n)$ 과 가까운 다항식을 추측하고, 이를 통해 BEST(BOP) 값을 계산하며 최적의 근사를 찾아가는 것입니다.

 

polynomial

 

문제 출처

https://projecteuler.net/problem=101

 

제가 작성한 소스는 다음과 같습니다.

//------------------------------------------------
//    Project Euler #101 - Optimum Polynomial
//        - by Aubrey Choi
//        - created at 2015-03-27
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

struct FN
{
    int n;            //    highest degree
    int64_t poly[20];    //    lowest : 0 ~ n
};

void SimpleGuess(FN *t, FN *s, int n, int fs[], int fact);
int64_t FindFIT(FN *g, FN *s, int n);
int64_t GetValue(FN *f, int n);
void PrintFn(FN *f);

int main()
{
    FN s = { 10, { 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1 } };
    //FN s = { 3, { 0, 0, 0, 1 } };
    FN g = { 0, { 0 } };
    int64_t ans = 0;
    int n = 1;
    int fs[20] = { 1 };
    int fact = 1;

    for( int n = 1 ; n <= s.n+1 ; n++ )
    {
        SimpleGuess(&g, &s, n, fs, fact);
        PrintFn(&g);
        if( g.n == s.n ) break;

        fact *= n;
        for( int i = n ; i > 0 ; i-- )
            fs[i] = fs[i-1];
        fs[0] = 0;
        for( int i = 0 ; i < n ; i++ )
            fs[i] -= n*fs[i+1];
        if( g.poly[n-1] ) ans += FindFIT(&g, &s, n);
    }
    printf("ans = %jd\n", ans);
}

void SimpleGuess(FN *t, FN *s, int n, int fs[], int fact)
{
    int64_t v = GetValue(s, n);
    v -= GetValue(t, n);
    if( v == 0 ) return;
    t->n = n-1;
    for( int i = 0 ; i < n ; i++ ) t->poly[i] += v*fs[i]/fact;
}

int64_t FindFIT(FN *g, FN *s, int n)
{
    for( int i = n+1 ; ; i++ )
    {
        int64_t v = GetValue(g, i);
        int64_t u = GetValue(s, i);
        if( v != u ) return v;
    }
}

int64_t GetValue(FN *f, int n)
{
    int64_t v = 0;
    for( int i = f->n ; i >= 0 ; i-- )
    {
        v *= n;
        v += f->poly[i];
    }
    return v;
}

void PrintFn(FN *f)
{
    bool needOp = false;
    printf("u = ");
    if( f->poly[0] != 0 ) { printf("%jd", f->poly[0]); needOp = true; }
    for( int i = 1 ; i <= f->n ; i++ )
    {
        if( f->poly[i] == 0 ) continue;
        if( f->poly[i] > 0 ) { if( needOp ) printf("+"); } 
        else printf("-");
        needOp = true;
        if( f->poly[i] > 1 ) printf("%jd", f->poly[i]);
        else if( f->poly[i] < -1 ) printf("%jd", -f->poly[i]);
        printf("n^%d", i);
    }
    putchar('\n');
}

 

소스 코드의 핵심 알고리즘과 설명

주어진 다항식을 기반으로 생성된 점열을 통해 “최적화된 다항식 근사”를 계산하고, “잘못된 예측 값(Best OP, BOP)“을 합산하는 과정이 포함되어 있습니다.

점열의 일부 값만을 사용하여 n-차 다항식을 추정합니다. 이 추정값은 점열의 나머지 값을 근사합니다.
근사된 다항식 $F_k(n)$ 가 실제 다항식과 일치하지 않는 가장 빠른 n-값에서의 예측 값을 계산합니다. 이는 문제에서 요구하는 BOP의 정의입니다.
점진적으로 k-차 다항식을 계산하며, 점열의 일부 항만 사용하여 근사합니다. 이전 단계에서의 결과를 다음 단계 계산에 활용합니다.

(1) 주요 구조체와 함수 개요

1. 구조체 FN
• FN은 다항식을 표현합니다.
• n: 다항식의 차수 (highest degree).
• poly[20]: 다항식의 계수 배열 (차수별 계수를 저장).
2. SimpleGuess(FN *t, FN *s, int n, int fs[], int fact)
• n-차 다항식 근사를 업데이트합니다.
• 현재까지 계산된 다항식 t 에 새로운 점 n 에서의 값을 반영하여 계수를 조정합니다.
3. FindFIT(FN *g, FN *s, int n)
• 근사된 다항식 g 와 실제 점열 s 를 비교하여 n+1 부터 최초로 불일치하는 값을 찾아 반환합니다.
4. GetValue(FN *f, int n)
• 다항식 f 를 사용해 특정 n 에서의 값을 계산합니다.
5. PrintFn(FN *f)
• 다항식을 사람이 읽을 수 있는 형태로 출력합니다.

(2) 메인 함수

int main()
{
    FN s = { 10, { 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1 } };
    FN g = { 0, { 0 } };
    int64_t ans = 0;
    int n = 1;
    int fs[20] = { 1 };
    int fact = 1;

    for( int n = 1 ; n <= s.n+1 ; n++ )
    {
        SimpleGuess(&g, &s, n, fs, fact);
        PrintFn(&g);
        if( g.n == s.n ) break;

        fact *= n;
        for( int i = n ; i > 0 ; i-- )
            fs[i] = fs[i-1];
        fs[0] = 0;
        for( int i = 0 ; i < n ; i++ )
            fs[i] -= n*fs[i+1];
        if( g.poly[n-1] ) ans += FindFIT(&g, &s, n);
    }
    printf("ans = %jd\n", ans);
}

1. 다항식 정의
• s는 실제 점열을 생성하는 $U(n)$ 을 표현합니다. 여기서는 $U(n)=n^{10}-n^9+\cdots +n^0$로 설정되었습니다.
2. 초기화
• g: 근사 다항식 $F_k(n)$ 초기값.
• fs: 다항식 근사를 위한 계수 업데이트 배열.
• fact: 팩토리얼 계산 (다항식 계수 조정을 위해 사용).
3. 루프 구조
• n 을 증가시키며 $F_k(n)$ 을 점진적으로 업데이트합니다.
• SimpleGuess: 점열의 n-번째 항을 반영하여 $F_k(n)$ 를 업데이트.
• FindFIT: 근사 다항식과 실제 점열 간의 불일치 값을 계산.
• fs와 fact를 갱신하여 다음 단계 계산에 활용.

1. SimpleGuess 함수

void SimpleGuess(FN *t, FN *s, int n, int fs[], int fact)
{
    int64_t v = GetValue(s, n);
    v -= GetValue(t, n);
    if( v == 0 ) return;
    t->n = n-1;
    for( int i = 0 ; i < n ; i++ ) t->poly[i] += v*fs[i]/fact;
}

• t: 현재까지의 근사 다항식.
• s: 실제 점열.
• fs: 다항식 계수 업데이트용 배열.
• fact: 계수 정규화를 위한 팩토리얼 값.
작동 원리:
• n-번째 점열 값에서 기존 다항식의 예측 값을 뺀 오차를 계산 (v).
• 이 오차를 다항식에 반영하여 계수 배열을 업데이트.

2. FindFIT 함수

int64_t FindFIT(FN *g, FN *s, int n)
{
    for( int i = n+1 ; ; i++ )
    {
        int64_t v = GetValue(g, i);
        int64_t u = GetValue(s, i);
        if( v != u ) return v;
    }
}

• g: 근사 다항식.
• s: 실제 점열.
작동 원리:
• n+1 부터 시작하여 g(i) 와 s(i) 를 비교.
• 최초로 값이 다른 경우, g(i) 값을 반환.

3. GetValue 함수

int64_t GetValue(FN *f, int n)
{
    int64_t v = 0;
    for( int i = f->n ; i >= 0 ; i-- )
    {
        v *= n;
        v += f->poly[i];
    }
    return v;
}

작동 원리:
• 다항식 f의 계수를 사용해 n에서의 값을 계산.
• 계수 배열과 n-제곱을 활용해 결과를 도출.