<div id="readability-page-1" class="page"><div aria-label="Content">
 <article itemscope="" itemtype="http://schema.org/BlogPosting">

 

 <div itemprop="articleBody">
 Reference: <a href="https://youtu.be/ZMOFmHBVEcg">Range Sum Querying - Prevent Repeated Work with Chaching</a>



캐싱을 통해 범위 동안의 Sum 값을 구한다.

이 방법이 가진 가장 큰 장점은, 캐싱 작업을 통해 한 번 진행하였던 계산은 이후에 다시 진행하지 않아도 된다는 점에 있다.

간단한 코드로 살펴보자.

<div><pre><code>function solution(arr) {
 let result = new Array(arr.length + 1).fill(0);

 for (let i = 1; i &lt; result.length; i++) {
 result[i] = arr[i - 1] + result[i - 1];
 }

 // rest of the code
}
</code></pre></div>

기본적으로 식은 <code>cache[i] = cache[i - 1] + array[i - 1]</code>을 계산한다고 생각하면 된다.

이 방식으로 계산을 하면, 이후부터는 기존의 <code>array</code>가 아닌, <code>cache</code> 배열만으로 계산을 진행할 수 있다.

예를들어, 아래와 같이 계산한다고 가정해보자.

<div><pre><code>function solution(arr, start, end) {
 let result = new Array(arr.length + 1).fill(0);

 for (let i = 1; i &lt; result.length; i++) {
 result[i] = arr[i - 1] + result[i - 1];
 }

 return result[end] - result[start];
}
</code></pre></div>

 </div>
 
 
</article>

 </div></div>

immigration9

Reference: Range Sum Querying - Prevent Repeated Work with Chaching
Range Sum Querying
캐싱을 통해 범위 동안의 Sum 값을 구한다.
이 방법이 가진 가장 큰 장점은, 캐싱 작업을 통해 한 번 진행하였던 계산은 이후에 다시 진행하지 않아도 된다는 점에 있다.
간단한 코드로 살펴보자.
function solution(arr) {
 let result = new Array(arr.length + 1).fill(0);
 for (let i = 1; i < result.length; i++) {
 result[i] = arr[i - 1] + result[i - 1];
 }
 // rest of the code
}
기본적으로 식은 cache[i] = cache[i - 1] + array[i - 1]을 계산한다고 생각하면 된다.
이 방식으로 계산을 하면, 이후부터는 기존의 array가 아닌, cache 배열만으로 계산을 진행할 수 있다.
예를들어, 아래와 같이 계산한다고 가정해보자.
function solution(arr, start, end) {
 let result = new Array(arr.length + 1).fill(0);
 for (let i = 1; i < result.length; i++) {
 result[i] = arr[i - 1] + result[i - 1];
 }
 return result[end] - result[start];
}

Range Sum Querying: Dynamic Problem

댓글