[알고리즘] 분할 정복(Divide and Conquer)

1. 정의

- 작은 문제로 분할하여 문제를 해결하는 방법

   1) 분할 : 본 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 나누기

   2) 정복 : 하위 문제를 각각을 재귀적으로 해결

   3) 조합 : 하위 문제들의 답을 합쳐서 본 문제를 해결

 

2. 상세설명

- 특정 수나 행렬의 거듭제곱을 구할 때 사용

  => 시간 복잡도 O(n)에서 O(logN)으로 줄일 수 있음

 

3. 적용 사례

3-1) 거듭제곱

long long power(long long n, long long m) {
	long long ret = 1;
	while (m) {
		if (m & 1) ret = ret * n % MOD;
		m = m / 2;
		n = n * n % MOD;
	}
	return ret;
}

3-2) 행렬 거듭제곱

long long matrix[5][5] = {
	1, 2, 3, 4, 5,
    6, 7, 8, 9, 0,
    1, 2, 3, 4, 5,
    6, 7, 8, 9, 0,
    1, 2, 3, 4, 5};

long long ans[5][5] = {
	1, 0, 0, 0, 0,
    0, 1, 0, 0, 0,
    0, 0, 1, 0, 0,
    0, 0, 0, 1, 0,
    0, 0, 0, 0, 1};

void multi_matrix(long long matrix1[5][5], long long matrix2[5][5]) {
	long long tmp[5][5];

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			long long sum = 0;

			for (int i = 0; i < N; i++) {
				sum += matrix1[y][i] * matrix2[i][x];
			}

			tmp[y][x] = sum
		}
	}

	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			matrix1[y][x] = tmp[y][x];
}

void power_matrix() {
	while (B > 0) {
		if (B % 2 == 1)
			multi_matrix(ans, matrix);

		multi_matrix(matrix, matrix);
		B /= 2;
	}
}