재배열 부등식 Rearrangement Inequality
r1≤r2≤⋯≤rn 이고, s1≤s2≤⋯≤sn 이라 하자.
그러면, 임의의 s1,s2,…,sn의 순열 t1,t2,…,tn 에 대해서,
r1sn+r2sn−1+⋯+rns1 ≤r1t1+r2t2+⋯+rntn ≤r1s1+r2s2+⋯+rnsn
이 성립한다.
증명
x1<x2<⋯<xp<xqy1<y2<⋯<yp<yq
일 때, (p<q)
S1S2S1−S2=x1y1+x2y2+⋯+xpyp+xqyq=x1y1+x2y2+⋯+xqyq+xpyq=xpyp+xqyq−xqyp−xpyq=(xo−xq)(yp−yq)>0∴S1>S2
즉, 임의의 두 위치를 바꾸었을 때 합이 항상 작아지므로 최대합 S는 치환 π가 π(i)=i 일 때 성립한다. □
재배열 부등식은 그리디 알고리즘의 한 종류라고 볼 수 있다.
체비셰프 합 부등식 Chebyshev’s Inequality
x1<x2y1<y2⇓n(x1y1+x2y2+⋯+xnyn)<⋯<xn<⋯<yn≥(x1+x2+⋯+xn)(y1+y2+⋯+yn)
연습 문제
BOJ 1026 - 보물
재배열 부등식의 성질을 이용해 바로 풀 수 있다. 그리디 알고리즘 문제이다.
Comments