기술 블로그

https://www.acmicpc.net/problem/1953 이분 그래프 문제이다. 참고 문제 : https://www.acmicpc.net/problem/1707 참고 풀이 : https://hsdevelopment.tistory.com/74 #include using namespace std; #define MAX 101 int N, M, T; vector v[MAX]; vector a, b; int color[MAX]; bool go(int now, int next) { for (auto i : v[now]) { if (i == next) { return false; } } return true; } void dfs(int vertex, int nodeColor) { color[vertex] ..

https://www.acmicpc.net/problem/17836 1. 방문 처리할 때, 그람을 먹었는지와 아직 먹지 않았는지 2가지를 따져야한다. 즉, 3차원 방문 처리 2. 제한시간인 T시간을 고려하여 구현한다. 그냥 현재 그 순간의 시간(d)을 활용하여 T와 비교하면 된다. 도착했을 때, 이제 먹으려고 할 때 d vs T #include using namespace std; #define MAX 101 typedef struct{ int r, c, g, d; }info; int N, M, T; int m[MAX][MAX]; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; bool used[MAX][MAX][2]; // 0 : 그람을 먹지 않았..

https://www.acmicpc.net/problem/16493 냅색 #include using namespace std; int N, M, cache[201][21]; vector v; int ks(int goal, int idx) { if (idx == M) { return 0; } int& ret = cache[goal][idx]; if (ret != -1) return ret; ret = ks(goal, idx + 1); if (goal - v[idx].first >= 0) { ret = max(ret, ks(goal - v[idx].first, idx + 1) + v[idx].second); } return ret; } int main() { //freopen("C:\\Users\\park7..

https://www.acmicpc.net/problem/3067 냅색 #include using namespace std; int N, T, cache[10001][21]; vector v; int ks(int goal, int idx) { if (idx == N) { if (goal == 0) return 1; return 0; } int& ret = cache[goal][idx]; if (ret != -1) return ret; ret = ks(goal, idx + 1); if (goal - v[idx] >= 0) { ret += max(ks(goal - v[idx], idx), ks(goal - v[idx], idx + 1)); } return ret; } int main() { //freopen..

https://www.acmicpc.net/problem/14728 냅색 문제이다. #include using namespace std; int N, T, cache[10001][101]; vector v; int ks(int T, int idx) { if (idx == N) { return 0; } int& ret = cache[T][idx]; if (ret != -1) return ret; ret = 0; // 우선 현재 순서를 건너 뛰어본다. ret = max(ret, ks(T, idx + 1)); // 알맞은 조건 하에 현재 순서를 진행한다. if (T - v[idx].first >= 0) { // 비교 ret = max(ret, ks(T - v[idx].first, idx + 1) + v[idx..

수학, 자료구조, multimap https://www.acmicpc.net/problem/9375 각 Type에 Name을 담는다. 이때, 숫자가 아닌 문자열이고, 1개 초과로 담아야 하므로, multimap을 이용한다. 정답은 (각 Type에 속해 있는 Name의 개수 + 1)을 Type 수에 맞게 연산한다. #include using namespace std; int T, n; multimap mm; set st; int main() { //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin); cin.tie(0); scanf("%d", &T); while (T--) { cin >> n; st.clear(); mm.clear(); ..

https://www.acmicpc.net/problem/2467 이분탐색 문제다. 참고로 두 용액의 합이 0이 될 수도 있다. 1. 맨 처음 원소와 맨 마지막 원소의 비교를 처음으로 설정한다. L = 0, R = v.size() - 1 2. 비교할 값(pivot)을 설정해, 각각의 절댓값을 비교하여 pivot을 갱신한다. 절댓값을 활용하는 이유는 -와 +를 고려할 필요가 없이 무조건 둘 중 작은 값이 0에 가깝기 때문이다. 3. L과 R은 v의 인덱스이고, (v[L] + v[R])이 0을 기준으로 큰지, 작은지, 같은지 비교한다. 4. 3의 결과에 따라, L과 R을 적절히 연산한다. 처음에 틀렸었는데 Update 함수 내의 if 조건문에서 pivot > abs(sum)로 작성했었다. pivot > ab..

유형 : 구현, 시뮬레이션, MST, BFS, DFS, 백트래킹, 브루트포스 18430번 무기공학 https://www.acmicpc.net/problem/18430 9935번 문자열 폭발 https://www.acmicpc.net/problem/9935 11559번 Puyo Puyo https://www.acmicpc.net/problem/11559 4991번 로봇 청소기 https://www.acmicpc.net/problem/4991 16932번 모양 만들기 https://www.acmicpc.net/problem/16932 16985번 Maaaaaaaaaze https://www.acmicpc.net/problem/16985 16987번 계란으로 계란치기 https://www.acmicpc.net..