컴파일러가 go 함수를 똑같은 인자로 호출하는 것이 똑같은 결과를 반환할 것을 알고 자체적으로 최적화를 한 거라고 생각됩니다.
1629번 - 곱셈
코드를 어디에서 올려보셨는지 모르겠지만 최적화 기법은 컴파일러마다 다르기 때문에 어느 한 곳에서 최적화가 이루어지지 않았다고 해서 다른 곳에서도 되지 말라는 법은 없습니다.
정말로 b값에 비례에서 호출이 일어났다면 말씀하신 대로 10^18이면 안 돌아야겠지만, 채점 환경과 유사한 환경에서 잘 돕니다. https://ideone.com/2RS6Gf
물론 호출이 실제로 있는데도 실행을 하지 않는 것이 일반적으로는 위험할 수 있으나, 이 함수의 경우 실행 범위가 명확하고 정적 분석을 통해 충분히 이 함수 내부를 벗어나지 않고 결정적인 연산이 이루어진다고 판단할 수 있기 때문에 최적화가 가능합니다.
https://cpp.godbolt.org/z/inl6...
-O2 옵션에서 함수 호출을 한 번으로 줄이는 최적화가 이루어졌음을 확인했습니다.
"순수 함수" (함수 외부에 영향을 미치지 않는 함수) 라는 것을 파악할 수 있으면 이런 종류의 최적화는 가능하다고 생각합니다.
댓글을 작성하려면 로그인해야 합니다.
lwh1992 4년 전 1
저는
9번째 줄에 if (b % 2 == 0) return (go(a, b / 2, c)%c * go(a, b / 2, c)) % c;을 할때 앞뒤에 go함수가 같기때문에 시간초과가 발생할 거라고 생각했는데 통과가 되서 여쭤보려 합니다.
memoization을 안해도 되는건지 알려주시면 감사하겠습니다.