MY MEMO

그래프 원소와 원소사이를 다:다 연결을 해 놓는 것 정점과 간선으로 구성되어있으며 (1. 이차원 배열 2. 연결 리스트) 로 구현할 수 있다. 탐색 방법 그래프의 모든 노드를 탐색하고 싶을 때 = 그래프 순회 / 그래프 탐색이라고 한다 DFS (깊이 우선 탐색) : Stack으로 구현 BFS (넓이 우선 탐색) : Queue로 구현 신장 트리 정점이 n개 일때 n-1개의 간선을 가지는 트리 형태 DFS / BFS를 구하면 신장트리가 나옴 +) 트리와 그래프의 차이? 트리는 그래프의 일부분으로 Cycle이 없는 그래프를 의미 최소 비용 신장 트리 만약 간선들이 모두 가중치를 가지고 있다면? 신장트리를 만들때 어떻게 최소비용으로 만들 수 있을까? 크루스칼 알고리즘 간선들 사이의 가중치를 정렬한 후 정점들 사..

#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; vectordp; vectorstr; int makePaline(int start, int end) { if (start >= end) return 0; int&ret = dp[start][end]; if (ret != 0) return ret; if (str[start] == str[end]) return makePaline(start + 1, end - 1); return ret = min(makePaline(start + 1, end), makePaline(start, end - 1)) + 1; } int main() { int n; scanf("%d", &..

#define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; vectordp(25, vector(25, vector(25, -1))); int w(int a, int b, int c) { int & ret = dp[a][b][c]; if (ret != -1) return dp[a][b][c]; if (a

#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { int cCnt, cKcal, intT, intM, intK; float tMoney, cMoney; vectordp; vectorcandy; while (1) { scanf("%d %f", &cCnt, &tMoney); if (cCnt == 0) break; intT = (int)(tMoney * 100 + 0.5); dp = vector(intT + 1, 0); candy.clear(); for (int j = 0; j < cCnt; j++) { scanf("%d %f", &cKcal, &cMoney); candy.push_back(ma..

#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int n; vectordp(31, vector(15001, -1)); vectorweight(31); void cal(int idxWeight,int totalWeight) { if (idxWeight > n) return; if (dp[idxWeight][totalWeight] != -1) return; dp[idxWeight][totalWeight] = 1; cal(idxWeight + 1, totalWeight); cal(idxWeight + 1, abs(totalWeight - weight[idxWeight])); cal(idxWeight + 1, tot..

#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { int n, num; scanf("%d", &n); vectordp(n + 1, 0); for (int j = 0; j n) break; dp[num] = (dp[num] + 1) % 1000000000; for (int k = 1; k + num

#define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int n; vectordp(1001, vector(3, vector(4,-1))); /* 지각 2번 || 결석 3번 연속이면 안됨 */ int Check_Attendance(int attendCnt, int lateCnt, int absentCnt) { if (absentCnt >= 3 || lateCnt >= 2) return 0; if (attendCnt == n) return 1; int&ret = dp[attendCnt][lateCnt][absentCnt]; if (ret != -1) return ret; return ret = (Check_Attendance(atten..

#include #include #include using namespace std; int main() { int n; int t=1; cin >> n; while (n != 0) { vector graph(n, vector(3, 0)); vector d(n, vector(3, 0)); for (int i = 0; i > graph[i][j]; } } d[0][1] = graph[0][1]; d[0][2] = d[0][1] + graph[0][2]; for (int i = 1; i < n; i++) { for (int j = 0; j < 3; j++) { if (j == 0) { d[i][j] = graph[i][j] ..

#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { int n; long long Max, num; scanf("%d", &n); while (n--) { scanf("%lld", &num); Max = num; while (num!=1) { Max = max(Max, num); if (num % 2 == 0) num /= 2; else num = num * 3 + 1; } printf("%lld\n", Max); } return 0; } 이 문제를 풀면서 얻은 교훈 : scanf와 printf를 사용하자..시간초과로..고생했다..

#include #include #include #define MAX 987654321 #define SUMCOUNT 130 using namespace std; int main() { vectorsum(SUMCOUNT, 0); vectordp(300001, MAX); int diff = 2, num = 1, N; sum[0] = 1; for (int j = 1; j = 300000) break; } cin >> N; for (int j = 0; j = 300000) break; dp[sum[j]] = 1; for (in..