알고리즘 문제풀기
-
77. 친구인가?(Disjoint-set : Union&Find 알고리즘)알고리즘 문제풀기/인프런 강의 정답 2022. 5. 30. 11:32
나의정답. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int unf[1001]; int Find(int v){ if(v==unf[v]) return v; else return unf[v] = Find(unf[v]); } void Union(int a, int b){ a = Find(a); b = Find(b); if(a != b) unf[a] = b; } int main(int argc, char** argv) { //freopen("input.txt", "rt", stdin); int n, m, a, b; scanf("%d %d", &n, ..
-
76. 이항계수(메모이제이션)알고리즘 문제풀기/인프런 강의 정답 2022. 5. 25. 23:47
나의정답1. 공식1사용 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int fac(int n) { if (n == 1) return 1; return n * fac(n - 1); } int nCr(int n, int r) { return fac(n) / (fac(r) * fac(n - r)); } int main(int argc, char** argv) { //freopen("input.txt", "rt", stdin); int n, r; scanf("%d %d", &n, &r); printf("%d\n", nCr(n, r)); } 나의정답2...
-
75. 최대 수입 스케쥴(priority queue greedy: 구조체와 Vector를 이용한 정렬)알고리즘 문제풀기/인프런 강의 정답 2022. 5. 24. 20:34
나의정답1. 최대힙 이용안함. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; struct money { int m, d; money(int m, int d) : m(m), d(d) {} bool operator com.d; if (m != com.m) return m > com.m; } }; int main(int argc, char** argv) { //freopen("input.txt", "rt", stdin); int n, m, d, res = 0, maxDate = -1, maxMoney = 0, idx; bool calc; vector ..
-
74. 최소힙(STL priority_queue : 우선순위큐)알고리즘 문제풀기/인프런 강의 정답 2022. 5. 21. 17:22
나의정답. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int main(int argc, char** argv) { //freopen("input.txt", "rt", stdin); int n; priority_queue pq; while (true) { scanf("%d", &n); if (n == -1) return 0; else if (n == 0) { if (pq.empty()) printf("-1"); printf("%d", -pq.top()); pq.pop(); } else { pq.push(-n); } } }
-
73. 최대힙(STL priority_queue : 우선순위큐)알고리즘 문제풀기/인프런 강의 정답 2022. 5. 21. 16:32
나의정답. STL 라이브러리 사용 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int main(int argc, char** argv) { //freopen("input.txt", "rt", stdin); int n; priority_queue pq; while (true) { scanf("%d", &n); if (n == -1) return 0; else if (n == 0) { if (pq.empty()) printf("-1"); printf("%d", pq.top()); pq.pop(); } else { pq.push(n); } } }
-
71. 송아지 찾기 (BFS : 상태트리탐색)알고리즘 문제풀기/인프런 강의 정답 2022. 5. 19. 14:43
나의정답. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int main(int argc, char** argv) { //freopen("input.txt", "rt", stdin); int myPos, cowPos, ch[10001] = { 0 }, dis[10001], x, p; int op[3] = { 1, -1, 5 }; queue q; scanf("%d %d", &myPos, &cowPos); q.push(myPos); ch[myPos] = 1; dis[myPos] = 0; while (!q.empty()) { x = q.front();..
-
70. 그래프 최단거리 (BFS: Breadth First Search)알고리즘 문제풀기/인프런 강의 정답 2022. 5. 19. 12:30
나의정답. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int main(int argc, char** argv) { //freopen("input.txt", "rt", stdin); vector map[30]; queue q; int ch[30] = { 0 }, dis[30], n, m, a, b, x; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d %d", &a, &b); map[a].push_back(b); } q.push(1); ch[1] = 1; dis[1] = 0; w..