[종만북] 7장 분할 정복

⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡·2022년 1월 15일

종만북

알고리즘 문제 해결 전략

목록 보기

1/13

종만북 7장 분할 정복

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

➖ 21-06-27

도입

분할 정복 (Divide & Conquer):
주어진 문제들을 둘 이상의 부분 문제로 나눈 뒤,
각 문제에 대한 답을 재귀 호출을 이용하여 계산하고,
각 부분 문제의 답으로부터 전체 문제의 답 계산
일반적인 재귀 호출: 문제를 한 조각과 나머지 전체로 나눔
분할 정복: 문제를 거의 같은 크기의 부분 문제로 나눔
분할 정복을 사용하는 알고리즘의 세가지 구성 요소:
문제를 더 작은 문제로 분할하는 과정(divide)
각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

⚡카라츠바의 빠른 곱셈 알고리즘

두 개의 큰 정수의 곱셈을 하는 알고리즘
수백~수만 자리의 큰 숫자들을 다룰 때 사용
-> 정수형 변수가 아닌 정수형 배열을 이용해 숫자 저장

두 큰 수를 곱하는 O(n^2) 시간 알고리즘

곱할 수의 각 자릿수를 맨 아래자리부터 저장한다

-> A[i]에 주어진 자릿수의 크기: 10^i
-> A[i]와 B[j]를 곱한 결과: C[i+j]에 저장
예: 123 * 456 = 56088
multiply({3,2,1}, {6,5,4}) = {8,8,0,6,5}

//num[]의 자릿수 올림을 처리한다   
void normalize(vector<int>& num){
    num.push_back(0);

    for(int i = 0; i<num.size(); ++i){
        if(num[i] < 0){
            int borrow = (abs(num[i]) + 9)/10;
            num[i+1] -= borrow;
            num[i] += borrow * 10;
        }
        else{
            num[i+1] = num[i]/10;
            num[i] %= 10;
        }
    }

    while(num.size() > 1 && num.back() == 0) num.pop_back();
}


//두 긴 자연수의 곱을 반환한다
vector<int> multiply(const vector<int>& a, const vector<int>& b){
    vector<int> c(a.size() + b.size() + 1, 0);

    for(int i = 0; i<a.size(); ++i)
        for(int j = 0; j<b.size(); ++j)
            c[i+j] = a[i] * b[j];

    normalize(c);
    return c;
}

카라츠바의 빠른 곱셈 알고리즘

두 수를 각각 절반으로 쪼갠다

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

//num[]의 자릿수를 올림을 처리한다.
void normalize(vector<int>& num){
	num.push_back(0);

	//자릿수 올림을 처리한다.
	int size = num.size();
	for (int i = 0; i < size - 1; i++)
	{
		if (num[i] < 0)
		{
			int borrow = (abs(num[i]) + 9) / 10;
			num[i + 1] -= borrow;
			num[i] += borrow * 10;
		}
		else
		{
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
	}
	//앞에 남은 0을 제거한다.
	while (num.size() > 1 && num.back() == 0)
		num.pop_back();
}

//초등학교식 정수 곱셈
vector<int> multiply(const vector<int>& a, const vector<int>& b){
	vector<int> c(a.size() + b.size() + 1, 0);

	int aSize = a.size();
	int bSize = b.size();

	for (int i = 0; i < aSize; i++)
		for (int j = 0; j < bSize; j++)
			c[i + j] += a[i] * b[j];
	normalize(c);
	return c;
}

//a += b * (10^k)
void addTo(vector<int>& a, const vector<int>& b, int k){
	int originalASize = a.size();
	if (a.size() < b.size() + k)
		a.resize(b.size() + k);
	a.push_back(0);

	int aSize = a.size();
	for (int i = originalASize; i < aSize; i++)
		a[i] = 0;

	int bSize = b.size();

	for (int i = 0; i < bSize; i++)
		a[i + k] += b[i];

	normalize(a);
}

// a -= b
// a>= b인 경우에만 사용 가능하다.
void subFrom(vector<int>& a, const vector<int>& b){
	int bSize = b.size();

	for (int i = 0; i < bSize; i++)
		a[i] -= b[i];
	normalize(a);
}

vector<int> karatsuba(const vector<int>& a, const vector<int>& b){
	int an = a.size(), bn = b.size();

	//a가 b보다 짧을 경우 둘을 바꾼다.
	if (an < bn)
		return karatsuba(b, a);
	//기저 사례 : a나 b가 비어있는 경우
	if (an == 0 || bn == 0)
		return vector<int>();
	//기저 사례 : a가 비교적 짧은 경우, O(n^2) 곱셈으로 변경한다.(성능을 위함)
	if (an <= 10)
		return multiply(a, b);
	int half = an / 2;

	vector<int> a0(a.begin(), a.begin() + half);
	vector<int> a1(a.begin() + half, a.end());
	vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
	vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

	//z2 = a1 * b1
	vector<int> z2 = karatsuba(a1, b1);

	//z0 = a0 * b0
	vector<int> z0 = karatsuba(a0, b0);

	//z1 = ((a0 + a1) * (b0 + b1)) - z0 - z2
	addTo(a0, a1, 0);
	addTo(b0, b1, 0);
	vector<int> z1 = karatsuba(a0, b0);
	subFrom(z1, z0);
	subFrom(z1, z2);

	//병합 과정
	//ret = z0+z1*10^half + z2 * 10(half*2)
	vector<int> ret(z2.size() + half * 2, 0);
	addTo(ret, z0, 0);
	addTo(ret, z1, half);
	addTo(ret, z2, half * 2);
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str_a, str_b;
	cin >> str_a >> str_b;

	vector<int> a, b;
	for (auto it = str_a.rbegin(); it != str_a.rend(); ++it)
		a.push_back(*it - '0');
	for (auto it = str_b.rbegin(); it != str_b.rend(); ++it)
		b.push_back(*it - '0');

	vector<int> c = karatsuba(b, a);
	for (auto it = c.rbegin(); it != c.rend(); ++it)
		cout << *it;

	return 0;
}

쿼드 트리 뒤집기

쿼드 트리(quad tree):

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 기법
주어진 공간을 항상 4개로 분할해 재귀적으로 표현한다
검은 색과 흰 색 밖에 없는 흑백 그림을 압축하여 표현할 때 사용한다

2^N * 2^N 크기의 흑백 그림을 문자열로 압축하기

모든 픽셀이 검은 색 일 경우 쿼드 트리의 압축 결과: b
모든 픽셀이 흰 색 일 경우 쿼드 트리의 압축 결과: w
모든 픽셀이 같은 색이 아니라면, 이 그림을 가로 세로로 각각 2등분해 4조각으로 쪼갠 뒤 각각을 쿼드 트리로 압축한다
-> 전체 그림의 압축 결과:
x(왼쪽 위 부분 압축 결과)(오른쪽 위 압축 결과)(왼쪽 아래 압축 결과)(오른쪽 아래 압축 결과)

쿼드 트리 뒤집기

쿼드 트리로 압축한 그림이 주어졌을 때,
이 그림을 상하로 뒤집은 그림을 쿼드 트리로 압축하여 출력하는 프로그램 작성하기

#include <string>

string reverse(string::iterator& it){
    char head = *it;
    ++it;
    
    if(head == 'w' || head == 'b')
        return string(1, head);

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