본문 바로가기

알고리즘90

BOJ 14452 - Cow Dance Show (usaco silver, 이분탐색) https://www.acmicpc.net/problem/14452 이분탐색할때 mid값이 문제 조건에 맞는 지 판단하는 isPossible 함수를 짤 때, multiset이나 priority_queue를 이용하고 싶었으나 구현을 못해서 vector로 구현했더니 시간초과가 났던 문제.. Barking dog님의 코드를 참고했습니다. https://github.com/blisstoner/BOJ/blob/master/14452.cpp #include #include #include using namespace std; int n, t; int d[10000]; bool isPossible(int k) { multiset ms; int tot = k, time = 0; for (int i = 0; i < k;.. 2019. 10. 7.
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 11444 - 피보나치 수 6 (행렬곱, 점화식 이용) https://www.acmicpc.net/problem/11444 MOD가 10의 거듭제곱꼴이 아니므로 피사노 주기를 사용할수 없다. 따라서 행렬곱을 이용해야 한다. https://www.acmicpc.net/blog/view/28 설명은 이곳 참고 #include #include using namespace std; typedef long long ll; typedef vector matrix; const ll MOD = 1000000007LL; matrix operator * (const matrix& a, const matrix& b) { int n = a.size(); matrix c(n, vector(n)); for (int i = 0; i < n; i++) { for (int j = 0; j.. 2019. 9. 27.

티스토리툴바