[Algorithm] 동적 프로그래밍 익히기 - 1
동적 프로그래밍을 설계하는 데 있어서, 가장 먼저 고려해야 할 것은 변수 간의 규칙성이다.
규칙을 찾아 점화식을 작성할 수 있게 되면, 가장 간단한 코드 작성으로도 답은 구할 수 있는 상황이 된다.
여기에서 추가적인 최적화(불필요한 연산 제거)를 통해서 시간을 단축할 수 있다.
즉, 메모이제이션(Memoization)을 통해서 연산이 중복되는 것을 방지해야 한다.
1. 점화식
2. 메모이제이션
3. 더 최적화할 방법 찾기
1번을 만족시키게 되면, 완전 탐색(Brute-force)으로 볼 수 있고,
1번과 2번을 모두 만족시켜야 동적 프로그래밍(Dynamic Programming)이라고 볼 수 있다.
추가로 어려운 문제의 경우, 3번까지 활용해야 제한 시간 내에 해결할 수 있다.
https://www.acmicpc.net/problem/14501
DP(Dynamic Programming)를 연습할 수 있는 문제이다.
위의 문제를 풀다가, 재귀로 푸는 방법은 쉽게 떠올랐으나 반복문으로 푸는 방법이 바로 떠오르지 않아서 여러 코드를 분석해보았다.
여러 가지 방법이 있겠지만, 시간복잡도와 이해하기 쉬운 코드를 기준으로 선별하였다.
풀이 방법에 따라 어떤 변수를 고려하고, 어떻게 접근해야 하는지 생각해볼 수 있겠다.
0. 점화식
i번을 선택하지 않을 경우 : f(i + 1)
i번을 선택하는 경우 : f(i + t(i)) + p(i)
f(i) = max(f(i + 1), f(i + t(i)) + p(i)) (i <= n)
f(i) = 0 (i > n)
1. 재귀적인 방법
int n, d[16], t[16], p[16]; int f(int index) { if (index == n) return 0; if (index > n) return INT_MIN; if (d[index] != -1) return d[index]; int &ret = d[index]; return ret = max(f(index + 1), f(index + t[index]) + p[index]); } int main() { memset(d, -1, sizeof(d)); cin >> n; for (int i = 0; i < n; ++i) cin >> t[i] >> p[i]; cout << f(0); }
int n, d[16], t[16], p[16]; int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> t[i] >> p[i]; for (int i = n - 1; i >= 0; --i) { if (i + t[i] <= n) d[i] = p[i] + d[i + t[i]]; d[i] = max(d[i], d[i + 1]); } cout << d[0]; }
int n, d[16], t[16], p[16]; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> t[i] >> p[i]; for (int i = 0; i < n; i++) { d[i + 1] = max(d[i + 1], d[i]); if (i + t[i] <= n) d[i + t[i]] = max(d[i + t[i]], d[i] + p[i]); } cout << d[n]; }
댓글
댓글 쓰기