[BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘

[BOJ 알고리즘, C++] #11659_구간 합 구하기 4, Prefix Sum(누적 합) 알고리즘

 

BOJ 알고리즘 문제 풀이, 11659_구간 합 구하기 4

누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제

 

 

---

 

문제

출저: https://www.acmicpc.net/problem/11659

풀이 과정

 

위 문제를 해결하기 위해 우리는 누적 합 알고리즘 두 가지를 선행할 필요가 있습니다.

 

1. 구간 합 (Prefix Sum)
2. 투 포인터(Two Pointers)

 

Prefix Sum, 구간 합

/*
    1. Prefix Sum을 계산하여 배열에 저장합니다.
    2. i(left bound) ~ j(right bound) 구간의 합은 array[r] - array[l-1] 입니다.
*/

#include <iostream>
using namespace std;

constexpr size_t n = 5;

int main()
{
	// 총 5개의 수를 갖는 수열
	int arr[n] = { 10, 20, 30, 40, 50 };

	// 누적 합을 저장할 prefixSum 배열
	int prefixSum[n + 1] = { 0, };

	for (size_t i = 1; i <= n; i++)
	{
		prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
	}

	int l = 1, r = 3;
	
    // 첫 번재 ~ 세 번째 구간의 누적 합
	cout << prefixSum[r] - prefixSum[l - 1] << endl;
}

// 결과 값: 60 == 10 + 20 + 30

"구간 합" 알고리즘은 간단합니다.

먼저, 수열의 시작점 부터 마지막까지 누적합을 별도의 배열에 저장합니다.

주어진 l(left bound) ~ r(right bound) 구간의 누적 합은 "arr[r] - arr[l-1]"으로 계산합니다.

 

투 포인터, Two Pointers 

#include <iostream>
using namespace std;

// 수열이 갖는 수의 개수 N, 주어진 구간 합 M
constexpr int N = 5 , M = 50;

int main()
{
	// 주어진 수열
	int arr[N] = { 10, 20, 30, 40, 50 };

	int start = 0, end = 0;
	int tmpSum = 0;
	int res = 0;

	// END 포인터를 기준으로 While문 진행.
	while (end <= N)
	{
		// 1. 임시 누적 합이 목표 누적 합보다 크다면 START 포인터를 증가
		if (tmpSum >= M)
			tmpSum -= arr[start++];
		// 2. 임시 누적 합이 목표 누적 합보다 작다면 END 포인터를 증가
		else if (tmpSum < M)
			tmpSum += arr[end++];
		
		// 진행 중 임시 누적합이 목표 누적합과 같은지 체크합니다.
		if (tmpSum == M)
			++res;
	}

	cout << res << endl;
}

 

"투 포인터" 알고리즘 또한 간단합니다.

 

1. 시작 점(START)과 끝(END) 점을 수열의 첫 번째 원소를 가리키도록 합니다.

2. 현재 임시 구간 합이 M과 같다면 카운트합니다.

3. 현재 임시 구간 합이 M보다 작다면 END를 증가시킵니다.

4. 현재 임시 구간 합이 M보다 크다면 START를 증가시킵니다.

 

정리하자면, 현재의 구간 합을 기준으로 START 포인터를 증가 시킬것인지, END 포인터를 증가시킬 것인지 결정하는 알고리즘입니다.

 

코드 작성

#include <iostream>
using namespace std;
typedef long long ll;

ll preSum[100001] = {0,};

int main()
{
    // 수행 시간 감소를 위한 라인
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;

    int tmp;
    for(int i=1; i<=N; i++)
    {
        cin >> tmp;
        preSum[i] = preSum[i-1] + tmp;
    }
    
    for(int i=0; i<M; i++)
    {
        // 구간의 첫 번째, l(left) + 구간의 마지막, r(right)
        int l, r;
        cin >> l >> r;
        cout << preSum[r] - preSum[l-1] << "\n";
    }
}