늘

신촌 ICPC대회에 나왔던 문제이다. 처음에 LIS문제인가 싶어서 만만히 보고 덤볐다가 여러번 시간을 날리고.. 두 포인터문제라는걸 알게되니 금방 풀렸다..! //20922 #include #include #include using namespace std; int n, k; int arr[200001]; int visited[200001]; vector v; int answer; int l, r; int main() { cin >> n >> k; for (int i = 0; i > arr[i]; } visited[arr[0]] = 1; l = r = 0; while (l

전형적인 dp문제 중 한문제였다. 위에서 내려올때와 옆에서 올때의 두가지 경우로 dp[i][j]가 결정된다. #include #include #include using namespace std; int arr[301][301]; int dp[301][301]; int k; int main() { int n, m; cin >> n >> m; for (int i = 0; i > x >> y; arr[x][y] = m - (x + y); if (arr[x][y] < 0) { arr[x][y] = 0; } dp[x][y] = arr[x][y]; } for (int i = 1; i < 300; ++i) { for (int j = 1; j < 300; ++j) { d..

실버문제여서 만만히 보고 덤볐다고 시간좀 걸렸다. 왠지 자주 사용할것 같아서 한번 정리해두기로 하였다. #include #include using namespace std; int arr[10001]; int dp[10001]; int n; int main() { int k; cin >> n >> k; for (int i = 0; i > arr[i]; } dp[0] = 1; for (int i = 0; i < n; ++i) { for (int j = arr[i]; j

위상정렬 알고리즘을 통하여 해결하였다. 위상 정렬 알고리즘(Topology Sort)은 어떤 일을 하는 순서를 찾는 알고리즘이다. 방향 그래프에서 각 정점의 작업(?)수행 순서에 따라서 정렬은 한다고 볼 수 있다. #include #include #include #include using namespace std; int n, k; int time[1001]; int dp[100001]; int degree[100001]; vector v[100001]; int a, b, c; void clear() { for (int i = 1; i t; for (int x = 0; x > n >> k; for (int i = 1; i > time[i]; } for (int i = 1; ..

#include #include #include using namespace std; int dp[1000001]; vector v; int x; int main() { int n; cin >> n; v.push_back(-1000000001); for (int i = 0; i > x; if (v.back() < x) { v.push_back(x); } else { auto it = lower_bound(v.begin(), v.end(), x); *it = x; } } cout

#include #include using namespace std; int i, n; int d[100001]; int main() { cin >> n; for (i = 0; i

#include #include #include #include using namespace std; string c; string s; string boom; int main() { cin.sync_with_stdio(false); cin.tie(NULL); int del = 0; cin >> c; cin >> boom; int i; int last = boom.length() - 1;//boom의 마지막 문자 for (i = 0; i =last) { del = 0; for (int j = 1; j < boom.length(); ++j) { if (boom[last - j] != s[s.size(..

첫 알고리즘은 백준에 있는 난이도 골드5인 LCS문제이다 문자열 길이를 구하는 문제로 알고리즘을 모르면 해매기 쉬울것 같다. #include #include #include #include using namespace std; int dp[1001][1001]; int main() { string main_str, sub_str; cin >> main_str >> sub_str; main_str = "0" + main_str; sub_str = "0" + sub_str; int main_len = main_str.length(); int sub_len = sub_str.length(); for (int i = 1; i < main_len; ++i) { for (int j = 1; j < sub_len; ..

이제 알고리즘 공부는 여기에 적어두려고 한다!