전체 글 (131) 썸네일형 리스트형 85. 수식만들기(삼성 SW역량평가 기출문제 : DFS 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆ #include int n, mxAns = 0, mnAns = 2147000000; int N[10]; int C[4]; void DFS(int x, int y) { if(x == n) { if(mxAns y) mnAns = y; } else { for(int i = 0; i < 4; i++) { if(C[i] != 0) // 해당 수식의 개수가 남아있다면 { C[i]--; // 쓴다 if(i == 0) DFS(x+1, y+N[x+1]); else if(i == 1) DFS(x+1, y-N[x+1]); else if(i == 2) DFS(x+1, y*N[x+1]); else DFS(x+1, y/N[x+1]); C[i]++; // 쓰고나면 다시 복구 } } .. 84. 휴가(삼성 SW역량평가 기출문제 : DFS 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★ #include #include using namespace std; int n, t, p, money = 0; struct COS { int day; int cost; COS(int x, int y) { this -> day = x; this -> cost = y; } }; vector v; void DFS(int x, int y) { if(x == n+1) // n+1부터 휴가이므로 { if(y > money) money = y; } else { COS temp = v[x]; // 해당 일차의 드는 시간과 받는 돈 if(x + temp.day 83. 복면산 SEND+MORE=MONEY (MS 인터뷰) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include int a[8]; int 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 x) { if(x == 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]); p.. 82. 순열구하기(DFS : Depth First Search) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include int n, r, cnt = 0; int a[17]; int ch[17]; int res[17]; using namespace std; void DFS(int x) { if(x == r) { for(int i = 0; i < r; i++) printf("%d ", res[i]); printf("\n"); cnt++; } else { for(int i = 1; i 80. 다익스트라 알고리즘 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include #include #include using namespace std; struct Edge { int node; int cost; Edge(int x, int y) { this -> node = x; this -> cost = y; } bool operator cost > a.cost; } }; int main() { int n, m, a, b, c; scanf("%d %d", &n ,&m); vector dis(n+1, 2147000000); // 각 노드까지의 거리를 무한대로 설정 vector v[n+1]; priority_queue pQ; for(int i = 1; i nextCost) { dis[nextNode] = nextCost; pQ.push(Edge(nextNode, nex.. 79. 원더랜드(Prim MST 알고리즘 : priority_queue 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include #include #include #include using namespace std; int ch[1001]; struct Edge { int node; // 연결할 노드 int cost; // 가중치 값 Edge(int x, int y) { this -> node = x; this -> cost = y; } bool operator cost > a.cost; // 구조체가 우선순위큐에서 사용되면 최소힙으로 사용된다. // 이 멤버 함수는 구조체가 pop, push 될 때 호출되며, 호출된 a.cost가 더 작은 값이므로 최소힙이 된다 // !! vector에서 사용하면 내림차순을 위한 조건, 우선순위큐에서 사용하면 최소힙 } }; int main() { int v, e, a, b, c,.. 78. 원더랜드(Kruskal MST 알고리즘 : Union & Find 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★ #include #include #include using namespace std; int ch[1001]; struct Edge { int node[2]; // 연결할 두 노드 int cost; // 가중치 값 Edge(int x, int y, int z) { this -> node[0] = x; this -> node[1] = y; this -> cost = z; } bool operator cost < a.cost; // 크루스칼 알고리즘은 오름차순을 이용한다 } }; int Find(int x) { if(ch[x] == x) return x; // 마지막으로 도달한 루트 노드를 반환 else return Find(ch[x]); // 루트 노드가 아니라면 찾을 때까지 재귀함수 호출 } void U.. 77. 친구인가? (Union & Find 자료구조) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★ #include using namespace std; int a[1001]; int Find(int x) { if(x == a[x]) return x; else return a[x] = Find(a[x]); // 3. 같은 루트노드를 가지는 원소 묶기(트리 구조 단순화) } void Union(int x, int y) { int z = Find(x); int w = Find(y); if(z != w) a[z] = w; } int main() { int n, m, x, y, q, w; scanf("%d %d", &n, &m); for(int i = 1; i 이전 1 ··· 4 5 6 7 8 9 10 ··· 17 다음
