Storage Gonie

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-16-DP-문제-풀이3-5-백준-No1912-연속합 # C++ #include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); vector d(n); for (int i = 0; i > a[i]; d[0] = a[0]; for (int i = 1; i < n; i++) d[i] = max(d[i-1] + a[i], a[i]); cout

연속합 문제 - https://www.acmicpc.net/problem/1912 문제요약 n개의 정수로 이루어진 임의의 수열이 주어지면 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하라. ex) A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 연속된 수들의 합 중 가장 큰 값은 12 + 21 = 33 해결 방법 1. D[i] 정의 D[i] = "A[i]로 끝나는(까지 왔을 때의) 최대 연속합" 으로 정의할 수 있고, A[i]로 끝나는 최대 연속합은 두가지의 경우가 될 수 있다. 1) A[i-1]로 끝나는 최대 연속합에 A[i]가 포함되는 경우 => D[i-1] + A[i] 2) A[i]가 새로운 수열의 합으로 시작하는 경우 => A[i] 그러면 ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-15-DP-문제-풀이3-4-백준-No11054-가장-긴-바이토닉-부분-수열 # C++ #include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); vector d1(n); vector d2(n); for (int i = 0; i > a[i]; // 왼->오 순으로 A[i]를 원소로 포함하는 가장 긴 증가하는 부분 수열의 길이 구하기 for (int i = 0; i < n; i++) { d1[i] = 1; for (int j = 0 ; j < n; j++) { if (a[j] < a[..

가장 긴 바이토닉 부분 수열 문제 - https://www.acmicpc.net/problem/11054 문제요약 수열 A가 주어졌을 때, 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {1 5 2 1 4 3 4 5 2 1} 가장 긴 바이토닉 부분 수열 A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1} => 길이는 7 해결 방법 * 최근에 푼 3개의 문제에 대한 이해가 있다면 이를 응용하여 풀 수 있다. - 바이토닉 수열의 꼭지값을 기준으로 왼쪽은 가장 긴 증가하는 부분 수열, 오른쪽은 가장 긴 감소하는 부분 수열을 찾아 이 둘의 길이를 합하여 구할 수 있다. 이를 조금만 다르게 생각해보면 "부분 수열의 마지막 원소로 A[i..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-13-DP-문제-풀이3-3-백준-No11722-가장-긴-감소하는-부분-수열 # C++(reverse해서 가장 긴 증가하는 부분 수열의 길이를 구하는 방법을 사용) #include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); vector d(n); for (int i = 0; i > a[i]; // 역순으로 변경 reverse(a.begin(), a.end()); // 가장 긴 증가하는 부분 수열의 길이를 구하는 방법 이용 for (int i = 0; i < n; i++) { d[i]..

가장 긴 감소하는 부분 수열 문제 - https://www.acmicpc.net/problem/11722 문제요약 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {10, 30, 10, 20, 20, 10} 가장 긴 감소하는 부분 수열 A = {10, 30, 10, 20, 20, 10} => 길이는 3 해결 방법 * 바로 전전 문제를 조금 수정해서 풀 수 있다. 방법 1. 입력으로 주어진 수열을 reverse해서 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법' 방법 2. 왼쪽 -> 오른쪽 순으로 값을 구하는 것이 아닌, 오른쪽 -> 왼쪽 순으로 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법' (1) 구현..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-12-DP-문제-풀이3-2-백준-No11055-가장-큰-증가-부분-수열 # C++ #include #include #include using namespace std; int main() { int n; cin >> n; vector d(n); vector a(n); for (int i=0; i> a[i]; for (int i=0; i

가장 큰 증가 부분 수열 문제 - https://www.acmicpc.net/problem/11055 문제요약 수열 A가 주어졌을 때 증가 부분 수열 중에서 가장 수열의 합이 큰 것을 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 합이 가장 큰 증가 부분 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} => 총 합은 1 + 2 + 50 + 60 = 113 해결 방법 * 바로 이전 문제를 조금 수정해서 풀 수 있다. 1. D[N]에 어떤 값을 저장할 것인지 문장으로 정의해줘야한다. 다른 문제에서와 마찬가지로 D에 저장되는 값은 분할된 문제의 해답이다. 즉, D[N] 그 자체가 문제에서 원..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-11-DP-문제-풀이3-1-백준-No2156-포 # C++ #include #include #include using namespace std; int main() { int n; cin >> n; vector d(n); vector a(n); for (int i=0; i> a[i]; for (int i=0; i

가장 긴 증가하는 부분 수열 문제 - https://www.acmicpc.net/problem/11053 문제요약 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {10, 20, 10, 30, 20, 50} 가장 긴 증가하는 부분 수열 A = {10, 20, 10, 30, 20, 50} => 길이는 4 해결 방법 1. D[N]에 어떤 값을 저장할 것인지 문장으로 정의해줘야한다. 다른 문제에서와 마찬가지로 D에 저장되는 값은 분할된 문제의 해답이다. 즉, D[N] 그 자체가 문제에서 원하는 최종 결과값을 의미하지 않는다. 이런 맥락에서 D[i]를 아래와 같이 정의한 뒤 이들의 최대값을 통해 문제가 원하는 해답을 구할..