[C++] 분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer)

말 그래도 문제를 분할과 정복으로 나눠서 해결하는 것을 말한다.

• 분할 단계에서는 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아질수록 풀기 쉬워지기 때문이다.
• 대체로 분할 정복은 재귀 호출을 사용한다.

 

문제

 

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

#include <iostream>
#include <cmath>
using namespace std;

int board[64][64];

void f(int n, int x, int y)
{
	bool color = board[y][x];
	bool diff = false;
	for (int i = y; i < n + y; ++i) {
		for (int j = x; j < n + x; ++j)
			if (color != board[i][j]) {
				diff = true;
				break;
			}

		if (diff)
			break;
	}

	if (!diff) {
		cout << color;
		return;
	}
	cout << "(";
	f(n / 2, x, y);
	f(n / 2, x + n / 2, y);
	f(n / 2, x, y + n / 2);
	f(n / 2, x + n / 2, y + n / 2);
	cout << ")";
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			scanf("%1d", &board[i][j]);

	f(n, 0, 0);
}

 

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

#include <iostream>
using namespace std;

int board[2190][2190];
int ans[3];

void f(int n, int x, int y)
{
	if (n == 1) {
		ans[board[y][x] + 1]++;
		return;
	}

	int tmp = board[y][x];
	bool diff = false;
	for (int i = y; i < n + y; ++i) {
		for (int j = x; j < n + x; ++j)
			if (tmp != board[i][j]) {
				diff = true;
				break;
			}
		if (diff)
			break;
	}

	if (!diff) {
		ans[tmp + 1]++;
		return;
	}

	n /= 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			f(n, x + n * j, y + n * i);
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			scanf("%d", &board[i][j]);

	f(n, 0, 0);
	cout << ans[0] << "\n" << ans[1] << "\n" << ans[2];
}

 

https://leetcode.com/problems/different-ways-to-add-parentheses/description/

#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    unordered_map<string, vector<int>> hash;

    vector<int> diffWaysToCompute(string expression) {
        if (hash.find(expression) != hash.end())
            return hash[expression];

        vector<int> result;

        for (int i = 0; i < expression.size(); ++i) {
            char c = expression[i];

            if (c == '+' || c == '-' || c == '*') {
                string left = expression.substr(0, i);
                string right = expression.substr(i + 1);

                vector<int> leftResults = diffWaysToCompute(left);
                vector<int> rightResults = diffWaysToCompute(right);

                for (int l : leftResults) {
                    for (int r : rightResults) {
                        if (c == '+') {
                            result.push_back(l + r);
                        }
                        else if (c == '-') {
                            result.push_back(l - r);
                        }
                        else if (c == '*') {
                            result.push_back(l * r);
                        }
                    }
                }
            }
        }

        if (result.empty())
            result.push_back(stoi(expression));

        hash[expression] = result;
        return result;
    }
};