분류 전체보기 127

[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에 ..

[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

[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개의 가지를 만들 필요가 없다.(순서가 정해져있다.) 따라서, 상담을 한다와 안한다로 두개의 가지를 뻗어나가는 것이 더 유리하다. 만약 이걸 고려하지 않았다면 재귀를 아래처럼 짯을 ..

[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..

[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,..