우리가 보통 행렬의 곱셈을 구현하기 위해서는 n x n 행렬이 A, B가 있을 때 주어진 행렬의 모든 원소(n^2 가지)에 대해 A행렬의 가로, B행렬의 세로를 곱해줘야 하기 때문에 O(n^3) 번의 연산이 필요하게 된다. 이렇게 되면 n이 조금만 커져도, 또는 거듭제곱의 수가 조금만 커져도 필요한 연산의 수가 매우 크게 증가하기 때문에 연산의 수를 줄이는 알고리즘이 필요하다. 우리는 이 문제를 분할 정복(divide & conquer)로 해결할 수 있는데 예를 들어 행렬 A를 m번 거듭 제곱한다 하면, A^(m) = A^(m/2) * A^(m/2)로 나눌 수 있다는 점을 이용한다. (행렬의 곱셈법칙에 따라서) 만약 A^8 를 구하기 위해 곧이곧대로 A를 7번 곱하게 되면 연산은 총 7 * n^3번 해야..
종만북
ac 코드입니다 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 #include #include using namespace std; //현재 다른 점에 지배당하지 않는 점들의 목록을 저장 //coords[x] = y map coords; //새로운 점(x,y)가 기존의 다른 점들에 지배당하는지 확인한다. bool isDomianted(int x, int y) { //x보다 오른쪽에 있는 점 중 가장 왼쪽에 있는 점을 ..
AC 코드 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 #include #include using namespace std; int main() { int c; scanf("%d", &c); while (c--) { stack st; string s; cin >> s; bool check = true; for (int i = 0; i
AC 코드입니다. 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 #include #include #include #include using namespace std; int waysToBuy(const vector& psum, int k) { const int MOD = 20091101; int ret = 0; vector count(k, 0); //overflow를 방지 for (int i = 0; i
데큐(dequeue) 를 이용한 간단 풀이입니다 AC 코드 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace std; int main(){ int c; scanf("%d", &c); while (c--) { int n, k; scanf("%d %d", &n, &k); int ans; deque dq; for (int i = 2; i
AC 코드입니다. 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 #include #include #include using namespace std; const int INF = 987654321; int n, k, m, l; //prerequisite[i] = i번째 과목의 선수과목 집합 int prerequisit..
에라토스테네스의 체는 굉장히 빠르게 동작하는 소수 찾기 알고리즘입니다. 알고리즘에 대해 간단히 요약을 하자면 소수를 구할 때 소수가 아닌 수들의 배수는 소수가 아니기 때문에 그들을 모두 지워나가면서 남은 수(소수) 들을 찾는 방법인데, 수의 범위가 점점 커지면, 메모리 공간이 부족하기 때문에 이를 극복하기 위해 비트 마스크를 이용합니다. (기존 알고리즘 또한 웬만한 범위 내에서는 잘 작동합니다) 따라서 비트마스크를 사용하는 구간도 메모리 영역에 국한되는데, 기존 에라토스테네스의 체 구현 과정에서 bool 배열로 범위 내 소수가 아닌 수들의 인덱스를 모두 false 처리하고, 소수들을 true 처리해서 소수들을 골라냈다면 이번엔 비트마스크를 이용해서, check 역할을 하는 배열을 unsigned char..
