[Algorithm] 분할 정복 (Divide & Conquer) #230202

본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 

분할 정복

부분 문제의 답으로부터 전체 문제의 답을 도출한다.

(1) 문제를 더 작은 문제로 분할하는 과정 (Divide)
(2) 부분 문제를 원래 문제로 병합하는 과정(merge)
(3) 더이상 답을 분할하지 않고 바로 푸는 문제 (base case)

 

ex) 행렬의 거듭제곱

행렬의 곱셈은 주어진 행렬의 모든 원소를 가로 세로를 곱해줘야하므로 O(n^3) 의 시간 복잡도를 가진다. 이를 분할 정복을 이용해서 풀어보자.

class SquareMatrix;

SquareMatrix identity(int n);

SquareMatrix pow(const SquareMatrix& A, int m) {
    if (m == 0)
        return identity(A.size());
    if (m % 2 > 0)
        return pow(A, m - 1) * A;
    SquareMatrix half = pow(A, m / 2);
    return half * half; 
}

문제 : 쿼드 트리 뒤집기

#include <iostream>
#include <vector>
#define MAX_SIZE 64 // 왜?
using namespace std;

char decompressed[MAX_SIZE][MAX_SIZE];
string input;


// 현재 위치 (y, x) 
void decompress(string::iterator &iter, int y, int x, int size) {
	int head = *(iter++); 
	if (head == 'b' || head == 'w') {
		for (int dy = 0; dy < size; dy++) {
			for (int dx = 0; dx < size; dx++) {
				decompressed[y + dy][x + dx] = head;
			}
		}
	}
	else { // 'x'인 경우
		int half = size / 2; 
		
		decompress(iter, y, x, half);
		decompress(iter, y, x + half, half);
		decompress(iter, y + half, x, half);
		decompress(iter, y + half, x + half, half);
	}
}

string answer;

string reverse(string::iterator& iter) {
	char head = *(iter++);
	if (head == 'b' || head == 'w')
		return string(1, head); 
	string upperLeft = reverse(iter);
	string upperRight = reverse(iter);
	string lowerLeft = reverse(iter);
	string lowerRight = reverse(iter);

	return string("x") + lowerLeft + lowerRight + upperLeft + upperRight; 
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> input;
		string::iterator iter = input.begin();
		decompress(iter, 0, 0, input.size());

	}
}