Algorithm
-
영화 수집 - 3653Algorithm/BOJ 2020. 3. 5. 03:54
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 //3653 - 영화 수집 #include #include using namespace std; int N, M; int idx[100001]; struct FenwickTree { vector tree; FenwickTree(int n) : tree(n, 0) {} int sum(int pos) { int ret = 0; while(pos > 0) { ret += ..
-
펜윅트리Algorithm/세그먼트, 펜윅트리 2020. 3. 5. 01:56
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 //펜윅 트리의 완전한 구현 //펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을 //빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의 //원소가 전부 0이라고 생각한다 struct FenwickTree { vector tree; FenwickTree(int n) : tree(n+1) {} //A[0...pos]의 부분 합을 구한다. int sum(int pos) { //인덱스가 1부터 시작한다고 생각하자. ++pos; int ret = 0; while(pos > 0) { ret += tree[pos]; //다음 구간을 찾기..
-
구간 합 구하기 4 - 11659Algorithm/BOJ 2020. 3. 4. 20:08
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 //11659 - 구간 합 구하기 4 #include using namespace std; int N, M; int arr[100001]; void init() { cin >> N >> M; cin >> arr[1]; for(int i = 2; i> arr[i], arr[i] += arr[i-1]; } int ar(int x) { if(x == 0) return 0; return arr[x]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); init(); int x, y; for(int i =..
-
구간 합 구하기 5 - 11660Algorithm/BOJ 2020. 3. 4. 19:15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 //11660 - 구간 합 구하기 5 #include using namespace std; int N, M; int arr[1025][1025]; int ar(int x, int y) { if(x N >> M; for(int i = 1; i arr[i][j]; arr[i][j] += (ar(i-1, j) + ar(i, j-1) - ar(i-1, j-1)); } } int get(int x2, int y2, int x1, int y1) { return ar(x2, y2) - ar(x2, y1 - 1)..
-
임계경로 - 1948Algorithm/BOJ 2020. 3. 4. 18:48
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 //1948 - 임계경로 #include #include #include using namespace std; int N, M; int s, e; vector adj; vect..
-
줄 세우기 - 2252Algorithm/BOJ 2020. 3. 4. 03:12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 //2252 - 줄 세우기 #include #include using namespace std; int N, M; vector adj; vector order; vector seen; void init() { cin >> N >> M; adj = vector(N+1); seen = vector(N+1, false); int u, v; for(int i = 0; i> u >> v; adj[v].push_back(u); } } void dfs(int he..