알고리즘 자료구조 - 백준 11659번 구간 합 구하기

이번 문제는 구간 합을 사용하면 아주 쉽게 풀 수 있습니다.

구간합(또는 부분합)은 주어진 연속된 숫자 집합에서 특정 구간(일부 부분) 내의 숫자들을 모두 합한 값을 나타냅니다. 이것은 주어진 범위 내의 숫자들을 합계로 계산하는 데 사용되며, 다양한 응용 분야에서 유용합니다.

구간합을 계산하는 공식은 다음과 같습니다:

주어진 연속된 숫자 집합: `A = [a[0], a[1], a[2], ..., a[n-1]]`
구간합을 계산하고자 하는 구간: `[L, R]` (L은 시작 인덱스, R은 종료 인덱스)

구간 `[L, R]`의 합 (구간합)은 아래와 같이 계산됩니다:

Sum([L, R]) = a[L] + a[L+1] + a[L+2] + ... + a[R]

간단히 말하면, 시작 인덱스 `L`에서 종료 인덱스 `R`까지의 모든 숫자를 더하여 구간합을 구합니다.

구간합을 계산하는 주요 이점은 많은 경우 중복 계산을 피할 수 있다는 것입니다. 예를 들어, 동일한 구간 `[L, R]`의 합을 여러 번 계산해야 할 때, 한 번 계산한 결과를 저장하고 나준 다시 사용함으로써 계산 효율성을 향상시킬 수 있습니다.

구간합은 알고리즘 및 데이터 구조에서 자주 활용되며, 특히 배열, 리스트 또는 트리 데이터 구조에서 구현됩니다. 주어진 구간의 합을 빠르게 계산하기 위한 여러 알고리즘과 자료구조가 존재하며, 이러한 구간합을 이용하여 다양한 문제를 효과적으로 해결할 수 있습니다.

아래는 구간합을 python 코드를 사용하여 구현한 결과입니다.

import sys
input = sys.stdin.readline
n = input()
number = input().split()
sum_n = [0]
n1 = 0
for j in number :
    n1 += int(j)
    sum_n.append(n1)

for i in range(int(n.split(' ')[1])):
    x = input()
    minus1 = int(x.split(' ')[0])-1
    plus1 = int(x.split(' ')[1])
    print(sum_n[plus1] - sum_n[minus1])