알고리즘/백준 & swacademy108 BOJ 12865 - 평범한 배낭 기본 knapsack문제다. int knapsack(int pos, int cap) // 가방의 남은 용량이 cap이고 pos~n-1번 물건을 고를 때 가치의 최대. 0번 물건~ n-1번 물건을 순서대로 참조하면서 1. pos번째 물건을 선택할 수 있을 경우 (물건의 무게가 cap보다 낮거나 같은 경우) ret = max(pos번째 물건을 선택하지 않은 경우, pos번째물건의 가치 + knapsack(pos+1, cap - item[pos].first) 2. pos번째 물건이 너무 무거워 선택할 수 없는 경우 ret = pos번째 물건을 선택하지 않은 경우 d[pos][cap]을 메모하며 dp하는 문제다. #include #include #include using namespace std; int n, .. 2019. 7. 29. BOJ 11780 - 플로이드2 플로이드 와샬 알고리즘을 사용하는 문제. #include #include #include using namespace std; typedef unsigned long long ll; const int INF = 1e9; int dist[101][101]; int via[101][101]; int ks[101][101]; void reconstruct(int i, int j, vector& path) { //i->j 경유없이 가는 경우면 if (via[i][j] == -1) { path.push_back(i+1); path.push_back(j+1); return; } //i->j 경유점이 있다면 int w = via[i][j]; //w에 경유점 담아주고 reconstruct(i, w, path); pat.. 2019. 7. 29. BOJ 1182 - 부분수열의 합 N과 M 시리즈에서 사용한 논리를 적용했다. 여러 군데에서 요긴하게 잘 쓸 것 같다. #include #include #include using namespace std; int arr[20], n, s, cnt; void go(vector& picked, int sum) { if (!picked.empty() && sum == s) { cnt++; } int next = picked.empty() ? 0 : picked.back() + 1; for (int i = next; i < n; i++) { picked.push_back(i); go(picked, sum + arr[i]); picked.pop_back(); } } int main() { scanf("%d %d", &n, &s); for (int.. 2019. 7. 6. BOJ 9663 - N QUEEN 저번에 마구잡이로 풀어봤지만 백트래킹 연습으로 한 번 더 풀어봤다. 1번줄부터 n번 줄까지 퀸을 배치하는데, x좌표가 중복되지 않게 뽑는 것을 백트래킹 해주면서 대각선에 다른 퀸이 배치돼있는지 검사해줬다. #include #include #include #include using namespace std; int n; bool isValid(vector& picked) { //대각선 검사만 해주면 된다. |(y'-y)| == |(x'-x)| 인경우 return false if (picked.empty()) return true; for (int i = 0; i < picked.size()-1; i++) { // {i, picked[i]} : 퀸의 위치 (y,x) for (int j = i + 1; j <.. 2019. 7. 6. 이전 1 ··· 23 24 25 26 27 다음