본문 바로가기

전체 글

 (131)
75. 최대 수입 스케줄(priority_queue 응용문제) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★ #include #include #include #include using namespace std; struct Pay { int pay, day; Pay(int x, int y) // 구조체 생성자 { pay = x; day = y; } bool operator x.day; // day = this.day , x.day = Pay x의 day } }; int main() { int n, d, m, j = 0, max = 0, answer = 0; scanf("%d", &n); vector allPay; priority_queue pQ; for(int i = 1; i = 1; i--) // 3일차부터 { for(; j < allPay.size(); j++) // 매우 중요한 부분!! j를 계속해서 0으..
74. 최소힙(priority_queue : 우선순위 큐) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★☆☆☆☆ #include #include using namespace std; int main() { int n; priority_queue pQ; queue Q; while(true) { scanf("%d", &n); if(n == 0) { if(pQ.empty()) printf("%d", -1); else { Q.push(-pQ.top()); pQ.pop(); } } else if(n == -1) { while(!Q.empty()) { printf("%d\n", Q.front()); Q.pop(); } break; } else { pQ.push(-n); } } return 0; } 1. 최소힙의 경우에는 우선순위 큐에 넣을 때 부호를 바꿔서 넣고 꺼낼 때도 부호를 바꿔서 꺼낸다.
73. 최대힙(priority_queue : 우선순위 큐) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆ #include #include using namespace std; int main() { int n, val; priority_queue pQ; // STL queue에 포함되어있는 우선순위형태의 큐이다 queue Q; while(true) { scanf("%d", &n); if(n == 0) { if(pQ.empty()) printf("%d", -1); else { Q.push(pQ.top()); // 가장 큰 노드의 값에 접근 pQ.pop(); } } else if(n == -1) { while(!Q.empty()) { printf("%d\n", Q.front()); Q.pop(); } break; } else pQ.push(n); } return 0; } 1. priority_queue : ST..
72. 공주 구하기(큐 자료구조로 해결) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★☆☆☆☆ #include #include using namespace std; int main() { int n, k, val, count = 0; scanf("%d %d", &n, &k); queue Q; for(int i = 1; i
71. 송아지 찾기(BFS : 상태트리탐색) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include #include using namespace std; queue Q; int dis[10001]; int dir[3] = {1, -1, 5}; int main() { int s, e, x, val; scanf("%d %d", &s, &e); Q.push(s); while(!Q.empty()) { val = Q.front(); Q.pop(); if(e - val >= 5) // 거리가 5이상 차이나면 5만큼 이동 { dis[val + 5] = dis[val] + 1; // 다음 노드까지의 거리 = 지금까지 이동한 거리 + 1 if(val + 5 == e) // 다음 노드가 목적지라면 { printf("%d", dis[val + 5]); return 0; } Q.push(val + 5); }..
70. 그래프 최단거리(BFS) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include #include using namespace std; queue q; vector map[21]; int n, val; int ch[21], dis[21]; int main() { int m, a, b, x = 2; scanf("%d %d", &n, &m); for(int i = 1; i
69. 이진트리 넓이우선탐색(BFS) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆ #include #include using namespace std; queue q; vector map[8]; int main() { int a, b, x = 1; for(int i = 1; i
68. 최소비용(DFS : 가중치 방향그래프 인접리스트) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include #include using namespace std; int n, sum = 0, minNum = 2147000000; vector map[21]; int path[21]; void DFS(int x, int sum) { if(x == n) { if(minNum > sum) minNum = sum; } else { for(int i = 0; i 0 && path[map[x][i].first] == 0) { path[map[x][i].first] = 1; DFS(map[x][i].first, sum + map[x][i].second); path[map[x][i].first] = 0; } } } } int ma..

티스토리툴바