알고리즘 문제 해결 전략 2 6장 트리 (5)

22.7 문제: 삽입 정렬 뒤집기

삽입 정렬은 A가 정렬된 배열일 때, A[i]를 적절한 위치를 만날 때까지 왼쪽으로 한 칸씩 움직임. 예제에서 각 위치에 있는 값들이 움직인 칸수를 표현하면 {0, 1, 1, 2, 3}이 됨. 이때 원래 수열을 찾아내는 프로그램을 작성하시오.

 

22.8 풀이: 삽입 정렬 뒤집기

이 알고리즘을 구현하기 위해서는 후보들의 집합 중 k번째 원소가 무엇인지를 찾고, 삭제하는 작업을 빠르게 수행할 수 있어야 함. 이진 검색 트리를 사용하면 이런 일을 O(lgN) 시간에 할 수 있음. 

void solve() {
	Node* candidates = NULL;
	for (int i = 0; i < n; ++i)
		candidates = insert(candidates, new Node(i + 1));
	for (int i = n - 1; i >= 0; --i) {
		int larger = shifted[i];
		Node* k = kth(candidates, i + 1 - larger);
		A[i] = k->key;
		candidates = erase(candidates, k->key);
	}
}

 

23 우선순위 큐와 힙

23.1 도입

우선순위가 가장 높은 자료가 가장 먼저 꺼내짐. 원소들을 우선순위로 정렬해 두면 최대 원소를 찾아 삭제하는 일과 새 원소를 삽입하는 일을 모두 O(lgN)시간에 할 수 있음. 우선순위 큐는 이진 검색 트리보다 훨씬 단순한 구조로도 구현할 수 있음. 힙은 가장 큰 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 모두 O(lgN)시간에 수행할 수 있음. 실제로 힙을 사용하면 우선순위 큐를 쉽게 구현할 수 있음. 

 

23.2 힙의 정의와 구현

힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이라는 것임. 힙의 대소 관계 규칙. 부모 자식 관계에만 적용됨. 이 규칙에 의하면 트리에서 가장 큰 원소는 항상 트리의 루트에 들어가므로, 최대 원소를 빨리 찾기를 원하는 힙의 목적에 부합함. 힙의 모양 규칙은 다음과 같은 두 가지의 조건으로 이루어짐. 

1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 함.

2. 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 함.

이 두 가지의 모양 규칙을 모두 만족한다면, 트리에 포함된 노드의 개수만으로 트리의 모양이 정해짐.

 

배열을 이용한 힙의 구현

 

새 원소의 삽입

void push_heap(vector<int>& heap, int newValue) {
	heap.push_back(newValue);
	int idx = heap.size();
	while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
		swap(heap[idx], heap[(idx - 1) / 2]);
		idx = (idx - 1) / 2;
	}
}

 

최대 원소 꺼내기

힙의 모양 구조에 의하면 힙의 마지막에 있는 노드는 어차피 지워질 운명이니, 이 노드를 일단 지우고 시작함. 이 노드는 리프이기 때문에 이 노드가 지워진다고 해도 힙의 구조에 끼치는 영향은 없음.

void pop_hea(vector<int>& heap){
	heap[0] = heap.back();
	heap.pop_back();
	int here = 0;
	while (true) {
		int left = here * 2 + 1, right = here * 2 + 2;
		if (left >= heap.size()) break;
		int next = here;
		if (heap[next] < heap[left])
			next = left;
		if (right < heap.size() && heap[next] < heap[right])
			next = right;
		if (next == here) break;
		swap(heap[here], heap[next]);
		here = next;
	}
}

 

힙 정렬은 병합 정렬과는 달리 추가적인 메로리를 요구하지 않으면서, 최악의 경우에는 O(NlgN)시간 복잡도만 요구하기 때문에 유명함. 이 외에 종종 유용하게 사용되는 연산이 이미 힙에 들어 있는 원소 중 하나를 증가시키는 것임.

 

23.3 문제: 변화하는 중간 값

한 수열의 중간 값은 이 수열을 정렬했을 때 가운데 오는 값입니다. 수열의 길이가 짝수일 떄는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간 값이라고 정의하도록 합시다. 

 

23.4 풀이: 변화하는 중간 값

이진 검색 트리를 사용하지 않고 이 문제를 푸는 한 가지 방법. 주어진 수열의 숫자들을 두 묶음으로 나누는 것임. 숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣도록 함. 

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 큼

2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같음.

이제 이 수열의 중간값은 항상 최대 힙의 루트에 있게 됨. 

 

시간 복잡도는 같지만, 힙은 대개 배열로 구현되기 때문에 노드들을 접근하기 위해 포인터를 따라가야 하는 트립보다 훨씬 빠름. 보통 2~3배. 환경이나 컴파일러에 따라 다르지만.

 

수열 생성하기

수행 시간을 지배할 정도로 입력의 양이 많을 떄는 난수 생성기를 통해 입력을 생성하는 경우가 종종 있음. 이 문제에서 사용하는 난수 생성기는 가장 흔한 형태의 난수 생성기인 선형 합동 난수 생성기임. 

struct RNG {
	int seed, a, b;
	RNG(int _a, int _b):a(_a), b(_b), seed(1983) {}
	int next() {
		int ret = seed;
		seed = ((seed * (long long)a) + b) % 20090711;
		return ret;
	}
};