Chapter 7 분할정복

• 분할정복은 다음과 같은 과정으로 이뤄진다.

  1. 주어진 문제를 둘 이상의 부분 문제로 나눈다. (divide)
  2. 재귀 호출을 이용해 각 부분 문제를 계산한다. (recursive & base case)
  3. 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. (merge)

• 분할정복의 도드라지는 특징은 한 문제를 거의 같은 크기의 부분 문제들로 나눈다는 점이다.

• 분할정복으로 문제를 풀기 위해서는 다음과 같은 물음들에 대한 답이 필요하다.

  1. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있는가?
  2. 부분 문제들의 답이 곧 전체 답으로 효율적으로 이어지는가?
  • 분할정복은 일반적인 재귀호출로 문제를 풀이하는 것보다 훨씬 빠르다.
  • 분할정복은 일반적인 재귀호출이 흔히 가질 수 있는 ‘중복 호출(Overlapped call)’문제가 상대적으로 적다.

• 

  • 분할정복은 문제를 어떻게 분할하느냐에 따라 효율성에 차이가 있다. 따라서 문제 특성에 따라 문제를 잘 분할하는 것이 중요하다.
    • 예를 들어, 위 그림은 ‘행렬의 거듭제곱’에 분할정복을 적용한 것을 그림으로 나타낸 것이다.
    • (a) 홀수를 절반으로 나누는 경우 pow(A, 4)는 총 3번 호출되며 pow(A, 2)는 4번 호출된다. 같은 답을 구하는 과정에서 수 많은 중복 호출과 낭비가 발생한다.
    • (b) 홀수에서 1을 빼서 짝수로 만드는 경우 모든 함수는 한 번씩 호출되어 우리가 원하는 ‘base case’까지 도달하게 된다.

교재에는 ^1)^ 수열의 합과 ^2)^ 병합정렬/퀵정렬로 간단히 분할정복에 대한 개념을 설명하고 있지만 기본적인 내용이므로 생략한다.

Ex01 - 카라츠바 빠른 곱셈 알고리즘 (Karatsuba)

• 우리가 일반적으로 사용하는 int자료형은 4Byte로 일반적으로 약 ±21억까지 표현할 수 있다.
• 만일, 수 천, 수 만 자리 수의 곱셈을 하는 경우 우리가 사용할 수 있는 최대 자료형 unsigned long long 으로도 계산할 수 없기 때문에 배열을 이용해서 해결해야 한다.

• 좌측 사진은 사람이 일반적으로 수행하는 곱셈 과정을 나타낸 그림이다. 그러나 컴퓨터가 수행하기에는 매 연산에서 ‘올림’과 ‘내림’ 과정을 거치는 것은 비효율적이다.

• 우측 사진은 컴퓨터가 일반적으로 수행하는 곱셈 과정을 나타낸 그림이다. ‘올림’ 과정, 그러니까 ‘정상화(normalization)과정’은 모든 계산이 끝난 뒤 1회만 수행하면 된다.

• 두 정수의 길이가 n이라고 할 때 시간복잡도는 O(n^2^)임을 알 수 있다.
  일반적으로 두 정수의 곱의 시간복잡도는 이보다 빨라질 수 없을 것이라고 알려져있었지만, 1960년 카라츠바에 의해 이것보다 더 빠른 O(n^log3^) 알고리즘이 등장하게 되었다.

• $a = a_1\times10^{128} + a_0 \\ b = b_1\times10^{128} + b_0 \\ a \times b = a_1\times b_1 \times 10^{256} + (a_1\times b_0 + a_0\times b_1)\times 10^{128} + a_0\times b_0$

  • a와 b가 256자리 수라고 가정하자. a~1~과 b~1~은 모두 256을 절반으로 나눈 첫 128자리를 의미하고 a~0~와 b~0~는 나머지 자리를 의미한다. (교재에는 설명이 부족하지만 a와 b가 꼭 같은 자리 수일 필요가 없다.)
  • 카라츠바 알고리즘의 핵심은 큰 정수 두 개를 한 번에 곱하는 것을 작은 조각을 4번 곱하는 것으로 생각하고, 4번의 곱셈을 3번의 곱셈으로 바꾸는데 있다.
  • Z~2~를 a~1~×b~1~ 이라고 하고 Z~0~를 a~0~×b~0~ 이라고 한다면, Z~1~은 (a~0~+a~1~)×(b~0~+b~1~) - Z~2~ - Z~0~ 이다. 이 과정은 곱셈을 3번 밖에 사용하지 않는다!

• 자료형으로 나타낼 수 없는 큰 수를 표현하기 위해 배열을 사용한다는 점 그리고 빠른 연산을 위해 큰 문제를 4개의 작은 문제로 나눈 다음 연산 횟수를 줄이는 일련의 과정은 분할정복의 핵심이라 할 수 있다.

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

void normalize(vector<int> &c) {
    c.push_back(0);
    for (int i = 0; i + 1 < c.size(); i++) {
        if (c[i] < 0) {
            int borrow = (abs(c[i]) + 9) / 10;
            c[i + 1] -= borrow;
            c[i] = borrow * 10;
        } else {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
    while (c.size() > 1 && c.back() == 0) c.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;
}

void addTo(vector<int> &a, vector<int>& b, int k) {
    int newsize = a.size() < b.size() + k ? b.size() + k : a.size();
    while (a.size() != newsize) a.push_back(0);
    for (int i = k; i < newsize; i++) {
        a[i] = a[i] + b[i - k];
    }
    normalize(a);
}
 
void subFrom(vector<int> &a, vector<int>& b) {
    for (int i = 0; i < b.size(); i++) {
        a[i] -= b[i];
    }
    normalize(a);
}

vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
	int aSize = a.size(), bSize = b.size();
	
	if (aSize == 0 || bSize == 0) return vector<int>();   // [기저 1]
	if (aSize < bSize) karatsuba(b, a);                   // [기저 2]
	if (aSize <= 150) return multiply(a, b);              // [기저 3] - 150자리 이하인 경우
	
	int half = aSize / 2;   // 절반으로 자릿수를 나눈뒤
	
	vector<int> a0(begin(a), begin(a) + half); 
	vector<int> a1(begin(a) + half, end(a));
	vector<int> b0(begin(b), begin(b) + min(bSize, half));
	vector<int> b1(begin(b) + min(bSize, half), end(b));
	
	vector<int> z0(karatsuba(a0, b0));
	vector<int> z2(karatsuba(a1, b1));
	
	addTo(a0, a1, 0); // a0 + a1
	addTo(b0, b1, 0); // b0 + b1
	
	vector<int> z1(karatsuba(a0, b0));
	
	subFrom(z1, z0);  
	subFrom(z1, z2);  // z1 - z0 - z2
	
	vector<int> ret;
	addTo(ret, z0, 0);
	addTo(ret, z1, half);
	addTo(ret, z2, 2 * half);
	
	return ret;
}


int main() {
   vector<int> a, b;
   string number;

    cout << "첫 번째 정수를 입력해주세요 >> ";   cin >> number;
	for (auto i = number.size() - 1; i <= number.size(); --i) a.push_back(number[i]);
	
	cout << "두 번째 정수를 입력해주세요 >> ";   cin >> number;
	for (auto i = number.size() - 1; i <= number.size(); --i) b.push_back(number[i]);
	
	vector<int> result(multiply(a, b));
	cout << "Result of func 'multiply' >> ";
	for(const auto& i : result) cout << i; cout << '\n';
	
	result = karatsuba(a, b);
	cout << "Result of func 'karatsuba' >> ";
	for(const auto& i : result) cout << i; cout << '\n';
}

물론 입력받은 두 수가 150자리 미만이므로 정확히는 카라츠바 알고리즘을 수행한게 아니라 일반적인 알고리즘을 수행한거지만...ㅎㅎ 그래도 어떻게 동작하는지 파악했으면 됐다.

Ex 02 - 쿼드 트리 뒤집기 (QUADTREE, 下)

• 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(Quadtree)가 있다.
• 쿼드 트리는 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하며 흑백 그림을 압축해서 표현할 때 유용하다.
  • [규칙 1] :: 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b다.
  • [규칙 2] :: 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w다.
  • [규칙 3] :: 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x다.

• 쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력해야 한다.

문제 해결 과정

1. x가 확인될 경우, 큰 문제에서 작은 문제로 이동해야 함을 직관적으로 알 수 있다. -> 재귀를 이용해야 한다.
2. 한 번에 네 구역씩 나뉘므로 분할정복 문제임을 직관적으로 알 수 있다.
3. 그림을 상하로 뒤집는다는 것은 abcd로 표현되는 쿼드트리를 cdab로 표현하는 것과 같다.

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

static int caseNum = 0;

string doReverse(string::iterator& itr) {
	char ch = *(itr++);
	// [기저] - b, w면 재귀를 돌 필요없이 바로 값 반환
	if (ch == 'b' || ch == 'w') return string(1, ch);

	string one = doReverse(itr);	// 좌측 상단
	string two = doReverse(itr);	// 우측 상단
	string three = doReverse(itr);	// 좌측 하단
	string four = doReverse(itr);	// 우측 하단

	return string("x") + three + four + one + two;	// 1234 -> 3412
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> caseNum;
	
	string* input = new string[caseNum];

	for (int i = 0; i < caseNum; ++i) cin >> input[i];

	for (int i = 0; i < caseNum; ++i) {
		auto itr = begin(input[i]);
		cout << doReverse(itr) << '\n';
	}
}

Ex 03 - 팬미팅 (FANMEETING, 上)

팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖는다. M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 포옹한다.

아이돌 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 하기로 했다. 이때 팬 미팅이 진행되는 과정에서 모든 멤버가 동시에 포옹을 하는 일이 몇 번이나 있는가?

문제 해결 과정

• 멤버와 팬의 수는 20만 이하의 정수이므로 단순히 시뮬레이션을 구현하는 것으로는 시간제한 10초내로 풀기 힘들다.
• 이 문제를 빠르게 푸는 방법은 두 큰 수의 곱셈으로 문제를 바꿔서 푸는 것이다.

• 상단의 수식은 6자리 수 B와 3자리 수 A의 곱을 도식화해 나타낸 그림이다. 중요한 것은 $C_i = A_0 \times B_i + A_1 \times B_{i-1} + A_2 \times B_{i-2}$ 라는 수식을 얻을 수 있다는 것이다.
• 조금 더 나아가자. M과 F로 이루어진 입력 문자열을 1과 0으로 대칭한다면, 남자와 남자가 만나는 경우를 제외하면 모두 곱이 0이다. 따라서 C~i~가 0이라면 해당 위치에서 남성-남성이 만나는 일이 없고 따라서 모든 멤버가 포옹을 한다는 것을 알 수 있다.

int getAnswer(const string& member, const string& fan) {
	int memSize(member.size()), fanSize(fan.size());

	vector<int> tempM(memSize), tempF(fanSize);
	for (int i = 0; i < memSize; ++i) tempM[i] = (member[i] == 'M');
	for (int i = 0; i < fanSize; ++i) tempF[fanSize - i - 1] = (fan[i] == 'M');

	vector<int> ret = karatsuba(tempM, tempF);

	int count = 0;
	for (int i = memSize - 1; i < fanSize; ++i)
		if (ret[i] == 0)
			++count;
	return count;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int caseNum = 0; cin >> caseNum;

	string mem, fan;

	for (int i = 0; i < caseNum; ++i) {
		cin >> mem >> fan;
		cout << getAnswer(mem, fan) << '\n';
	}
}