7.1 도입
Divide & Conquer은 유명한 알고리즘 패러다임이다.
분할정복 알고리즘은 문제를 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.
일반적인 재귀호출과 다른 점은 문제를 한조각과 나머지로 나누는 대신, 비슷한 크기의 부분문제로 나누는 것이다.
분할정복을 사용하는 알고리즘은 대개 세가지의 구성요소를 갖는다.
- 문제를 더 작은 문제로 분할하는 과정 (divide)
- 각 문제에 대해 구한 답을 원래 문제의 답으로 병합하는 과정 (merge)
- 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)
분할정복으로 문제를 풀기 위해서는 문제에 몇가지 특성이 있어야 한다.
문제를 둘 이상의 부분 문제로 나누는 것이 자연스러워야하며, 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야한다.
분할정복의 장점은 같은 작업을 더 빠르게 처리하는 것이다.
7.2 문제: 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하)
쿼드 트리는 대량의 좌표 데이터를 메모리안에 압축해 저장하기 위해 사용하는 기법이다.
주어진 공간을 4개로 분할해 재귀적으로 표현하기에 쿼드 트리라는 이름이 붙었다.
가장 대표적인 사용처는 흑백 이미지를 압축해서 표현하는 것이다.
쿼드 트리는 2ⁿ X 2ⁿ 크기의 흑백 이미지를 다음과 같이 문자열로 압축한다.
이미지의 모든 픽셀이 검은 색인 경우 쿼드 트리로 변환한 결과는 그림의 크기와 관계없이 b가 된다.
이미지의 모든 픽셀이 흰 색인 경우 쿼드 트리로 변환한 결과는 그림의 크기와 관계없이 w가 된다.
모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 이미지를 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축한다. 압축 결과는 x(좌상단 압축결과)(우상단 압축결과)(좌하단 압축결과)(우하단 압축결과)가 된다.
쿼드트리로 압축된 흑백 이미지가 주어졌을 때, 이 이미지를 상하로 뒤집은 이미지를 쿼드트리 압축하여 출력하는 프로그램을 작성하시오.
시간 및 메모리 제한
프로그램은 1초안에 실행되어야 하며, 64MB이하의 메모리를 사용해야 한다.
입력
첫 줄에 테스트 케이스의 개수 C(C≤50)가 주어진다. 그 후 C줄에 하나씩 쿼드 트리로 압축된 텍스트가 주어진다. 문자열의 길이는 1000이하이고, 원본 이미지의 크기는 2^20 X 2^20을 넘지 않는다.
출력
상하로 뒤집은 쿼드트리 텍스트를 출력한다.
7.3 풀이: 쿼드 트리 뒤집기
문제를 푸는 가장 무식한 방법은 쿼드 트리로 실제 이미지를 얻고 상하반전한 뒤 다시 쿼드트리 압축하는 것이다.
그러나 제한에 걸려 이 방법을 사용할 수 없다.
이런경우 선택가능한 방법은 두가지이다.
- 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
- 작은 입력에 대해서만 동작하는 단순한 알고리즘으로부터 시작해서 최적화해 나가기
시행착오와 경험이 중요하다.
쿼드 트리 압축 풀기
쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제하는 과정은 재귀 호출로 구현하는 것이 자연스럽다.
문자열 s의 압축을 해제해서 배열에 저장하는 함수 decompress()를 구현하자.
base case는 s의 첫 글자가 w나 b인 경우이다. 이 경우 배열에 저장 후 종료한다.
첫 글자가 x라면 s의 나머지 부분을 넷으로 쪼개 재귀 호출한다.
이 때 각 부분이 배열의 어느 부분에 저장되어야 하는지 지정하는 위치 오프셋도 전달해야한다.
char decompressed[MAX_SIZE][MAX_SIZE];
void decompress(const string& s, int y, int x, int size);
압축 문자열 분할하기
구현을 시작하면 s의 나머지 부분을 넷으로 쪼개기가 까다롭다는 사실을 깨닫게 된다.
각 부분의 길이가 일정하지 않기 때문이다.
이를 해결할 수 있는 첫 번째 방법은 주어진 위치에서 시작하는 압축결과의 길이를 반환하는 함수 getChunkLength()를 만드는 것이다.
s[0]이 x라고 하면 왼쪽 위 조각을 나타내는 부분은 항상 s[1]에서부터 시작한다.
이 때 getChunkLength(s, 1)이 해당 부분의 길이를 반환하도록 하는 것이다. 그 후 반환한 값에 이전 위치를 더해서 다음 부분을 구할 수 있다.
이 함수를 작성하는 것은 어렵지 않지만, 비슷한 일을 하는 함수를 나누어 작성하는 것이 마음에 들지 않을 것이다.
이럴 때 유용한 패턴은 s를 미리 쪼개는 것이 아니라 decompress()함수에서 '필요한 만큼 가져다 쓰도록' 하는 것 이다.
s를 통째로 전달하는 것이 아니라, s의 한 글자를 가리키는 포인터를 전달한다.
함수 내에서는 한 글자를 검사할 때마다 포인터를 앞으로 옮긴다.
char decompressed[MAX_SIZE][MAX_SIZE]
void decompress(string::iterator& it, int y, iny x, int size){
//한글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
char head = *(it++);
//base case: 첫 글자가 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;
decompress(it, y, x, half);
decompress(it, y, x+half, half);
decompress(it, y+half, x, half);
decompress(it, y+half, x+half, half);
}
}
압축 다 풀지 않고 뒤집기
string reverse(string::iterator& it){
char head = *iter;
++iter;
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;
}
카라츠바