kjs89271s   2년 전

현재 이 소스를 채점하면 맞는 코드라고 나옵니다. 하지만 for문 안의 var<=2200000000 을 2110000000으로 변경하면 시간초과로 틀렸다고 나옵니다.

분명 22억이 더 큰 범위인데도 시간초과가 나오지 않고 정답처리 되는 것은 왜 그런건가요

djm03178   2년 전

사실 이런 코드가 통과되면 안 되는데... 컴파일러가 어둠의 최적화를 한 것 같습니다.

22억 번이나 루프를 돌리는 게 0ms가 될 수가 없습니다. 그럼에도 그런 일이 벌어졌다는 건, 애초에 컴파일러가 이 루프 자체를 제거하고 이 루프의 동작을 O(1)으로 줄여내는 최적화를 수행한 거라고 보여지네요.

22억이라는 수 자체가 int의 범위를 벗어나 루프를 제대로 돌릴 수 없어서 그런 시도를 한 것 같습니다. 반면 2110000000은 int 범위에 들어오기 때문에 그냥 루프를 돌린 것 같고요.

kjs89271s   2년 전

@djm03178

저도.. 뭔가 이상해서;; 이 문제의 질문글들을 보면 반복문을 사용하면 시간초과가 떠야하는 것이 당연한데.. 왜 이러나 싶어 궁금해서 질문글을 올렸었습니다. 감사합니다

djm03178   2년 전

그리고 결과를 볼 때에는 단순히 통과 / 시간 초과로만 나눌 게 아니라 구체적인 시간을 같이 보는 게 좋습니다. 통과는 코드는 0ms기 때문에, 4ms 단위로 측정되는 시간상 문제의 시간 제한인 0.35초 = 350ms와는 수백 배의 차이가 나는 시간입니다. 이건 단순히 루프를 조금 더 / 덜 도는 정도로 극복될 정도가 아니므로, 무한 루프 혹은 컴파일러의 최적화의 차이를 만들어냈다고 추정할 수 있습니다. 만일 통과된 코드가 350ms에 가까웠다면 실행 시마다의 오차 때문에 차이가 생겼다고 추측할 수 있습니다.

kjs89271s   2년 전

@djm03178 좋은 정보 감사합니다

kjs89271s   2년 전

@djm03178

이렇게까지 자세히 설명을 해주실줄;;감사합니다;; 

아직 c초입이라 적어주신 모든게 지금당장 한번에 정확하게 이해되진 않지만, 몇 번 읽어보면 이해될 것 같아요 감사합니다

djm03178   2년 전

수정하던 과정에서 실수로 지웠는데, @Green55 님과 https://godbolt.org/ 에서 실험한 내역이었습니다.

djm03178   2년 전

추가로 @yclock 님께서 보충해주셔서 다시 정리합니다.

1. 루프가 22억까지 돌 때에는 루프의 조건이 항상 참이기 때문에 (int의 값이 아무리 커도 2147483647을 넘을 수 없으므로) break를 하지 않고 루프를 탈출할 수가 없습니다. Side effect가 없는 무한루프는 그 자체로 undefined behavior이기 때문에, 이런 경우 컴파일러는 일반적으로 루프 내의 탈출 조건에서 승부를 본다고 생각하고 최적화를 수행합니다. 그래서 else if 부분이 O(1)짜리 공식으로 바뀌어버린 것입니다. 따라서 이는 루프가 도는 범위를 2147483647로 줄일 때까지도 최적화가 발생했고, 2146483646일 때에는 최적화가 되지 않았습니다.

2. var의 자료형을 long long으로 바꾸면 이러한 undefined behavior가 사라집니다. 하지만 a, b, c는 모두 int이므로 a/(c-b)가 2147483647보다 클 수 없음이 자명합니다. 따라서 var가 2147483648를 넘어서 루프를 도는 일은 발생하지 않을 것이므로, 루프를 도는 범위가 2147483648일 때에도 최적화가 되었습니다. 하지만 이 경우 2147483647까지 루프를 돌릴 때 최적화가 되지 않았습니다. 왜냐하면, 예를 들어 a=2147483647, b=1, c=2인 경우 2147483647까지 루프를 돌리는 것만으로는 아무런 출력을 하지 않아야 하기 때문입니다.

3. 결론적으로, 컴파일러는 "루프 내에서 반드시 답을 찾고 나온다"는 결론을 내렸을 때 최적화를 수행합니다. 그래서 이와 같이 undefined behavior가 발생하면 도중 if나 else if 둘 중 하나에는 걸린다고 판단하고 한 번에 계산하는 식으로 바꾸어버린 것입니다.

kjs89271s   2년 전

@djm03178 감사합니다!! 그런데 내용중 "그래서 else if 부분이 O(1)짜리 공식으로 바뀌어버린 것" 이라는 말에서 O(1)이라는 것이 "1번 실행하는" 의 의미인가요? 정확히 무엇을 의미하는지 알 수 있을까요

djm03178   2년 전

시간 복잡도에 대해 알아보시면 좋을 것 같습니다. 간단히 말하면 이 문제의 답은 -1이 아니면 그냥 a/(c-b)+1이라는 것입니다.

djm03178   2년 전

a/(c-b)+1이라는 답을 구하기 위해 굳이 루프를 돌릴 필요가 없음을 컴파일러가 깨닫고 답을 한 번에 계산해버린 것입니다.

kjs89271s   2년 전

@djm03178

감사합니다

djm03178


voltage 로 혼내줘야됨 ㅋㅋㅋ

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