백준34 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. BOJ 2749 - 피보나치 3 (MOD=10^k꼴일 때 주기 이용) https://www.acmicpc.net/problem/2749 피보나치를 MOD로 나눈 나머지는 항상 주기를 갖는다. (피사노 주기라고 함) 그중 특히 MOD = 10^k (k>2) 인 경우 PRD = 15*10^(k-1)이다. fibo(n)의 값은 fibo(n%PRD)의 값과 같아진다. 피보나치를 dp를 이용하여 풀게되면 O(n)에 풀 수 있으므로 이 방법을 이용하면 O(MOD)라고 볼 수 있겠다. #include #include using namespace std; typedef long long ll; const int MOD = 1e6; const int PRD = 15e5; ll dp[PRD]; ll fibo(int k) { if (k > n; fill(dp, dp + PRD, -1); cout 2019. 9. 27. BOJ 7535 - A Bug's Life https://www.acmicpc.net/problem/7535 7535번: A Bug’s Life The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexua www.acmicpc.net 각 항이 xor로 묶여있는 2-Sat문제이다. p번 벌레가 q번 벌레와 소통했을 때 둘의 성별이 달라야 한다. 이를 p x.. 2019. 8. 19. 이전 1 ··· 3 4 5 6 7 8 9 다음