soicem's note

겹치는 docs cost를 고려해서 queue를 사용하는 문제 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include using namespace std; int main() { int cases; cin >> cases; while (cases--) { int N, T; cin >> N >> T; list docs; list maxDocs; for (int i = 0; i > val; if (i == T) { docs.push_back(make_pair(val, true)); } else { docs.push_back(make_pair(val, false)); } max..

자료구조 선택의 중요성 123456789101112131415161718192021222324252627282930313233#include #include #include using namespace std;string paren;int level; int main() { int cases; cin >> cases; while (cases--) { cin >> paren; vector stk; for (int i = 0; i 0) stk.pop_back(); else { stk.push_back('e'); break; } } if (stk.size() == 0) cout

cout target; while ((sp == -1 || target > stk[sp]) && n >= val) { stk.push_back(val++); pm.push_back('+'); sp++; } if (target == stk[sp]) { stk.pop_back(); pm.push_back('-'); sp--; } else { cout

Longest Common Sequence 메트릭스를 만들고 역으로 올라가서 LCS 문자열을 구하는 문제 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std; int strBoard[1001][1001];string s1;string s2;string getLCS(int i, int j) { if (strBoard[i][j] == 0) return ""; while (strBoard[i][j] == strBoard[i - 1][j]) i--; while (strBoard[i][j] == strBoard[i][j - 1]) j--; return getLCS(i - 1..

P[N] = P[N-2] + P[N-3] 1234567891011121314151617181920212223#include using namespace std; unsigned long long padovan[100]; int main() { padovan[0] = 1; padovan[1] = 1; padovan[2] = 1; int cases; cin >> cases; while (cases--) { int N; cin >> N; for (int i = 3; i

knuth's optimization을 공부해야함 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include #define MAX 0x12345678 using namespace std;int files[501];int dp[501][501];int pSum[501];int n; // iteration// dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j] + pSum[j] - pSum[i - 1]); (i

최장공통수열찾기. comp가 좋은 네이밍은 아닌듯 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std; int comp[1001][1001]; int main() { string s1; string s2; cin >> s1; cin >> s2; for (int i = 0; i

내리막길이므로 오는 방향의 캐싱을 고려할 필요가 없다.(어느 방향에서 오든 갈 수 있는 길은 왔던 길의 영향을 받지 않기때문) 12345678910111213141516171819202122232425262728293031323334353637383940#include #include using namespace std; int M, N;int map[500][500];int cache[501][501]; int getDownhillPath(int y, int x) { if (y == M - 1 && x == N - 1) { return 1; } if (y N) return 0; int & ret = cache[y][x]; if (ret != -1) return ret; ret = 0; if(map[y ..

두칸 뛰는 문제 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std; int grapes[10000];int cache[10002];int N; int getMaxGrape(int pos) { if (pos == N + 1) return 0; int & ret = cache[pos + 1]; if (ret != -1) return ret; ret = 0; for (int i = pos + 1; i grapes[i]; cout

첫 번째는 재귀로 짰다가 메모리 공간을 줄일 방법을 못찾아서 이터레이션으로 바꾼 문제. int 1000만개에 40mb이므로 10000 * 100은 100만이니 4mb를 넘는다는 사실을 알 수 있다. 따라서 배열을 줄여야하는데 그에 대한 방법은 아래와 같다. 1 1+1 2 1+1+1 1+2 3 1+1+1+1 1+1+2 1+3 4 1234567891011121314151617181920212223242526272829303132#include using namespace std; int N, K;int coins[101];int D[10001]; /*D(i, k) = { D(i -1, k) if C(i) = K}*/ int main() { cin >> N >> K; for (int i = 1; i > coi..