[Algorithm] 40강 : 구간 합(Interval) 빠르게 구하기

구간 합(Interval) 1.1 구간 합 문제 설명 구간 합 문제 : 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제 예를들어 5개의 데이터로 구성된 수열 10,20,30,40,50 이 있다고 가정 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 = 90 N개의 정수로 구성된 수열 M개의 쿼리 정보가 주어진다 각 쿼리는 Left와 Right로 구성 각 쿼리에 대하여 left, right 구간에 포함된 데이터들의 합을 출력 수행시간 제한은 O(N+M) 1.2 구간 합 빠르게 계산하기 접두사 합(Prefix Sum): 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것 접두사 합을 활용한 알고리즘은 다음과 같다 N개의 수 위치 각각에 대하여 접두..