[알고리즘] 백준 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의 방식은 크게 '탑다운', '바텀업' 두 가지 방식으로 나뉜다.
다음 포스팅에서 이 두 가지의 차이점에 대해 알아봐야겠다.