이분법(Bisection method)

* 이분법(Bisection method)
  1차원 데이터에 대해 [low, high] 구간을 지정하고, 원하는 데이터를 이분적으로 찾아가는 방식을 말한다.
여기서 low와 high는 사용자 정의 f()함수에 대해 f(low) > f(high)인 경우 low와 high를 swap 해주는 것이 더욱 깔끔하게 소스를 짤 수 있다.
  즉, low = 10, high = 15, f(low) = 2, f(high) = 1 인 경우, 결과적으로 f(low)가 f(high)보다 크기 때문에 구간 [low, high]를 [15, 10]로 잡는 것이다.

  방식은 iteration(순차 접근, for문)을 이용하는 방법과 while로 근사치를 추정해나가는 방식이 있다. 두 방식 중 안전한 방법은 iteration한 방법이다. 이유는 while로 근사치를 추정하는 방식은 프로그래머에게 직접 데이터를 설정을 강요하기 때문이며, 이 근사치가 실제 해와 다른 근사치로 설정될 수 있기 때문이다.

  iteration을 이용하는 경우엔 약 100번 정도 돌면 2^100 만큼 데이터를 나누고 찾아가게 되는데, 이정도면 소수값 답을 매우 근사하게 다가갈 수 있기 때문이다.

(※ 이 게시글에선 두 방식을 섞여 있다.)

* 문제

1. 2017 아주대학교 프로그래밍 경시대회 (APC) - 구분구적법 (Large, Small)

   (https://www.acmicpc.net/problem/14609, https://www.acmicpc.net/problem/14608)

  구간 low, high를 해당 x축의 가로 크기로 두고 이분법을 사용하여 적당한(오차의 범위에 벗어나지 않는) 값을 찾아간다.

문제에서 주어진 오차값을 1e-4를 이용하여 답을 도출해낼 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <cstdio> #include <cmath> double diff = 0.0001, m = 1e-15; double abs_v(double a) { return a < 0 ? -a : a; } double ing(int c, int n, int a) {     return c*(pow(a, n + 1.) / (double)(n + 1)); } double gv(int c, int n, double a) {     return c*pow(a, n); } int main() {     int K, c[10], a, b,N,i,j;     double integral=0, ans=-1,l,r,mid,fx,seg,off;     scanf("%d", &K);     for (i = 0; i <= K; i++)         scanf("%d", &c[i]);     scanf("%d%d%d", &a, &b, &N);     for (i = 0; i <= K; i++)         integral += ing(c[i], K - i, b) - ing(c[i], K - i, a);     l = 0, seg = r = (double)(b - a)/N;     while (l <= r) {         mid = (l + r) / 2;         fx = 0;         for (i = 0; i < N; i++)             for (j = 0; j <= K; j++)                 fx += gv(c[j], K - j, a + i*seg + mid)*seg;           if (abs_v(integral - fx) <= diff) {             ans = mid;             break;         }           if (integral > fx) l = mid + m;         else r = mid - m;     }     printf("%lf", ans);     return 0; }

2. ROOTS

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

  재밌는 문제 !

  해를 구하기 위해 극점 추출을 한다. 극점은 f(x)에 대해 미분을 한 g(x)의 해가 곧 f(x)의 극점 위치가 된다. 이 점을 활용해야 한당

  2차 이하 방정식에 대해서 해는 근의 공식으로 구할 수 있고, 그 이상에 대해서는 미분을 하고, 극점을 추출한 다음, 극점 간의 데이터를 확인하여 해를 구하는 방식을 취한다.(재귀)

  아래 그림에서 e1,e2,e3가 극점이고 x0,x1,x2,x3가 해일 때, 양 끝과 극점 사이에 답이 있음을 알 수 있다. 단 f(e_i)*f(e_i+1) <= 0 이어야만 해가 존재한다. 극점 사이에 해가 존재한다면, 양 끝 극점의 f(x)값은 서로 부호가 달라야하기 때문이다.

  극점말고 양끝 구간에 대해서는 문제에 보이듯 절대값이 10 이하이므로 그 구간을 -11 ~ 11으로 대충 잡아주자.

  이제 이분법으로 답을 찾아가야 한다.

  이분법은 x1, x2에 대해 가운데 값을 구하고(mid = (x1+x2)/2) 그 값의 f(mid)를 구한다. 그 값이 0에 근접하다면 이를 답으로 내놓는다. 근접의 기준은 문제에서 주어진 값을 이용하며 최대한 근사한 치로 구하도록 한다.

- 코드

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; typedef double DT; const int L = 10; const DT diff = 1e-9; DT abs_v(DT a) { return a < 0 ? -a : a; }   vector<DT> getF0(vector<DT> coefs){     vector<DT> ret;     DT a=coefs[0],b=coefs[1], ans;     if(coefs.size() == 3) {         DT c=coefs[2], t;         ans = -b/(2*a);         if(b*b-4*a*c < 0) return ret; // 2-degree equation doesn't have any ans.         t = sqrt(b*b-4*a*c)/(2*a);         if(t == 0)             ret.push_back(ans);         else{             ret.push_back(ans + t);             ret.push_back(ans - t);         }     } else         ret.push_back(-b/a);     return ret; }   vector<DT> getDifferential(vector<DT> coefs){     vector<DT> ret;     int n = coefs.size(),i;     for(i=0;i<n-1;i++)         ret.push_back((n-1-i)*coefs[i]);     return ret; }   DT getFx(vector<DT> coefs, DT x){     DT ret = 0;     for(int i=0;i<coefs.size();i++){         ret *= x;         ret += coefs[i];     }     return ret; }   vector<DT> getAnswer(vector<DT> coefs){     int n = (int)coefs.size()-1;     if(n <= 2)         return getF0(coefs);     vector<DT> extremumP = getAnswer(getDifferential(coefs));     extremumP.insert(extremumP.begin(), -L-1);     extremumP.insert(extremumP.end(), L+1);     sort(extremumP.begin(), extremumP.end());     DT x1, x2, y1, y2, low, high,mid, y;     vector<DT> ret;     for(int i=0;i<extremumP.size()-1;i++){         x1 = extremumP[i], x2 = extremumP[i+1];         y1 = getFx(coefs, x1), y2 = getFx(coefs, x2);         if(y1*y2 > 0) continue;         low = y1 >= 0 ? x2 : x1;         high = y1 >= 0 ? x1 : x2;         do {             mid = (low + high) / 2;             y = getFx(coefs, mid);             if(y < 0) low = mid;             else high = mid;         } while(abs_v(y) > diff);         ret.push_back(mid);     }     return ret; }   int main() {     int C,n,i;     DT d;     vector<DT> coefs, ans;     scanf("%d",&C);     while(C--){         scanf("%d\n",&n);         for(i=0;i<=n;i++){             scanf("%lf",&d);             coefs.push_back(d);         }         ans = getAnswer(coefs);         sort(ans.begin(),ans.end());         for(i=0;i<ans.size();i++)             printf("%.12lf ", ans[i]);         puts("");         coefs.clear();     }     return 0; }

3. LOAN

   (https://algospot.com/judge/problem/read/LOAN)

  low와 high를 제대로 설정만 한다면 충분히 쉽게 접근할 수 있는 문제.

  high의 경우 C로 처리해야하는 최대값을 설정한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <cstdio> int main() {     int T, M;     double N, P, lo,hi,mid,i,TN;     scanf("%d", &T);     while (T--) {         scanf("%lf %d %lf", &N, &M, &P);         lo = 0;         hi = N*(1.0 + P/1200.);           for(int it=0;it<100;it++){             TN = N;             mid = (lo + hi) / 2.;             for (i = 0; i < M; i++) {                 TN *= (1.0 + P / 1200.);                 TN -= mid;             }             if (TN <= 0) hi = mid;             else lo = mid;         }         printf("%.12lf\n", hi);     }     return 0; }