[알고리즘] 동적 계획법을 이용하여 구간합 구하기(Prefix Sum)

1. 구간합이란?

어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다.

 

2. 구간합 알고리즘

구간합 개념

고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법을 배웠다.

자연수 n에 대하여 수열 A(n)의 1 ~ n까지의 합을 S(n)이라고 할 때
두 자연수 a ~ b까지의 합은 S(b) - S(a-1)이다.

 

[증명]

a  <  b 인 두 자연수가 있을 때, 

 

S(b) = A(1) + A(2) + ... + A(a-1)  + A(a) + ... + A(b)

S(a-1) = A(1) + A(2) + ... + A(a-1)

이다.

 

이때 b까지의 합에서 a-1까지의 합을 빼면 1부터 a-1까지의 공통부분이 사라지므로 a부터 b까지의 구간합이 된다.

                                S(b) = A(1) + A(2) + ... + A(a-1)  + A(a) + ... + A(b)

  - S(a-1) = A(1) + A(2) + ... + A(a-1)

---

               S(b) - S(a-1) = A(a) + A(a+1) + ... + A(b) 

 

따라서 a ~ b 의 구간합은 S(b) - S(a-1)이다.

---

1) 완전 탐색

아이디어

일반적으로 원하는 구간의 합을 구할 때 반복문으로 직접 순회하며 구간의 합을 구할 수 있다.

 

예를 들어 다음과 같은 크기가 100인 배열 A(n)이 있을 때 50항부터 70항까지의 구간합을 구한다고 해보자.

A(n) = { A1, A2, A3, ... , A100 }

 

위의 구간합 개념대로 S(70) - S(49)를 계산하기 위해서  S(70)과 S(49)를 구한 뒤 S(70) - S(49)를 계산할 것이다.

S(70) = A(1) + A(2) + A(3) + ... + A(49) + ... + A(70)

S(49) = A(1) + A(2) + A(3) + ... + A(49)

S(70) - S(49) = A(50) + A(51) + ... + A(70)

 

만약 두 수 a와 b를 입력받고 a ~ b의 구간합을 구하는 경우라면 그 때의 입력받은 a, b에 따라서 S(a)부터 S(b) 직접 구해야 한다.

---

 

코드

코드로 구현하면 다음과 같다. 다음은 수열의 길이 N을 입력받고 a부터 b까지의 구간합을 구하는 알고리즘이다.

#include<iostream>

using namespace std;
int A[100];

int main(void) {
    int N, a, b;
    int Sa = 0;
    int Sb = 0;;
    cin >> a >> b;
	for (int i = 1; i <= N; i++) cin >> A[i];
	//S(b), S(a) 구하기
    for(int i=1; i<=b; i++) Sb += A[i];
    for(int i=1; i<a; i++) Sa += A[i];
    cout << Sb - Sa;
	return 0;
}

---

 

알고리즘 분석

위의 계산과정을 살펴보면

S(n)을 계산하는 동안 A(1) 부터 A(n) 까지  n번의 연산이 일어나고 이 과정을 n이 1 ~ n까지 반복한다.

 

따라서 위의 구간합을 구하는 알고리즘의 시간복잡도를 고려해보면 O(n²)이다.

---

 

2) 동적 계획법을 이용한 구간합 알고리즘

아이디어

동적 계획법(Danamic programming)을 이용하면 시간복잡도 O(n)으로 원하는 구간합을 구할 수 있다.

앞에서 구한 S(n)은 1부터 n까지 순차적으로 더하며 표현하였다.

S(n) = A(1) + A(2) + A(3) + ... + A(n)

 

하지만 S(n)은 다음과 같이 점화식으로 나타낼 수 있다.

S(n) = S(n-1) + A(n)   (단, 수열의 일반성을 위해 S(0) = 0으로 설정)

 

이를 이용하면 동적 계획법을 이용하여 원하는 구간의 합을 구할 수 있다.

정리하면 다음과 같다.

S(n-1)까지의 누적합을 구하는 배열을 따로 만들어 A(n)을 입력받을 때마다 S(n)을 구하여 업데이트해두면 된다.

S(n)들을 이렇게 미리 구해두면 S(n)이 필요한 순간에 1 ~ n을 돌며 추가연산을 하지 않고 바로 가져다 쓸 수 있게 된다.

---

알고리즘 순서

1. 1~n까지 A(n)을 입력받는다.
2. A(n)을 입력받음과동시에 점화식을 이용하여 S(n)을 업데이트시킨다.
3. 미리 구해놓은 S(n)을 이용하여 원하는 구간합을 구한다. 

---

 

시뮬레이션

동적 계획법을 이용하여 50항부터 70항까지의 구간합을 구하는 과정을 다시 살펴보자.

1. n = 70까지 A(n)을 입력받음과동시에 점화식을 이용하여 S(n)을 업데이트시킨다.
2. 미리 구해놓은 S(70)과 S(49)를 바탕으로 바로 50항부터 70항까지의 구간합을 구할 수 있다.

---

 

코드

코드로 구현하면 다음과 같다. 다음은 전의 코드를 동적 계획법을 이용하여 똑같이 구현한 구간합을 구하는 알고리즘이다.

#include<iostream>

using namespace std;
int S[100];

int main(void) {
    int N, a, b;
    int Sa = 0;
    int Sb = 0;;
    cin >> N;
    //A(n)입력과 동시에 S(n) 업데이트
	for (int i = 1; i <= N; i++) {
	    int Ai;
	    cin >> Ai;
	    S[i] = S[i-1] + Ai;
	}
	cin >> a >> b;
    cout << S[b] - S[a-1];
	return 0;
}

---

 

알고리즘 분석

이 알고리즘의 을 분석해보면,

구간합을 저장하는데 걸리는 시간 복잡도는 O(n)이고

구간합을 구하는 알고리즘은 O(1)이다.

---

 

3. 예제

https://wondrous-developer.tistory.com/46

[백준 2559번] 수열 (C++)

https://wondrous-developer.tistory.com/48

[백준 11659번] 구간 합 구하기 4 (C++)

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

4. 정리

구간합 알고리즘은 그 자체로 쓰이기보다 이분 탐색이나 두 포인터와 함께 쓰이는 경우가 많다. 따라서 구간합 알고리즘을 제대로 익혀두고 적재적소에 써먹을 수 있도록 하는 것이 중요하다.