calculus   2년 전

문제 자체가 단순해서 반례랄께 따로 없긴 하지만,

몇 가지 간과할 수 있는 사실들이 있어서 댓글을 남겨봅니다.

1. ~(1<<31)의 고려

이 괴상한 숫자는 자연수 231-1 = 2147483647을 나타냅니다.

1 1

2147483647

이 입력될 경우, 2147483647을 출력해야 합니다.

이것도 답이 될 수 있으니,

이 킹갓 블로그 (https://www.acmicpc.net/blog/v...)를 참고해서 이진탐색으로 푸셨다면 (안하셨다면 참고 추천드립니다), 세 줄 요약의 1번조건을 잘 생각해보세요.

위의 예시는 이진탐색의 'hi'를 2147483647 등으로 해야 한다는 것, 그리고 애초에 그전에 2147483647이 답이 될 수 있는지부터 체크해야 함을 나타냅니다.

2147483647이 답이라면 Check(hi)도 Check(lo)와 같을 테니까요.

2. 오버플로우 발생 가능성 고려 (필자는 이것때문에 40-50퍼에서 틀렸어요...)

32비트 signed int형을 사용하셨다구요? 좋아요! 그렇게 해서 풀 수 있습니다! 저도 그렇게 풀었구요.

그런데 이진 탐색 과정에서 다음과 같은 연산을 한 번쯤 하셨을 겁니다.

int mid = (s+e)/2;

자, e는 2147483647이 될 수 있죠. 그리고 또 s도 거의 2147483646까지도 가능합니다!

중요한 점은 우리가 숫자를 더해서 오버플로우가 발생했다는 것입니다!

그리고 오버플로우가 일어날 때에는 s+e가 음수가 되고,

음수를 비트 right shift 연산을 때리면 가장 왼쪽 MSB(Most Significant Bit)가 0이 아니라 1이 된다는 것입니다!

한마디로 여러분의 연산결과가 음수가 된다는 뜻입니다.

그게 문제라는 것을 못 믿으시겠다구요? 아니, 걍 생각하면 MSB까지 shift될텐데, 뭐가 문제냐고요?

저도 못 믿어서 아래 C++ 코드를 돌려보니 저의 경우는 저렇게 나오네요...

cout << (-8>>1); // NOT 엄청난 '양수', but -4! => NOT 0 extend to MSB, but 1 extend! => 단순 (s+e)/2는 오버플로우 발생 가능!

이게 문제가 된다는 것을 깨닫고 오버플로우 문제를 해결하니 제 반례를 통과했습니다.

이제 아래 반례를 잘 참고하시고 (s+e)/2를 오버플로우 안나게 계산하는 방법을 한번 생각해보시기 바랍니다!

calculus   2년 전

참고로 저는 (s+e)/2를 ((s^e)>>1)+(s&e) 로 계산했습니다.

0과 1이 있는 자릿수 비트는 1로 만들어서 2로 나누고,

1이 겹치는 자릿수 비트는 2로 나눠도 그대로니까 그대로 더했어요.

이것 말고 또다른 방법을 사용하셨다면 댓글 한 번만 달아주세요!

zenith82114   2년 전

부호 있는 정수 타입의 overflow는 UB입니다. int 2개를 더해서 int의 최댓값을 넘어간다면 그때부터 확실하게 말할 수 있는 것은 아무것도 없습니다. 반드시 결과가 음수가 되는 것도 아니며, 그냥 에러가 나면서 터질 수도 있습니다.

khhandrea   2년 전

저는 (0.5 * s + 0.5 * e) 로 연산하는 방법 사용했습니다.

댓글을 작성하려면 로그인해야 합니다.