우리가 보통 행렬의 곱셈을 구현하기 위해서는 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
데큐(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
