[2021/08/11][짤막한 이야기 - 구간합]

[2021/08/11][짤막한 이야기 - 구간합]

“구간합(Prefix Sum)”이란 자료구조에 나열된 숫자들 중 일부 구간에 대하여 합을 구하는 방법이다.

예를 들어, 위 그림에서 A 배열의 2~4번째 구간합을 물어본다면 10(=7+2+1)을 답하면 되는 것이다.

최악의 경우에도 자료구조 내 모든 데이터를 1번씩만 확인하며 합을 더해나가면 되기 때문에 10의 시간을 초과하지 않는다.

그런데 질문의 개수가 많아지면 이야기는 달라진다.

자료구조의 데이터 개수(N)가 10개이지만 질문의 개수(Q)가 1억개가 주어진다면, 최악의 경우 10억(N*Q)만큼의 시간이 소요되는 것이다.

이 경우는 약 10초가 소요된다.

만약 데이터 개수가 최대 1만개이고 질문의 개수가 최대 10만개인 경우에도 10초보다 적게 소요될 수 있을까?

이는 구간합을 미리 배열로 추가하여 만들어두면 가능하다.

위 그림에서 SumA 배열은 지금까지의 합을 저장하고 있다.

즉, A 배열의 2~4번째 구간합을 물어본다면 SumA[4] - SumA[1](=10)을 답하면 되는 것이다.

배열의 특정 원소로 접근하는 시간은 1이기 때문에 어떠한 구간합을 물어보더라도 2의 시간을 초과하지 않는다.

즉, 질문이 최대로 들어오더라도 전체 연산은 최대 20만(약 0.002초)을 넘지 않을 것이다.

그런데 만약 A 배열내의 숫자가 변경될 수 있다면 어떻게 될까?

[관련된 짤막한 이야기 - 시간 복잡도[2021/08/04]]

#이야기 #루니프 #알고리즘 #구간합 #시간복잡도

 

[2021/08/11][Short Story - Prefix Sum]

“Prefix Sum” is a method of finding the sum of some intervals among the numbers listed in the data structure.

For example, if I ask for the sum of the 2nd to 4th sections of the A array in the figure above, you can answer 10(=7+2+1).

Even in the worst case, it does not exceed 10 times because all data in the data structure is checked only once and the sum is added.

However, as the number of queries increases, the story changes.

If the number of data structures ( N) is 10, but the number of queries (Q) is 100 million, in the worst case, it will take 1 billion (N*Q) time.

So in this case it takes about 10 seconds.

If the number of data is up to 10,000 and the number of queries is up to 100,000, can it take less than 10 seconds?

This can be done by adding the interval sum to an array in advance.

In the figure above, the SumA array stores the sum.

That is, if I ask for the sum of the 2nd to 4th sections of the A array, you can answer SumA[4] - SumA[1](=10).

Since the time to access a specific element of the array is 1, it does not exceed the time of 2 no matter what interval sum is asked.

That is, even with the maximum number of queries, the total operation will not exceed the maximum of 200,000 (about 0.002 seconds).

But what if the numbers in the A array could be changed?

[Related Short Story - Time Complexity[2021/08/04]]

#Story #LootNiP #Algorithm #PrefixSum #TimeComplexity