q8514199   4년 전

음 간단한 문제라 생각했는데 96퍼에서 계속 틀리네여... 어디서 예외처리를 안한건지 아니면 코드자체가 방향이 틀린건지 모르겠네여 주석은 열심히 달았습니다. 한 번 읽어보시고 반례나 지적할 부분 있다면 해주세요

djm03178   4년 전

MAX의 값이 과연 충분할까요?

q8514199   4년 전

아! 충분하지 않네요 .. 그런데 MAX의 범위를 충분치 바꾸었는데 이번에는 시간초과가 나네요..

djm03178   4년 전

맥스만 바꾸면 mid를 계산할 때 오버플로우가 납니다.

q8514199   4년 전

오버플로우가 난다는 게 무슨 뜻인가요..?

코드는 r값에 MAX값을 2147483647로만 수정한 것입니다.

djm03178   4년 전

l이 10억이고 r이 MAX이면 l+r은 int가 표현할 수 있는 범위를 벗어납니다. 그러니 mid 역시 올바른 값을 가지지 못합니다.

q8514199   4년 전

하 결국 변수타입 문제이군요.. 정말 정말 감사합니다. 그런데 혹시 변수 타입이 제대로 설정되지 않은 경우 왜 시간초과가 발생하는지 알려주실 수 있나요..? 저는 시간초과의 원인은 반복문으로 인한 시간복잡도 증가밖에 없다고 생각했는데 그러지 않은가보네요

djm03178   4년 전

정확히 따져보지는 않았지만 mid가 잘못 계산되어 lo가 계속 올라가는 것이 반복되면 결국 lo도 MAX를 넘어서며 오버플로우가 되고, 그 때문에 lo가 hi보다 커지는 것이 아닌 오히려 음수로 가서 반복문이 계속 돌게 될 수 있어 보입니다.

그리고 오버플로우와 같은 undefined behavior는 무슨 결과를 일으켜도 원래 이상하지 않습니다. 전혀 예상하지 못한 방향으로 무한 루프에 빠지는 것도 충분히 가능합니다.

q8514199   4년 전

아아 감사합니다! 친절히 알려주셔서 큰 도움된 것 같습니다 

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