중앙값 구하기의 OverflowPermalink

우리가 특정 문제에서 L+R2\left\lfloor \dfrac {L+R}2 \right\rfloor 의 값을 구해주어야 할 때, L+RL+R 은 overflow가 날 수도 있는 상황이 있을 수 있다.

안전한 공식Permalink

이 때, L+R2=L+RL2\left\lfloor \dfrac {L+R}2 \right\rfloor = L+\left\lfloor \dfrac {R-L}2 \right\rfloor 라는 사실을 이용하여 overflow를 피해줄 수 있다.

\left\lfloor \right\rfloor 이 없다면 저 식은 실수에서 성립하는데 정수에서도 성립할까?

1. L+RL+R 이 짝수일 때,Permalink

RLR-L 도 짝수이다. RRLL이 모두 짝수일 때는 자명하고 RRLL이 모두 홀수일 때도 옳다.

따라서 \left\lfloor \right\rfloor 에 영향을 받지 않으므로 식이 성립한다.

2. L+RL+R이 홀수일 때,Permalink

RLR-L 도 홀수이다. 위와 비슷한 방식으로 유도할 수 있다.

L+R2=L+RL2\left\lfloor \dfrac {L+R}2 \right\rfloor = L+\left\lfloor \dfrac {R-L}2 \right\rfloor 에서,

좌변은 L+R12\dfrac {L+R-1}2 가 되고, 우변은 L+RL12L+\dfrac {R-L-1}2 이되는데,

L+RL12=R+L12L+\dfrac {R-L-1}2 = \dfrac {R+L-1}2 가 되어 결국 양변이 같음이 보여진다.

Tags:

Categories:

Updated:

Comments