본문 바로가기

전체 글327

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); path.pop_back(); reconstru.. 2019. 8. 6.
BOJ 1300 - K번째 수 이분탐색 문제다. binarysearch나 lower_bound 등을 쓸 수 없는 이분탐색 문제 중 하나다. [lo, hi] : 주어진 조건을 만족하는 값의 범위 //라이님의 블로그에선 [lo,hi)로 알려주셨지만 코드 짤 때 이게 더 편한 것 같다. cnt+=min(n,mid/i) // i번째 행의 j번째 요소는 i*j 즉 i의 배수이므로 mid보다 작거나 같은 요소의 개수는 mid/i이다.(최대 n) 이부분을 생각하지 못하고 O(n)논리만 써서 자꾸 시간 초과가 났다. if(cnt>=k) mid이하의 수가 k개 이상이라면 mid는 답이 될 가능성이 있다. (mid-1이하의 수가 k개 미만임이 보장돼야 확실한 답이 되지만 굳이 판단할 필요는 없다.) 따라서 mid+1은 답이 될가능성이 없다. ->hi .. 2019. 7. 29.
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.

티스토리툴바