[알고리즘] 백준 11659번: 구간 합 구하기 4 (C++), DP 개념

이 문제를 직관적으로 풀었을 때는 시간 초과가 발생한다. 구간이 예를 들어 1~100,000이고, 합을 구하는 횟수가 1~100,000이라면 어마한 양의 시간이 발생하기 때문에 다른 방법을 생각해내야 한다.

---

DP (Dynamic Programming) 개념

DP란 큰 문제를 해결하기 위해 작은 문제들로 나누어 작은 문제들을 해결하여 큰 문제들 해결할 수 있도록 도와주는 알고리즘이다.

 

예를 들어 피보나치 수가 DP의 대표적인 문제라고 할 수 있다.

피보나치 4를 구한다고 생각해보자.

일반적으로 코드는 이렇게 짤 것이다.

#include <iostream>
using namespace std;

int fibo(int n) {
	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	else {
		return fibo(n - 1) + fibo(n - 2);
	}
}

int main() {
	int n;
	cin >> n;
	cout << fibo(n);

	return 0;
}

피보나치 4를 구하는 과정에서 fibo(2)가 두 번 호출된다.

'겨우 2번인데 DP를 배워야 하나'라고 생각할 수 있지만 이건 아주 극단적으로 작은 예이다. 피보나치 100,000을 구한다고 하면 피보나치 2가 몇 번 수행되고, 피보나치 3이 몇 번 수행되고를 생각한다면 엄청 낭비적인 코드구나 라고 생각할  수 있다.

 

한 번 호출된 값은 어디에 저장해 두고 다시 부를 때 함수를 호출하지 않고, 저장된 값을 가져온다면 어떨까?

그렇게 되면 더 효율적인 코드를 만들 수 있다.

이 기법을 메모이제이션(Memoization)이라고 한다.

 

이 메모이제이션을 코드로 나타내면 이렇다.

#include <iostream>
using namespace std;

int cache[46];

int fibo(int n) {
	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	else {
		if (cache[n] != 0) {
			return cache[n];
		}
		else {
			return cache[n] = fibo(n - 1) + fibo(n - 2);
		}
	}
}

int main() {
	int n;
	cin >> n;
	cout << fibo(n);

	return 0;
}

cache라는 배열에서 피보나치 2가 한 번 호출되었다면 cache의 역할이 '아직 구하지 않았으니 한 번이라도 구해두면 내가 알아두고 나중에 귀찮게 함수 호출 안 하게 해 주겠다'라고 생각할 수 있다.

 

[그림으로 이해]

 

---

점화식

DP가 어떻게 돌아가는지 알았다면 DP에서 제일 중요한 점화식을 알아야 한다.

점화식이란 '수열의 항(項) 사이에 성립하는 관계식' (출처: 위키백과)라는 것이다.

말 그대로 '피보나치 N'을 구한다고 했을 때, 점화식은

fibo(N) = fibo(N - 1) + fibo(N - 2)

라는 관계식이라 볼 수 있다.

fibo(N)이라는 큰 문제를 fibo(N - 1)과 fibo(N - 2)로 나누어 작은 문제들을 풀어가며 최종적으로 큰 문제를 해결해나가는 것을 볼 수 있다.

 

즉, DP에서 가장 중요하다고 생각하는 것이 '큰 문제가 무엇인지 > 어떻게 작은 문제로 분할할지 (점화식을 세울지)'가 중요한 포인트가 될 거 같다.

---

다시 문제로 돌아와서

이번 문제는 위에서 말한 대로 직관적으로 풀었다가는 시간 초과가 발생한다.

그렇다면 이런 풀이는 어떨까?

cache 배열에 1번째 항부터 N번째 항까지 담고, 어떠한 구간 a와 b가 주어지면 'cache[b] - cache[a - 1]'을 통해 구할 수 있지 않을까?

 

큰 문제:

a~b구간까지의 합

작은 문제:

1~a-1구간까지의 합, 1~b구간까지의 합

 

[코드]

#include <iostream>
#include <vector>
using namespace std;

int cache[100001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);


	int n, m;
	cin >> n >> m;
	vector<int> arr(n + 1, 0);
	
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		arr[i] = a;
		cache[i] = a + cache[i - 1];
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		cout << cache[b] - cache[a - 1] << '\n';
	}

	return 0;
}

---

이번 문제를 통해 DP가 무엇인지 어떻게 돌아가는 알고리즘인지 알 수 있었다.

DP의 방식은 크게 '탑다운', '바텀업' 두 가지 방식으로 나뉜다.

다음 포스팅에서 이 두 가지의 차이점에 대해 알아봐야겠다.