재배열 부등식 Rearrangement InequalityPermalink

r1≤r2≤⋯≤rnr_1 \le r_2 \le \cdots \le r_n 이고, s1≤s2≤⋯≤sns_1 \le s_2 \le \cdots \le s_n 이라 하자.

그러면, 임의의 s1,s2,…,sns_1,s_2,\dots,s_n의 순열 t1,t2,…,tnt_1, t_2, \dots, t_n 에 대해서,

r1sn+r2sn−1+⋯+rns1   ≤r1t1+r2t2+⋯+rntn   ≤r1s1+r2s2+⋯+rnsn \begin{aligned} &r_1s_n+r_2s_{n-1} + \cdots + r_ns_1\\ &~~~\le r_1t_1 + r_2t_2 + \cdots + r_nt_n\\ &~~~\le r_1s_1 + r_2s_2 + \cdots + r_ns_n \end{aligned}

이 성립한다.

증명

x1<x2<⋯<xp<xqy1<y2<⋯<yp<yq \begin{aligned} x_1 < x_2 < \dots < x_p < x_q\\ y_1 < y_2 < \dots < y_p < y_q \end{aligned}

일 때, (p<q)(p < q)

S1=x1y1+x2y2+⋯+xpyp+xqyqS2=x1y1+x2y2+⋯+xqyq+xpyqS1−S2=xpyp+xqyq−xqyp−xpyq=(xo−xq)(yp−yq)>0∴S1>S2 \begin{aligned} S_1 &= x_1y_1+x_2y_2 + \cdots + x_py_p + x_qy_q\\ S_2 &= x_1y_1 + x_2y_2 + \cdots + x_qy_q + x_py_q\\\\ S_1-S_2&=x_py_p+x_qy_q-x_qy_p-x_py_q\\ &=(x_o-x_q)(y_p-y_q)>0\\ \\ &\therefore S_1 > S_2 \end{aligned}

즉, 임의의 두 위치를 바꾸었을 때 합이 항상 작아지므로 최대합 SS는 치환 π\pi가 π(i)=i\pi(i)=i 일 때 성립한다. □\square

재배열 부등식은 그리디 알고리즘의 한 종류라고 볼 수 있다.

체비셰프 합 부등식 Chebyshev’s InequalityPermalink

x1<x2<⋯<xny1<y2<⋯<yn⇓n(x1y1+x2y2+⋯+xnyn)≥(x1+x2+⋯+xn)(y1+y2+⋯+yn) \begin{aligned} x_1 < x_2 &< \dots < x_n\\ y_1 < y_2 &< \dots < y_n\\ \Downarrow\\ n(x_1y_1+x_2y_2+\cdots + x_ny_n) &\ge (x_1 + x_2 + \cdots + x_n)(y_1 + y_2 + \cdots + y_n) \end{aligned}

연습 문제Permalink

BOJ 1026 - 보물

재배열 부등식의 성질을 이용해 바로 풀 수 있다. 그리디 알고리즘 문제이다.

Comments

You may also enjoy