[이것이 코딩 테스트다 with Python]_40_구간 합 빠르게 계산하기

220216 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=kqyHnoriStk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=40 

 

 

 

 

 

 

 

1. 구간 합 (interval sum)

: 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제

 

1) N개의 정수로 구열된 수열

2) M개의 쿼리 정보 주어짐

- 각 쿼리는 LEFT, RIGHT 으로 구성

- 각 쿼리에 대하여 [LEFT, RIGHT] 구간에 포함된 데이터들의 합 출력

3) O(N+M)

 

 

 

2. 접두사 합 (Prefix sum)

: 배열의 맨 앞부터 특정 위치까지의 합 미리 구하기

- N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장

- 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[RIGHT] - P[LEFT - 1]

 

 

 

 

 

 

 

• python

# 데이터의 개수 N과 전체 데이터 선언
n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산 (세 번째 수부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])

3, 4 번째 합

• c++

#include <bits/stdc++.h>

using namespace std;

int n = 5; // 데이터의 개수 N과 데이터 입력받기
int arr[] = {10, 20, 30, 40, 50};
int prefixSum[6];

int main() {
    // 접두사 합(Prefix Sum) 배열 계산
    int sumValue = 0;

    for (int i = 0; i < n; i++) {
        sumValue += arr[i];
        prefixSum[i + 1] = sumValue;
    }

    // 구간 합 계산(세 번째 수부터 네 번째 수까지)
    int left = 3;
    int right = 4;
    cout << prefixSum[right] - prefixSum[left - 1] << '\n';
}

• java

import java.util.*;

class Main {
    public static int n = 5; // 데이터의 개수 N과 데이터 입력받기
    public static int arr[] = {10, 20, 30, 40, 50};
    public static int[] prefixSum = new int[6];

    public static void main(String[] args) {
        // 접두사 합(Prefix Sum) 배열 계산
        int sumValue = 0;

        for (int i = 0; i < n; i++) {
            sumValue += arr[i];
            prefixSum[i + 1] = sumValue;
        }

        // 구간 합 계산(세 번째 수부터 네 번째 수까지)
        int left = 3;
        int right = 4;
        System.out.println(prefixSum[right] - prefixSum[left - 1]);
    }
}