[알고리즘 문제] 76. 이항계수(메모이제이션)
2020. 10. 27. 18:33
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int dy[21][21]; int DFS(int n, int r) { if (dy[n][r] > 0) return dy[n][r]; if (r == 0 || n == r) return 1; else return dy[n][r] = DFS(n - 1, r) + DFS(n - 1, r - 1); } int main(void) { int n, r; cin >> n >> r; cout
[알고리즘 문제] 75. 최대 수입 스케쥴(priority_queue 응용문제)
2020. 10. 26. 22:26
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; struct Data { int money; int when; Data(int a, int b) : money(a), when(b) {} bool operator b.when; } }; int main(void) { int n, m, d, i, j, res = 0, max = -2147000000; vector T; priority_queue pQ; cin >> n; for (i = 0; i > m >> d; T.emplace_back(Data(m, d)); if (d > max) max = d; } sort(T.begin(), T.e..
[알고리즘 문제] 74. 최소힙(priority_queue : 우선순위 큐)
2020. 10. 25. 22:18
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int main(void) { int input; priority_queue PQ; while (true) { cin >> input; if (input == -1) break; else if (input == 0) { if (PQ.empty()) cout
[알고리즘 문제] 73. 최대힙(priority_queue : 우선순위 큐)
2020. 10. 25. 21:53
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int main(void) { int input; priority_queue PQ; while (true) { cin >> input; if (input == -1) break; else if (input == 0) { if (PQ.empty()) cout
[알고리즘 문제] 72. 공주 구하기(큐 자료구조로 해결)
2020. 10. 25. 21:41
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int main(void) { int n, k, i; cin >> n >> k; queue Q; for (i = 1; i
[알고리즘 문제] 71. 송아지 찾기(BFS : 상태트리탐색)
2020. 10. 23. 23:48
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int ch[10001], d[3] = { -1, 1, 5 }; int main(void) { int s, e, x, pos, i; cin >> s >> e; queue Q; ch[s] = 1; Q.push(s); while (!Q.empty()) { x = Q.front(); Q.pop(); for (int i = 0; i < 3; ++i) { pos = x + d[i]; if(pos 10000) continue; if (pos == e) { // 출발 지점을 1로 잡았기 때문에 이전 지점 출력 cout
[알고리즘 문제] 70. 그래프 최단거리(BFS)
2020. 10. 21. 20:34
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int ch[21], dis[21]; int main(void) { int n, m, i, a, b, x; vector map[21]; queue Q; cin >> n >> m; for (i = 1; i > a >> b; map[a].push_back(b); map[b].push_back(a); } Q.push(1); ch[1] = 1; while (!Q.empty()) { x = Q.front(); Q.pop(); for (i = 0; i < map[x].size(); ++i) { if (ch[map[x][i]] == 0) { ch[map[x][i]] = 1; Q.push(map[x][i]); dis[map[x]..
[알고리즘 문제] 69. 이진트리 넓이우선탐색(BFS)
2020. 10. 20. 12:30
문제 풀이/알고리즘 문제풀이
코드 #include #include using namespace std; int Q[100], front = -1, back = -1, ch[10]; vector map[10]; int main(void) { int i, a, b, x; for (i = 1; i > a >> b; map[a].push_back(b); map[b].push_back(a); } Q[++back] = 1; ch[1] = 1; while (front < back) { x = Q[++front]; cout
[알고리즘 문제] 68. 최소비용(DFS : 가중치 방향그래프 인접리스트)
2020. 10. 20. 12:18
문제 풀이/알고리즘 문제풀이
코드 #include #include using namespace std; int n, cost = 2147000000; int ch[21]; vector map[21]; void DFS(int v, int sum) { if (v == n) { if (cost > sum) cost = sum; } else { for (int i = 0; i > n >..
[알고리즘 문제] 67. 최소비용(DFS : 인접행렬)
2020. 10. 19. 14:57
문제 풀이/알고리즘 문제풀이
코드 #include #include using namespace std; int arr[21][21]; int ch[21]; int n, min = 2147000000; void DFS(int v, int sum) { int i; if (v == n) { if (sum > n >> m; for (i = 0; i > a >> b; cin >> arr[a][b]; } ch[1] = 1; DFS(1, 0); ..
[알고리즘 문제] 66. 경로 탐색(DFS : 인접리스트 방법)
2020. 10. 19. 14:40
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int n, cnt = 0; int map[21][21]; int ch[21]; void DFS(int L) { int i; if (L == n) { ++cnt; } else { for (i = 1; i > n >> m; for (i = 1; i > a >> b; map[a][b] = 1; } ch[1] = 1; DFS(1); cout n >> m; for (i = 0; i > a >> b; map[a].push_back(b); } ch[1] = 1; DFS(1); cout
[알고리즘 문제] 65. 미로탐색(DFS)
2020. 10. 19. 14:33
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int arr[8][8], ch[8][8]; int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; int cnt = 0; void DFS(int x, int y) { int i, xx, yy; if (x == 7 && y == 7) { ++cnt; } else { for (i = 0; i 7 || yy 7) continue; if (arr[xx][yy] == 0 && ch[xx][yy] == 0) { ch[xx][yy] = 1; DFS..
[알고리즘 문제] 64. 경로 탐색(DFS)
2020. 10. 18. 23:45
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int n, cnt = 0; int map[21][21]; int ch[21]; void DFS(int v) { // 종료 지점이라면 if (v == n) { cnt++; } else { for (int i = 1; i > n >> m; int p1, p2; for (int i = 1; i > p1 >> p2; map[p1][p2] = 1; } ch[1] = 1; DFS(1); cout
[알고리즘 문제] 63. 인접행렬(가중치 방향그래프)
2020. 10. 16. 13:25
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int map[21][21]; int main(void) { int n, m; cin >> n >> m; int p1, p2, p3; for (int i = 1; i > p1 >> p2 >> p3; map[p1][p2] = p3; } for (int i = 1; i
[알고리즘 문제] 62. 병합정렬
2020. 10. 16. 13:11
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; vector vInt; vector vTemp; void divide(int left, int right) { int mid; int p1, p2, p3; if (left < right) { mid = (left + right) / 2; divide(left, mid); divide(mid + 1, right); p1 = left; p2 = mid + 1; p3 = left; while (p1
[알고리즘 문제] 61. 특정 수 만들기(DFS : MS 인터뷰)
2020. 10. 9. 18:04
문제 풀이/알고리즘 문제풀이
코드 #include #include #include #include using namespace std; vector nums; int m; int cnt = 0; void DFS(int L, int value) { if (L == nums.size()) { if (m == value) { ++cnt; } } else { DFS(L + 1, value + nums[L]); DFS(L + 1, value - nums[L]); DFS(L + 1, value); } } int main(void) { int n, i; cin >> n >> m; nums.resize(n); for (i = 0; i > nums[i]; } DFS(0, 0); cout
[알고리즘 문제] 60. 합이 같은 부분집합(DFS : 아마존 인터뷰)
2020. 10. 8. 10:23
문제 풀이/알고리즘 문제풀이
코드 #include #include #include #include using namespace std; int n, ch[11], arr[11]; vector v; bool isEnd = false; void DFS(int L) { if (isEnd) return; int i, sum = 0; if (L == n + 1) { for (i = 1; i arr[i]; } DFS(1); if(!isEnd) cout arr[i]; } DFS(1); cout
[알고리즘 문제] 59. 부분집합(DFS)
2020. 10. 8. 09:53
문제 풀이/알고리즘 문제풀이
코드 #include #include using namespace std; int n, ch[11]; void DFS(int L) { int i; if (L == n + 1) { for (i = 1; i