전체 글

가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)가장 긴 증가하는 부분 수열은 주어진 배열에서 순서를 유지한 채로 길이가 가장 긴 증가하는 부분 수열을 찾는 문제이다. 예를 들면 배열 [10, 9, 2, 5, 3, 7, 101, 18]이 주어지면 이 배열에서 길이가 가장 긴 증가하는 부분 수열은 [2, 3, 7, 101]이며 길이는 4이다. 간단해 보이는데, 접근 방법을 모르면 어려운 유형이므로 기록한다. 해결 방법해결 방법은 2가지가 있다. 동적 계획법을 이용한 방법과 이분 탐색을 활용한 방법이다. 동적 계획법, 시간복잡도 O(N^2)#include using namespace std;int n,a[1003],cnt[1003],res;int main() { ..

코드#include using namespace std;int a,b,c,cnt[21][21][21];int go(int x, int y, int z) { if(x 20 || y > 20 || z > 20) return go(20,20,20); if(cnt[x][y][z] != 0) return cnt[x][y][z]; // 값이 있으면 출력 if(x > a >> b >> c; if(a == -1 && b == -1 && c == -1) break; go(a,b,c); cout 재귀를 계속 실행하면 시간복잡도가 급증한다. 따라서 값을 저장하는 과정이 필요하다. 함수 매개변수가 3개이므로 3차원 배열을 이용해서 값을 기록해두는 아이디어가 필요했다.

코드// 데이터의 크기가 100만 => O(N^2)은 시간 내에 불가// O(NlogN) 풀이법#include #include using namespace std;int n, a[1000003], num, res;int main() { cin >> n; for(int i = 0; i > num; auto k = lower_bound(a, a+ res, num); if(*k == 0) res++; *k = num; } cout 가장 긴 증가하는 부분 수열 (11053번) 문제와 유사하지만 데이터 크기가 차이난다. 데이터 크기가 100만이기 때문에 O(NlogN)으로 해결해야 한다. lower_bound를 이용해, 들어오는 값의 위치를 찾고 만약 새로 들어오는 값이면 r..

코드#include using namespace std;int n, a[1003], cnt[1003],res;int main() { cin >> n; fill(cnt, cnt + 1003, 1); for(int i = 0; i > a[i]; } for(int i = 0; i O(N^2)으로 가장 긴 증가하는 부분 수열(LIS, longest increasing subsequence)를 구하는 문제.

코드#include using namespace std;typedef long long ll;ll n, m, a[100003], s, e = 1e18,result,temp;int main() { cin >> n >> m; for(ll i = 0; i > a[i]; while(s = m) break; // 이 부분이 없으면 틀렸습니다, 오버플로우 때문인 듯 } if(temp 시간을 줄이고 늘리는 방식으로 최소값을 찾아주면 되는데, if(temp >= m) break; 부분을 넣어주지 않아서 헤맨 문제. a[i]값이 작고 mid 값이 큰 경우, mid / a[i] 값이 큰 값을 갖는데 이를 여러 번 더하면 temp가 long long의 범위를 넘어서게 된다. ..

코드#include #include #include #include // memset, memcpy 포함using namespace std;int n, m, l, r, s, c, a[53][53], res = 987654321, b[53][53];vector> v;void go() { memcpy(b, a, sizeof(a)); // b 배열에 a배열을 복사 int temp[53][53]; // 임시 배열 for(int i = 0; i left; k--) temp[bot][k-1] = a[bot][k]; // 좌측 회전 for(int k = bot; k > top; k--) temp[k-1][left] = a[k][left]; } ..

코드#include #include using namespace std;typedef long long ll;const int INF = 1000000004;int n,a[103],op[5], mx = -INF,mn = INF;int oper(int a, int b, char c) { if(c == '*') return a * b; if(c == '+') return a + b; if(c == '-') return a - b; if(c == '/') return a / b; return 0;}// x는 인덱스 ret은 결과값void go(int x, int ret) { if(x == n) { mn = min(mn, ret); mx = max(mx..

올해 학교에서 공부하면서 빠지게 된 게임이 있습니다. 바로 2048 게임입니다. 스마트폰 처음 나왔을 때였나요? 학교에서 친구들이 많이했었던 것 같습니다. 추억 때문에 다시 들어가봤습니다. 금방 나올 줄 알았는데 단순한 조작법 때문인지, 기록을 세우겠다는 오기 때문인지 모르겠지만 시간가는 줄 모르고 했다가 도서관에서 밤을 꼬박 새운 기억도 있습니다. 아마 다시하기 기능 없이 8192점인가까지 만들었을텐데, 고수분들은 더 높은 점수를 기록했을지도 모르겠습니다. 아무튼 그러다보니 직접 만들어보고 싶은 마음도 들더군요... 이미 만들어져 있어서 굳이 만들 필요가 있나 싶을 수도 있지만, 직접 제작해 보고 싶었습니다. 구글에서 2048 검색하고 상위에 있는 링크에서 게임을 실행했을 때 메모리 용량도 많이 차지하..

코드#include #include #include using namespace std;int n, m, t, x, d, k, res;vector> v;vector> zv;void FASTIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}int main() { FASTIO(); cin >> n >> m >> t; for (int i = 0; i dq; for (int j = 0; j > temp; dq.push_back(temp); } v.push_back(dq); } for (int i = 0; i > x >> d >> k;..

코드#include #include #include #include #include using namespace std;typedef long long ll;// 문제의 답이 30만 * 100만이 될 수 있으므로 long long으로 선언ll n,k,m,v,c,res;vector> jew;vector bag;void FASTIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}int main() { FASTIO(); cin >> n >> k; for(int i = 0; i > m >> v; jew.push_back({m,v}); } while(k--) { cin >> c; bag.push_back(c..