알고리즘/메모44 pair 배열에서 이분탐색 stl 사용하기 (lower_bound 등) lower_bound(arr.begin(), arr.end(), make_pair(찾으려는value, 최소값)); 2019. 11. 14. 치킨 맥너겟 이론 (chicken mcnugget theorem) https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem 1) 소수 m, n와 임의의 정수 a,b로 나타낼 수 없는 am+bn(소수m,n의 linear combination)의 최대값은 mn-m-n이며 이를 초과하는 수는 모두 am+bn으로 나타낼 수 있다. 또한 am+bn으로 나타낼 수 없는 값의 개수는 다음과 같다 2) 소수가 아닌 일반 양의 정수 m, n에 대해서도 일반화 한다면, 우선 m,n의 linear combination인 am+bn을 다음과 같이 변환한다. 위 두개는 서로소이므로 이들에 대해서 치킨맥너겟 정리를 적용하면 아래와 같이 정리된다. gcd(m,n)을 마저 곱해주면 따라서 lcm(m,n)-m-n을 초과하는 gc.. 2019. 11. 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. 행렬의 표현 클래스나 구조체를 사용하는 법도 있겠지만 길이가 유동적인 정사각행렬에 대해서는 이 코드가 유용할 듯 하다. #include #include using namespace std; typedef long long ll; typedef vector matrix; matrix operator * (const matrix& a, const matrix& b){ int n = a.size(); matrix c(n, vector(n)); //n*n행렬이 0으로채워진 c 행렬이 생성된다. for(int i=0; i 2019. 9. 27. 이전 1 ··· 4 5 6 7 8 9 10 11 다음
