[C++] DP - 플로이드 워샬 알고리즘(최단거리 , 모든 N과 모든 N의 관계) 모든 도시에서 모든 도시로 가는 최소비용 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); int n,m,a,b,c; cin >> n >> m; vector dis(n+1,vector(n+1,5000)); for(int i = 1; i a>> b>> c; dis[a][b] = c; } for(int k = 1; k 기타등등/알고리즘 기록 2021.08.18
[C++] DP - Knapsack Algorithm(가방 문제) #include #include using namespace std; int main() { ios_base :: sync_with_stdio(false); int n, m, w, v; cin >> n >> m; vector dy(m+1,0); for(int i = 0; i > w >> v; for(int j = w; j 기타등등/알고리즘 기록 2021.08.17
[C++] DP - 알리바바와 40인의 도둑 #include #include using namespace std; int map[21][21]; int dy[21][21]; int main() { ios_base::sync_with_stdio(false); int N; cin >> N; for(int i = 1; i map[i][j]; } } dy[1][1] = map[1][1]; for(int i = 2; i 기타등등/알고리즘 기록 2021.08.17
[C++] DP - 최대 부분 증가수열 #include #include using namespace std; int arr[1001]; int dy[1001]; int main() { ios_base::sync_with_stdio(false); int N,num,res = 0; cin >> N; for(int i = 1; i > arr[i]; } dy[1] = 1; for(int i = 2; i = 1; j--){ if(arr[j] max) //이전의 값을 모두 탐색할 것인데, 자기자신보다 작은 값들 중 길이가 가장 긴 값이 있다면 max에 저장한다 max = dy[j]; } //max에는 자신의값(arr[i])보다 작은 이전의 값(arr[j])들 중 길이가 가장 긴 값이 들어가있다. //자기 자신은 그 값보다 길이가 1증가해야하므로 dy에 .. 기타등등/알고리즘 기록 2021.08.17
[C++] DP - 네트워크 선 자르기(Top-Down) Top Down방식은 재귀적으로 동작한다. #include int dy[101];//다이나믹 배열 메모이제이션 #include using namespace std; int DFS(int n){ if(dy[n] != 0) return dy[n]; //메모이제이션 if(n == 1 || n == 2) return n; //dfs(1)은 한가지 dfs(2)는 두가지 else return dy[n] = DFS(n-1) + DFS(n-2); } int main() { ios_base::sync_with_stdio(false); int n; cin >> n; cout 기타등등/알고리즘 기록 2021.08.17
[C++] DP - 네트워크 선 자르기(Bottom-Up) 아주 복잡하고 큰 문제를 직관적으로 알 수 있을 정도로 작은 단위로 바꾸고 그 답을 구한 다음 큰 문제로 점차 늘려가며 정답을 구한다. int dy[50];//다이나믹 배열 #include using namespace std; int main() { ios_base::sync_with_stdio(false); int n; cin >> n; dy[1] = 1; dy[2] = 2;//작게 쪼갰을때 알 수 있는 해를 미리 저장해놓는다. for(int i = 3; i 기타등등/알고리즘 기록 2021.08.17
[C++] DFS - 휴가(삼성 SW) #include #include #include using namespace std; int N; vector a; int res = -2147000000; void DFS(int v, int sum){ if(v == N+1){ if(sum > res) res = sum; } else{ if(v+a[v].first res) res = sum; } else{ ... 8일 이후값 거르지 않고 바로 재귀 } } 2. 이런 문제들은 순서가 정해져있다. 만약 3일차 상담을 받았다면 1일차와 2일차는 굳이 고려할 필요가 없다. 따라서 7개의 가지를 만들 필요가 없다.(순서가 정해져있다.) 따라서, 상담을 한다와 안한다로 두개의 가지를 뻗어나가는 것이 더 유리하다. 만약 이걸 고려하지 않았다면 재귀를 아래처럼 짯을 .. 기타등등/알고리즘 기록 2021.08.12
[C++] DFS - MS인터뷰 복면산(SEND + MORE = MONEY) using namespace std; int a[10], ch[10]; int send() { return a[0]*1000+a[1]*100+a[2]*10+a[3]; } int more() { return a[4]*1000+a[5]*100+a[6]*10+a[1]; } int money() { return a[4]*10000+a[5]*1000+a[2]*100+a[1]*10+a[7]; } void DFS(int L) { if(L==8) { if(send()+more()==money()){ if(a[0] == 0 || a[4] == 0) return; printf(" %d %d %d %d\n", a[0], a[1], a[2], a[3]); printf("+ %d %d %d %d\n", a[4], a[5], a.. 기타등등/알고리즘 기록 2021.08.12
[C++] 벨만포드 알고리즘 - 기초 다익스트라에서 Greedy를 뺌, 간선이 음의 값이어도 됌 #include #include using namespace std; int dist[101]; struct Edge{ int s; int e; int val; Edge(int a, int b, int c){ s = a; e = b; val = c; } }; int main() { vector Ed; int i, n, m, a, b, c, j ,s ,e; scanf("%d %d",&n,&m); for(i = 1; i 기타등등/알고리즘 기록 2021.08.10
[C++] 다익스트라 알고리즘(Greedy, priority queue활용) - 기초 시작 노드로부터 모든 노드까지의 최소비용 #include #include #include #include using namespace std; struct Edge{ int vex; int dis; Edge(int a, int b){ vex = a; dis = b; } bool operator ref.dis; } }; int main() { priority_queue pQ; vector graph[30];//인접리스트 그래프 그리기 int i, n, m, a, b, c; cint >>n>>m; vector dist(n+1, 2147000000);//벡터 초기화 for(i = 1; i > a >> b >> c; graph[a].push_back(make_pair(b, c)); } Q.push(Edge(1,.. 기타등등/알고리즘 기록 2021.08.08