[종만북] 문제: ROOTS

문제

$polynomial$과 이 $polynomial$의 해들이 범위 $[-20, 20]$내에 실수로 존재할 때, 해를 찾으시오.

문제 링크

서론

이분법에 대해 연습해봅시다.

---

알고리즘 구상

아이디어

문제에서 다항함수 $f(x)$의 해는 모두 다르다고 가정하고, 범위 $[-20, 20]$내에 존재한다고 가정합니다.

따라서 $f(x)$의 극점과 극점 사이에는 해가 존재함을 알 수 있습니다. (중간값 정리와 함수의 연속성 이용)

\[[-21, x_1], \, [x_1, x_2], \, \ldots, [x_{n-2}, x_{n-1}], [x_{n-1}, 21], \quad \text{where } x_1, x_2, \ldots, x_{n-1} \text{ are critical points.}\]

수학적으로 정리하면, 이 구간 내에 해가 존재한다고 알 수 있습니다.

알고리즘 설계

$f(x)$의 critical points는 $f’(x)$가 $0$인 $x$를 의미합니다. 재귀적으로 풀 수 있을 것 처럼 보입니다.

$solve(f(x))$가 해를 구하는 알고리즘이라고 가정해봅시다.

base case: 차수가 2 이하라면, 근의 공식이나 대입을 통해 값을 구합니다.

recursive case: $solve(f’(x))$를 통해 도함수의 해를 구하면, 이 해들은 $f(x)$의 극점이므로

\[[-21, x_1], \, [x_1, x_2], \, \ldots, [x_{n-2}, x_{n-1}], [x_{n-1}, 21], \quad \text{where } x_1, x_2, \ldots, x_{n-1} \text{ are critical points.}\]

각 구간 내에 정확히 하나의 해만 존재하므로, 이분 탐색으로 해를 구하는 알고리즘을 구상할 수 있습니다.

---

알고리즘 구현

사용할 STL들

$f(x)$의 각 계수를 저장하기 위해 vector<double>을 이용합니다.

마찬가지로 해를 구하기 위해서, vector<double>을 이용합니다.

유틸리티 함수

$f(x)$를 구하는 함수, $f’(x)$를 구하는 함수, 이차방정식의 해를 구하는 함수를 구현합니다.

// 함수와 입력 값이 주어졌을 때, 출력하는 함수
double function(const vector<double> &f, double input) {
    double ret = 0.0;
    for (int i = 0; i < f.size(); i++) {
        ret += f[i] * pow(input, i);
    }
    return ret;
}

// 미분했을 때, 차수를 제공하는 함수
vector<double> differentiation(const vector<double> &input) {
    vector<double> ret;
    for (int i = 1; i < input.size(); i++) {
        ret.push_back(input[i] * i);
    }
    return ret;
}

// 이차방정식을 해결하는 함수
vector<double> naive(const vector<double> &input) {
    vector<double> ret;
    double rand = 0;
    double gap = sqrt(input[1] * input[1] - 4 * input[2] * input[0]);
    rand = -input[1];
    ret.push_back((rand - gap) / (2 * input[2]));
    ret.push_back((rand + gap) / (2 * input[2]));
    return ret;
}

solve()

n차 방정식의 해를 구하는 함수를 구현합니다.

// n차 방정식의 해를 구하는 함수
vector<double> solve(const vector<double> &input) {
    int degree = input.size() - 1;
    // base case
    if (degree == 2) return naive(input);

    // 도함수의 해들, 양 옆에 -20 20을 추가
    vector<double> critical_points = solve(differentiation(input));

    // 극점들
    vector<double> points;
    points.push_back(-21.0);
    for (int i = 0; i < degree - 1; i++) {
        points.push_back(critical_points[i]);
    }
    points.push_back(21.0);

    vector<double> ret;

    // 극점들 간의 있는 해를 이분탐색으로 찾음. (문제에서는 있다고 가정)
    for (int i = 0; i < points.size() - 1; i++) {
        double xlo = points[i], xhi = points[i + 1];
        double ylo = function(input, xlo), yhi = function(input, xhi);

        // if (ylo * yhi > 0) continue;
        if (ylo > yhi) {
            swap(ylo, yhi);
            swap(xlo, xhi);
        }

        int it = 100;
        while (it--) {
            double mid = (xlo + xhi) / 2.0;
            double midf = function(input, mid);
            if (ylo * function(input, mid) > 0) {
                xlo = mid;
                ylo = midf;
            } else {
                xhi = mid;
                yhi = midf;
            }
        }
        ret.push_back(xlo);
    }
    return ret;
}

최종 코드

여기에서 확인하세요!