카테고리 없음
6.26 코테 일지 (값의 크기와 연산 시간의 관계)
코테챌린져
2024. 6. 26. 23:52
백준 1788 피보나치 수의 확장
- 시간 복잡도 뿐만이 아닌 계산되는 값들의 크기도 시간에 영향을 준다.
for _ in range(temp_n-1) :
temp = second
second = ( second + first )
first = temp
if (n<0 and n % 2 == 0) :
print(-1)
else :
print(1)
print(second % 1000000000 )
처음 작성했던 코드이다. 분명히 피보나치를 반복적 방식으로 풀어 시간 복잡도가 O(n)이지만 시간 초과가 됐다.
처음에는 알고리즘의 문제라 생각해 캐쉬를 사용하는 반복적 동적 계획법으로 풀이 해봤으나 여전히 시간 초과가 됐다.
피보나치 함수의 일반항이 있다고 하여 사용해봤으나 n이 커지면 n제곱의 값이 너무 커져 오버플로우가 일어나 런타임에러가 떳다. (사실 n이 커지면 실제 값과 조금씩 차이가 나기 시작해 오버플로우가 아니더라도 틀렸습니다가 떳을 것이다)
답
답은 간단히 마지막 second에서 1000000000으로 나머지를 찾는 것이 아닌 피보나치를 계산할때 매번 나머지를 계산하고 그것을 저장하는 것 이었다. 이러면 for문 안에 매번 나머지를 찾는 연산이 추가 돼 시간이 오히려 늘어날 것이라 오해할 수 있으나, 매번 덧셈과 변수에 저장을 할 때 큰 값으로 하는 것보다, 작은 값으로 연산을 하게 됨으로써 시간이 굉장히 줄어든다. 즉, 시간 복잡도 뿐만이 아닌 계산되는 값들의 크기도 시간에 영향을 준다.
참고
피보나치 수열 알고리즘을 해결하는 5가지 방법