1480. Running Sum of 1d Array

출처 : https://leetcode.com/problems/running-sum-of-1d-array/

사실 이 문제는 너무 쉬워서 설명할 것도 없지만,

최적화된 알고리즘을 위해, 생각해보아야 할 점을 몇 가지 짚어보겠다.

[ Stage 1]

기본이다. Sum list라는 Vector에 숫자를 더해서 
Sum_list[i] = Sum_list[i-1] + num[i] 라는 기본 점화식을 바탕으로 풀었다.
Runtime: 14 ms

[Stage 2]

Vector 라는 container는 기본적으로 Push_back 이라는 함수를 제공해주고, Memory에 allocate되는 사이즈가 불명확하다.
그래서 필요 이상의 메모리를 잡고 있다. 따라서 array를 사용할 수 있다면 이 문제에서는 array를 사용하는 것이 맞다.
하지만 return type이 vector이기에 억지로 vector를 써줬다. 

하지만 우리는 nums.size()를 통해 할당될 벡터의 크기를 알기에, 할당을 해준다. 우리는 Push back이라는 function을 call해서 element를 더하는 방식을 사용하지 않고, 인덱스를 통해 직접 접근한다.
Runtime: 7 ms
런타임이 2배가량 빨라졌다.

[stage 3]

nums.size()를 두번 호출하는 것을 피한다.
Runtime: 3 ms

 

다른 알고리즘으로 이렇게 하나의 ans를 업데이트하는 방식이 있다.

하지만, 내가 실험해본 바로는 더 느리다. 왜냐면, 두번의 지정 연산자 (=) 가 수행됬기 때문이며, ans 라는 variable을 유지해주어야하기 때문에 메모리 측면에서도 좋지 않다.