주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부문 문제의 답으로부터 전체 문제의 답을 계산한다.
세 가지 구성 요소
문제를 더 작은 문제로 분할하는 과정(divide)
각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)
수열의 빠른 합과 행렬의 빠른 제곱
fastSum(n) = 2*fastSum(n/2)+(n^2/4)
//필수 조건: n은 자연수
//1 + 2 + ... + n을 반환한다.
int fastSum(int n) {
//기저 사례
if(n == 1) return 1;
if(n % 2 == 1) return fastSum(n-1) + n;
return 2*fastSum(n/2) + (n/2)*(n/2);
}
행렬의 거듭제곱
A^m = (A^(m/2))*(A^(m/2))
//정방행렬을 표현하는 SqureMatrix 클래스가 있다고 가정하자.
class SquareMatrix;
// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
//A^m을 반환한다.
SquareMatrix pow(const SqureMatrix& A, int m) {
//기저 사례: A^0 = 1
if(m == 0) return identity(A.size());
if( m % 2 > 0) return pow(A, m-1) * A;
SquareMatrix half = pow(A, m /2);
//A^m = (A^(m/2))*(A^(m/2))
return half * half;
}
나누어 떨어지지 않을 때의 분할과 시간 복잡도
같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다.
Why? 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있다.
병합 정렬과 퀵 정렬
1. 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다.
2. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻습니다.
1. 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할
=> 퀵 정렬은 파티션이라고 부르는 단계를 도입하는데, 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보낸다.
일반적인 곱셈 알고리즘
//num[]의 자릿수 올림을 처리한다.
void nomalize(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();
}
// 두 긴 자연수의 곱을 반환한다.
// 각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다.
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];
nomalize(c);
return c;
}
예제: 카라츠바의 빠른 곱셈 알고리즘
카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갠다. a와 b가 각각 256자리 수라면 a1 과 b1은 첫 128자리, a0 과 b0은 그 다음 128자리를 저장하도록 하는 것이다.
a = a1 * 10^128 + a0
b = b1 * 10^128 + b0
a*b = (a1 * 10^128 + a0)*(b1 * 10^128 + b0)
= a1 * b1 * 10^256 + (a1 * b0 + a0 * b1) * 10^256 + a0 * b0
z2 z1 z0
z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;
=> 곱셈을 세 번밖에 쓰지 않는다.
// a += b * (10 ^ k)
void addTo(vector<int>& a, const vector<int>& b, int k);
// a -= b; a>=b를 가정
void subFrom(vector<int>& a, const vector<int>& b);
// 두 긴 정수의 곱을 반환한다.
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 <= 50) return multiply(a, b);
int half = an / 2;
// a 와 b를 밑에서 half 자리와 나머지로 분리한다.
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);
//a0 = a0 + a1; b0 = b0 + b1
addTo(a0, a1, 0); addTo(b0, b1, 0);
//z1 = (a0*b0) - z0 - z2
vector<int> z1 = karatsuba(a0, b0);
subFrom(z1, z0);
subFrom(z1, z2);
//ret = z0 + z1 * 10^half + z2 * 10^(half*2)
vector<int> ret;
addTo(ret, z0, 0);
addTo(ret, z1, half);
addTo(ret, z2, half + half);
return ret;
}
쿼드 트리 뒤집기
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 하나
주어진 공간을 항상 4개로 분할해 재귀적으로 표현함
검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현
1. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림과 관계없이 b가 된다.
2. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
3. 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 된다.
쿼드 트리 압축 풀기
char decompressed[MAX_SIZE][MAX_SIZE];
// s를 압축 해제해서 decompressed[y..y+size-1][x..x+size-1] 구간에 쓴다.
void decompress(const string& s. int y , int x, int size);
압축 문자열 분할하기
s의 나머지 부분을 넷으로 쪼개기가 어렵다
why? 각 부분의 길이가 일정하지 않다.
solution
1. 주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 함수를 만든다.
ex) s[0]이 x라고 할 때, 왼쪽위==s[1]이면 getChunkLength(s,1)이 해당 부분의 길이를 반환
getChunkLength(s, 1)이 4를 반환한다고 할 때, 다음 조각은 s[5]부터 시작
2. s를 미리 쪼개는 것이 아닌 decompress()함수에서 '필요한 만큼 가져다 쓰도록' 한다.
decompress() 함수에 s를 통째로 전달하는 것이 아닌, s의 한 글자를 가리키는 포인터를 전달한 후 함수 내에서 한 글자를 검사할 때마다 이 포인터를 앞으로 한 칸씩 옮긴다.
char decompressed[MAX_SIZE][MAX_SIZE];
void decompressed(string::iterator& it, int y, int x, int size) {
// 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
char head = *(it++);
// 기저 사례: 첫 글자가 b 또른 w인 경우
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 {
// 네 부분을 순서대로 압축 해제
int half = size / 2;
decompressed(it, y, x, half);
decompressed(it, y, x + half, half);
decompressed(it, y + half, x, half);
decompressed(it, y + half, x + half, half);
}
}
압축 다 풀지 않고 뒤집기
string reverse(string::iterator& it) {
char head = *it;
++it;
if (head == 'b' || head == 'w')
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;
}
울타리 잘라내기
분할 정복 알고리즘의 설계
가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다.
가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.
가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.
//각 판자의 높이를 저장하는 배열
vector<int> h;
// h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다.
int solve(int left, int right) {
//기저 사례:판자가 하나밖에 없는 경우
if (left == right) return h[left];
// [left, mid], [mid + 1, right]의 두 구간으로 문제를 분할한다.
int mid = (left + right) / 2;
// 분할한 문제를 각개격파
int ret = max(solve(left, mid), solve(mid + 1, right));
// 부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
int lo = mid, hi = mid + 1;
int height = min(h[lo], h[hi]);
// [mid, mid+1]만 포함하는 너비 2인 사각형을 고려
ret = max(ret, height * 2);
// 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
while (left < lo || hi < right) {
//항상 높이가 더 높은 쪽으로 확장
if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
++hi;
height = min(height, h[hi]);
}
else {
--lo;
height = min(height, h[lo]);
}
// 확장한 후 사각형의 넓이
ret = max(ret, height * (hi - lo + 1));
}
return ret;
}
정당성
양쪽 부분 문제에 걸쳐있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳다.
알고리즘에서는 너비가 2인 사각형에서 시작해서 한 칸씩 사각형의 너비를 늘려가므로,
우리가 고려한 사각형들 중 R과 너비가 같은 사각형(R')이 반드시 하나 있다.
너비가 같으면 높이가 높은 쪽이 크기가 크다.
팬미팅
int hugs(const string& members, const string& fans) {
int N = members.size(), M = fans.size();
vector<int> A(N), B(M);
for (int i = 0; i < N; i++) A[i] = (members[i] == 'M');
for (int i = 0; i < M; i++) B[M - 1 - i] = (fans[i] == 'M');
//karatsuba 알고리즘에서 자리 올림은 생략한다.
vector<int> C = karatsuba(A, B);
int allHugs = 0;
for (int i = N - 1; i < M; i++)
if (C[i] == 0)
++allHugs;
return allHugs;
}
댓글 없음:
댓글 쓰기