본문 바로가기

분류 전체보기327

BOJ 14170 - Counting Haybales (usaco silver, 차원압축, 세그먼트트리) https://www.acmicpc.net/problem/14170 분류를 차원압축과 세그먼트트리로 하긴 했지만 훨씬 쉽게 풀 수는 있다. 하지만, 차원압축에 익숙해지기 위한 예제로 사용하면 좋을 것 같다. #include #include #include #include using namespace std; const int MAX = 1 = 1; i--) arr[i] = arr[i * 2] + arr[i * 2 + 1]; } int sum(int s, int e, int node, int ns, int ne) { if (e > q; int x[100000], hsize=0; set xSet; unordered_map xHash; //입력 및.. 2019. 10. 3.
LCA - Lowest Common Ancestor (최소공통조상) 기본문제 https://www.acmicpc.net/problem/11438 https://www.acmicpc.net/problem/1761 '트리'에서 두 정점간의 공통 조상 중 가장 가까운 조상의 번호를 찾는 알고리즘이다. O(logn) (0번노드가 첫 노드) 기본 버전이다. O(n) 코드 이해하기가 굉장히 쉽다. 하지만 사용하진 않을 것. LCA 알고리즘이 크게 어떻게 돌아가는지 파악하기만 하면 됨. int depth[MAX], parent[MAX]; void dfs(int curr) { vst[curr] = true; for (int next : adj[curr]) { if (!vst[next]) { depth[next] = depth[curr] + 1; parent[next] = curr; d.. 2019. 10. 1.
BOJ 11973 - Angry Cows (usaco silver, 이분탐색) https://www.acmicpc.net/problem/11973 딱 봐도 이분탐색. 구현하는걸 까먹어서 옛날 코드 참고해서 풀었다. 폭발반지름R 대신 폭발구간 R'에 대해 이분탐색하였다. #include #include using namespace std; int n,k,arr[50000]; /* 처음 짠 논리. 밑에서 간략화 했다. bool isPossible(int m) { int i = 0, cnt = 0;; while(cnt= n) break; } return i >= n ? true : false; } */ bool isPossible(int m) { int i = 0, cnt = 0; while(cnt n >> k; for (int i = 0; i > arr[i].. 2019. 10. 1.
BOJ 11997 - Load Balancing (usaco silver, 차원압축) https://www.acmicpc.net/problem/11997 차원압축 + 2차원 구간합 문제. 차원압축하는 게 어떻게하는지 잘 몰랐는데, https://github.com/kks227/BOJ/blob/master/11900/11997.cpp kks227님 코드를 보며 공부했다. 항상 감사합니다 ㅜㅜ #include #include #include #include using namespace std; int pSum[1001][1001]; inline int rangeSum(int x1, int y1, int x2, int y2){ return pSum[x2][y2] - pSum[x2][y1] - pSum[x1][y2] + pSum[x1][y1]; } int main(){ int N, x[1000].. 2019. 9. 29.

티스토리툴바