Storage Gonie

문제 풀이 자세한 풀이 : 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]를 아래와 같이 정의한 뒤 이들의 최대값을 통해 문제가 원하는 해답을 구할..

문제 풀이 * 입력받은 수를 전부 다 입력 받아서 저장하게 되면 제한된 8MB의 메모리를 초과해버린다. 숫자를 카운트 해두었다가 표준출력으로 출력만 해주는 방식을 사용해야한다. (10^7 * 4byte = 40MB이므로) # C++ #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; int arr[10001] = {0}; // 숫자 개수 카운트 for(int i = 0 ; i > a; arr[a] += 1; } // 각 숫자를 개수만큼 출력해주기 for(int i = 1 ; i

용도 : 두 개 이상의 타입을 하나로 묶어줌, pair의 확장버전이라고 생각하면됨. 1. 헤더파일 #include 2. 변수 선언 및 값 변경 #include #include using namespace std; int main() { tuple t1 = make_tuple(1,2,3,4); tuple t2 = make_tuple(5,6,7,8); cout

문제 풀이 # C++(tutple, sort( , ,비교함수) 이용) - 중첩된 if문을 사용하지 않으므로 실수를 방지할 수 있다. #include #include #include #include using namespace std; struct Person{ string name; int kor, eng, math; }; bool cmp(const Person &u, const Person &v){ return make_tuple(-u.kor, u.eng, -u.math, u.name) > T; vector vec(T); for (int i = 0; i < T; i++) c..

문제 풀이 # C++(pair, stable_sort(, , 비교함수) 사용) - 가장 간단 #include #include #include #include using namespace std; bool cmp (pair u, pair v) { return u.first > T; vector vec(T); for (int i = 0; i > vec[i].first >> vec[i].second; stable_sort(vec.begin(), vec.end(), cmp); for (int i = 0; i > vec[i].second; stable_sort(vec...

문제 풀이 자세한 풀이 : # C++(pair, vector, sort 사용 : first second 를 뒤바꿔 입력받아 정렬한뒤 출력 때 다시 뒤집어 출력하는 방식) - 가장 간단 #include #include #include #include using namespace std; int main() { int T; cin >> T; vector vec(T); for (int i = 0; i > vec[i].second >> vec[i].first; sort(vec.begin(), vec.end()); for (int i = 0; i > vec[i].second; sort(vec.begin(), vec.end(), cmp)..

문제 풀이 자세한 풀이 : # C++(pair, vector, sort 이용) - 이 문제에서 가장 간편한 방법 #include #include #include #include using namespace std; int main() { int T; cin >> T; vector vec(T); for (int i = 0; i > vec[i].first >> vec[i].second; sort(vec.begin(), vec.end()); for(int i = 0; i > vec[i].y; sort(vec.begin(), vec.end(), cmp); for (int i = 0; i > vec..