algospot ROOTS

algospot : https://algospot.com/judge/problem/read/ROOTS

github : https://github.com/junho0956/Algorithm

 

algospot ROOTS 단변수 다항 방정식 해결하기 문제입니다.

풀이는 코드에 주석처리 되어있으며 문제해결기법을 참조하였습니다.

 

/*
실수 근만을 갖는 ax2 + bx + c = 0과 같은 형태의 단변수 다항 방정식이 주어질 때
이들의 근을 계산하는 프로그램을 작성하세요.
*/
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
 
// 모든 해의 절대값은 10 이하라고 가정해도 좋습니다.
const int L = 10;
 
// 단일 변수 다항식p의 계수가 주어질 때 미분한 결과 p'의 계수를 반환한다
vector<double> differentiate(const vector<double>& poly) {
    int n = poly.size() - 1;
    vector<double> res;
 
    for (int i = 0; i < n; i++) {
        res.push_back(poly[i] * (n - i));
    }
    return res;
}
 
// 1차 혹은 2차 방정식을 푼다
vector<double> solveNative(const vector<double>& poly) {
    int n = poly.size() - 1;
    vector<double> res;
    if (n == 1) {
        res.push_back((-1) * (poly[1] / poly[0]));
        return res;
    }
    if (n == 2) {
        double a, b, c;
        a = poly[0], b = poly[1], c = poly[2];
        res.push_back(((-b) + (sqrt(pow(b, 2) - 4 * a * c))) / (2 * a));
        res.push_back(((-b) - (sqrt(pow(b, 2) - 4 * a * c))) / (2 * a));
        sort(res.begin(), res.end());
        return res;
    }
}
 
// 다항식 f(x)의 계수 poly가 주어질 때, f(val)를 반환한다
double evaluate(const vector<double>& poly, double val) {
    double ans = 0;
    int n = poly.size() - 1;
    for (int i = 0; i <= n; i++) {
        ans += pow(val, n - i) * poly[i];
    }
 
    return ans;
}
 
// 방정식의 근을 반환한다
vector<double> solve(const vector<double>& poly) {
    
    // 방정식의 계수를 확인한다
    int n = poly.size() - 1;
 
    // 만약 2차 이하라면 바로 해결한다
    if (n <= 2) return solveNative(poly);
 
    // 3차 이상이라면 미분한 방정식을 구한다
    vector<double> different = differentiate(poly);
    // 미분한 방정식에 대한 극점을 재귀를 통하여 구한다
    vector<double> sol = solve(different);
 
    // 왼쪽, 오른쪽 끝의 극점은 그 옆에 또 다른 극점이 존재하지 않으므로 근을 구할 수 없다.
    // 그러므로 초기화 해놓은 L을 이용하여 근을 구한다.
    sol.insert(sol.begin(), -L - 1);
    sol.insert(sol.end(), L + 1);
 
    // 각 극점을 이분법을 이용하여 근을 구한다
    vector<double> res;
 
    for (int i = 0; i < sol.size()-1; i++) {
        double x1 = sol[i], x2 = sol[i + 1];
        double y1 = evaluate(poly, x1), y2 = evaluate(poly, x2);
 
        // y가 같은 부호이면 근이 존재할 수 없다.
        if (y1 * y2 > 0) continue;
        // 불변 조건 : 이분법의 진행과정에 따라 반드시 f(x1) < f(x2) 일 수는 없다.
        // f(x1) <= 0 < f(x2) 를 강제하여 이분법 상의 두 부분중 어느곳을 선택해야 할지 판단한다.
        if (y1 > y2) {
            swap(y1, y2);
            swap(x1, x2);
        }
        // while 이 아닌 최대 100 정도의 for문으로 이분법을 돌리는 것은
        // 이분법 과정에서 무한루프를 방지할 수 있다.
        for (int i = 0; i < 100; i++) {
            double x = (x1 + x2) / 2;
            double y = evaluate(poly, x);
 
            if (y <= 0) x1 = x;
            else x2 = x;
        }
 
        res.push_back(x1);
    }
    sort(res.begin(), res.end());
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    // 입력의 첫 줄에는 테스트 케이스의 수 C(C<=50)가 주어집니다.
    // 각 테스트 케이스의 첫 줄에는 방정식의 차수 n(2 <= n <= 5)이 주어지고,
    // 그 다음 줄에 n+1개의 실수로 방정식의 차수가 고차항부터 주어집니다.
 
    int C; cin >> C;
    while (C--) {
        int n; cin >> n;
        vector<double> poly;
        for (int i = 0; i < n + 1; i++) {
            double val; cin >> val;
            poly.push_back(val);
        }
        // 각 테스트 케이스마다 n개의 실수로 오름차순으로 정렬된 방정식의 해를 출력합니다.
        // 방정식의 해는 모두 다르다고 가정해도 좋습니다.
        // 10 - 8 이하의 상대 / 절대 오차가 있는 답은 정답으로 처리됩니다.
        vector<double> res = solve(poly);
        sort(res.begin(), res.end());
 
        cout << fixed;
        cout.precision(10);
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << " ";
        }
        cout << endl;
    }
    return 0;
}