🚀 [ROOTS] 문제 📈📈📈📈😊
실수 근만을 갖는 \(ax^2 + bx + c = 0\) 과 같은 형태의 단변수 다항 방정식이 주어질 때, 이들의 근을 계산하는 프로그램을 작성하세요.
다항식의 모든 해의 절대값은 10 이하라고 가정해도 좋습니다.
수강 철회를 하면 철회한 과목은 중간 고사의 누적 등수 계산에 들어가지 않게 됩니다. 다행히 백준이네 학교에서는 수강 철회를 해도 남은 과목이 k 개 이상이라면 장학금을 받을 수 있습니다. 백준이가 적절히 과목을 철회했을 때 얻을 수 있는 최소 누적 등수를 계산하는 프로그램을 작성하세요.
🔑 [풀이]
다항 방정식이 주어질 때 해를 찾는 방법은 우선 변곡점(미분 하였을때 근)을 구하여 변곡점을 기준으로 그 사이의 값들을 이분법을 사용하여 탐색하고 해를 찾아냅니다.
하지만 이 방법 만으로는 가장 왼쪽과 오른쪽 근은 찾을 수가 없습니다. 그리하여 변곡점을 기준으로 하되 가장 왼쪽과 가장 오른쪽에 (가장 왼쪽의 변곡점 - L), (가장 오른쪽의 변곡점 + L) 을 변곡점 컨테이너(range)에 추가해 줍니다.
그리하여 찾아진 변곡접 컨테이너를 순회하면서 이분법을 사용하여 탐색하고 해를 찾아냅니다.
⌨️ 입력
입력의 첫 줄에는 테스트 케이스의 수 C(C<=50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 방정식의 차수 n(2 <= n <= 5)이 주어지고, 그 다음 줄에 n+1개의 실수로 방정식의 차수가 고차항부터 주어집니다.
🖥 출력
각 테스트 케이스마다 n개의 실수로 오름차순으로 정렬된 방정식의 해를 출력합니다. 방정식의 해는 모두 다르다고 가정해도 좋습니다. \(10^-8\) 이하의 상대/절대 오차가 있는 답은 정답으로 처리됩니다.
🖱 입력 예제
2
3
1.00 -6.00 11.00 -6.00
2
1.00 -12.50 31.50
💻 출력 예제
1.000000000000 2.000000000000 3.000000000000
3.500000000000 9.000000000000
💎 전체 코드는 다음과 같습니다.
//
// ROOTS.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/07.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("ROOTS.txt");
int N; // 방정식의 차수
// 미분한 결과 p의 계수를 리턴
vector<double> differentiate(const vector<double>& poly){
int degree = poly.size() -1;
vector<double> result;
for(int i=0; i< degree; i++){
result.push_back(poly[i]*(degree-i) );
}
return result;
}
// 2차 이하 방정식이 주어지면 해를 리턴함
vector<double> solveNaive(const vector<double> &poly){
int degree = poly.size() -1;
vector<double> result;
if(degree == 2){
double a= poly[0], b = poly[1], c = poly[2];
if((pow(b,2) - 4*a*c) <0 ){ // 근이 존재하지 않을 경우
result.push_back(987654321);
return result;
}
// 근의 공식
double first = (-b+sqrt(pow(b,2) - 4*a*c)) / (2*a) ;
double second = (-b-sqrt(pow(b,2) - 4*a*c)) / (2*a) ;
if(first > second){ swap(first,second);}
result.push_back(first);
result.push_back(second);
}
else if(degree == 1){
result.push_back(-(poly[1]/poly[0]));
}
return result;
}
// f(x0) 가 주어지면 답을 리턴함.
double evaluate(const vector<double> &poly, double x0){
int degree = poly.size();
double sum = 0;
for(int i=0; i<degree; i++){
sum += poly[i]*pow(x0,(degree-1-i));
}
return sum;
}
const double L = 10;
vector<double> solve(const vector<double> &poly){
int degree = poly.size() - 1;
if(degree <= 2){
return solveNaive(poly);
}
vector<double> temp = differentiate(poly);
vector<double> range = solve(temp);
// 맨앞과 맨뒤에 L크기를 추가한다.
range.insert(range.begin(), -L-1);
range.insert(range.end(), L + 1);
vector<double> result;
for(int i=0; i< range.size()-1; i++){
double x1 = range[i], x2 = range[i+1];
double y1 = evaluate(poly, x1), y2 = evaluate(poly, x2);
if(y1*y2 > 0) continue; // 같은부호이면 해를 가지지 않기 때문.
// 증가하는 방향으로 생각한다.
if(y1 > y2) { swap(x1,x2); swap(y1,y2);}
// 100 번을 쪼개 최적값을 찾는다.
for(int it = 0; it<100; it++){
double mid_x = (x1+x2)/2.0;
double mid_y = evaluate(poly, mid_x);
if(mid_y*y1 > 0){
x1 = mid_x;
y1 = mid_y;
}
else{
x2 = mid_x;
y2 = mid_y;
}
}
result.push_back((x1+x2)/2.0);
}
sort(result.begin(),result.end());
return result;
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test < test_case; test++){
fin >> N ;
vector<double> poly;
for(int i=0; i< N+1; i++){
double degree;
fin >> degree;
poly.push_back(degree);
}
vector<double> result = solve(poly);
for(int i=0; i<result.size(); i++){
printf("%0.8f ",result[i]);
}
cout << endl;
}
}
Comments