분할정복

[백준 10090] Counting Inversion C++

10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 분할 정복 1. 문제해결 아이디어 임의의 수열에서 자신보다 뒤에 있는데 자신보다 작은 수의 개수의 총 합을 구하는 문제이다 N^2로 풀면 너무 쉽겠지만 N

[백준 1074] Z C++

분할정복은 어려워! 코드만 보면 되게 간단해 보이는데 간단하게 만들기 위해 머리를 짜내는게 힘들다.. 내 머리는 재귀적인 생각을 잘 못하는듯 하다 처음에 입력받은 N값을 2로 나눈 값을 solve()로 넘겨준다 -> 이 때 n == 2라고 가정하자(N == 3인 경우) (r, c)가 몇 사분면에 있는지 4개의 if문을 통해서 판별한다 판별기준 : row + n 과 col + n row+n을 기준으로 r이 이 값보다 작으면 1, 2 사분면 중 하나, 같거나 크면 3, 4 사분면 중 하나이다. col+n을 기준으로는 c가 이 값보다 작으면 1, 3 사분면 중 하나, 같거나 크면 2, 4 사분면 중 하나이다. 총 4가지 기준으로 분할 정복을 실행하고 r, c의 위치를 찾으면 (n == 0) 리턴하여 지금까지 ..

[백준 10830] 행렬 제곱 C++

분할 정복은 어렵다! 거듭제곱에 대해서는 위와 같이 분할이 일어난다. -> m이 짝수일 때, 홀수일 때 분할이 달라지는건 코드에 표현되어있다. 개인적으로 class를 만들어서 객체간의 연산을 해주는 방식으로 만들어서 마음에 든다! #include #include using namespace std; int N; long long B; // 정방 행렬을 저장하는 class class Matrix{ public: int Map[6][6]; Matrix(){} Matrix(int n){ int in; for(int i = 0; i > in; Map[i][j] = in % 1000; } } } // 연산자 오버로딩을 통해서 행렬의 곱..