중앙값 구하기의 Overflow
우리가 특정 문제에서 ⌊2L+R⌋ 의 값을 구해주어야 할 때, L+R 은 overflow가 날 수도 있는 상황이 있을 수 있다.
안전한 공식
이 때, ⌊2L+R⌋=L+⌊2R−L⌋ 라는 사실을 이용하여 overflow를 피해줄 수 있다.
⌊⌋ 이 없다면 저 식은 실수에서 성립하는데 정수에서도 성립할까?
1. L+R 이 짝수일 때,
R−L 도 짝수이다. R과 L이 모두 짝수일 때는 자명하고 R과 L이 모두 홀수일 때도 옳다.
따라서 ⌊⌋ 에 영향을 받지 않으므로 식이 성립한다.
2. L+R이 홀수일 때,
R−L 도 홀수이다. 위와 비슷한 방식으로 유도할 수 있다.
⌊2L+R⌋=L+⌊2R−L⌋ 에서,
좌변은 2L+R−1 가 되고, 우변은 L+2R−L−1 이되는데,
L+2R−L−1=2R+L−1 가 되어 결국 양변이 같음이 보여진다.
Comments