[ALGORITHM STUDY] Dynamic Programming (DP, 동적계획법)

피보나치

#include <cstdio> #include <vector> using namespace std; vector<int> dp; int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; // 이미 값을 계산한 적이 있다면 그 값을 바로 리턴 if (dp[n] != -1) return dp[n]; // 아니라면 계산해서 dp 리스트에 넣어 보존 dp[n] = fibonacci(n - 2) + fibonacci(n - 1); return dp[n]; } int main() { int N; scanf("%d", &N); dp.resize(N + 1, -1); // 초기값 -1은 fibonacci 결과로 절대 나올 수 없는 값 printf("%d\n", fibonacci(N)); } // [출처] 동적 계획법(Dynamic Programming) | 작성자 라이

9465 스티커 : https://www.acmicpc.net/problem/9465

#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; int sticker_count; vector<vector<int>> sticker, cache; /* status 0 : 아무 스티커도 떼지 않음 status 1 : 위쪽 스티커를 뗌 status 2 : 아래쪽 스티커를 뗌 */ int DP(int status, int index2) { if (index2 >= sticker_count) return 0; if (cache[status][index2] != -1) return cache[status][index2]; int result = DP(0, index2 + 1); if (status != 1) result = max(result, DP(1, index2 + 1) + sticker[0][index2]); if (status != 2) result = max(result, DP(2, index2 + 1) + sticker[1][index2]); return cache[status][index2] = result; } int main() { int for_count; cin >> for_count; while (for_count--) { cin >> sticker_count; sticker = vector<vector<int>>(2, vector<int>(sticker_count, 0)); cache = vector<vector<int>>(3, vector<int>(sticker_count, -1)); for (int j = 0; j < 2; j++) { for (int k = 0; k < sticker_count; k++) cin >> sticker[j][k]; } cout << DP(0, 0) << endl; } }

2579 계단 오르기 : https://www.acmicpc.net/problem/2579

#include <iostream> #include <algorithm> #include <vector> #include <fstream> using namespace std; int main() { ifstream fcin; fcin.open("2579_input.txt"); int stair_count; fcin >> stair_count; vector<int>stair = vector<int>(stair_count+1); vector<vector<int>>DP = vector<vector<int>>(stair_count+1, vector<int>(2, 0)); for (int n = 0; n < stair_count; n++) fcin >> stair[n]; DP[1][0] = stair[0]; DP[1][1] = 0; if (stair_count >= 2) { DP[2][0] = stair[0] + stair[1]; DP[2][1] = stair[1]; } for (int n = 3; n <= stair_count; n++) { DP[n][0] = DP[n - 1][1] + stair[n - 1]; DP[n][1] = max(DP[n - 2][0], DP[n - 2][1]) + stair[n - 1]; } cout<< max(DP[stair_count][0], DP[stair_count][1])<<endl; system("pause"); }

계단 오르기에는 규칙이 있다.

1. 한 칸을 연속으로 세 번 오를 수 없다.

2. 한 번에 한 칸 두 칸씩 움직일 수 있다.

3. 맨 마지막 계단에 도달해야한다.

그렇다면 규칙이있다.

먼저 한 칸을 올랐을 때

1. 두칸을 움직이고 한칸을 가는 방법

이 있다.

두 칸을 올랐을 때는

1. 한 칸을 오른 후에 두칸을 오르는 방법

2. 두 칸, 두 칸을 오르는 방법이 있다.

코드를 보면 맨 처음이 DP[n][0]이 한칸을 올랐을 때 이고

                         DP[n][1]이 두칸을 올랐을 때라는 것을 알 수 있다.

참고 : https://lyzqm.blogspot.kr/2017/03/2579.html

11053 가장 긴 증가하는 부분 수열 : https://www.acmicpc.net/problem/11053

#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; vector<int>num,cache; int main() { int num_count; cin >> num_count; num = vector<int>(num_count); cache = vector<int>(num_count); for (int j = 0; j < num_count; j++) cin >> num[j]; int result = 0; for (int j = 0; j < num.size(); j++) { int max_num = 0, index = 0; while (index >= 0 && index < j) { if (num[index] < num[j]) max_num = max(cache[index], max_num); index++; } cache[j] = max_num + 1; result = max(result,cache[j]); } cout << result << endl; }

11722 가장 긴 감소하는 부분 수열 ; https://www.acmicpc.net/problem/11722

#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; vector<int>num, cache; int main() { int num_count; cin >> num_count; num = vector<int>(num_count); cache = vector<int>(num_count); for (int j = 0; j < num_count; j++) cin >> num[j]; int result = 0; for (int j = 0; j < num.size(); j++) { int max_num = 0, index = 0; while (index >= 0 && index < j) { if (num[index] > num[j]) max_num = max(cache[index], max_num); index++; } cache[j] = max_num + 1; result = max(result, cache[j]); } cout << result << endl; }

+) 참고 : http://wootool.tistory.com/96

2879 코딩은 예쁘게 : https://www.acmicpc.net/problem/2879

#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; vector<int> original, difference; int main() { int input, num_count; cin >> num_count; original = vector<int>(num_count); difference = vector<int>(num_count, 0); for (int j = 0; j < num_count; j++) cin >> original[j]; for (int j = 0; j < num_count; j++) { cin >> input; difference[j] = input - original[j]; } int result = 0, end = difference.size() - 1; while (1) { int j = 0, num_flag = difference[0]; while (!difference.empty()) { if (j >= difference.size()) { j--; break; } else if (difference[0] == 0) { difference.erase(difference.begin()); num_flag = 0; } else if (difference[j] * num_flag < 0 || difference[j] == 0) { j--; break; } else { num_flag = difference[j]; j++; } } if (difference.empty()) break; vector<int> temp = vector<int>(j + 1); copy(difference.begin(), difference.begin() + j + 1, temp.begin()); sort(temp.begin(), temp.end()); int multiple = temp[0] < 0 ? temp[temp.size() - 1] : temp[0]; result += multiple < 0 ? multiple*-1 : multiple; for (int index = 0; index <= j; index++) difference[index] += multiple*-1; } cout << result << endl; }

코딩은 예쁘게

내가 처음 혼자서 푼 DP문제 이다.. 감격..

DP 고자에게는 너무 힘든 문제였다.

일단 이 문제를 어떻게 DP로 풀지 생각하였다.

부분을 나누어서 계산하는 것인 만큼 DP를 이용하면 된다고 했는데 그걸 머리 짜내서 고민하다가 그냥 DP를 버렸다.

1. 차이가 0일때

2. 부호가 달라질때

두개의 경우의 수가 있을 때 구간을 나누어야한다.

절댓값이 가장 작은 것을 골라서 구간에 있는 모든 숫자에 뺀다.

나의 코드 같은 경우는 차이가 0인 것이 맨 앞에 오면 지워버린다.

중복되는 반복을 조금이라도 줄이고 싶어서 이다.

+) return 1을 해주는 경우와 함수()+1해주는 경우는 무엇이 다를까?

 return 1을 해주는 경우는 방법의 수를 나타낼 때 주로 쓰인다. 예를 들어 이길로 가서 목표에 도달하면 return 1 즉 방법이 1개 있다는 뜻이다.

 하지만 함수()+1을 해주는 경우는 가는 경로를 모두 더해주는 것이다. 예를 들어 이길로 가서 목표에 도달하지만 가는 경로에 집이 9개 있었다면 이 방법을 쓴다.