이글은 STL에 대해서 조금이라도 알고 계신 분들을 위한 설명입니다.
김지혜 님이 쓰신 글 :
: 10개 이상의 수를 사용자 임의로 입력받아서 그 중 크기 순으로 작은 수 10개를 출력하는
: 프로그램인데요.
만약, 문제가 여기까지라면, 이 문제를 푸는 것은 정말 쉽겠죠?
그냥 배열이나 vector에 전부 때려 넣은 후, partial_sort 알고리듬을 쓰면 간단합니다.
int main()
{
const int sort_end = 10;
cout << "Enter more numbers. Press [Ctrl+Z] and Enter to quit.\n";
vector<int> v((istream_iterator<int>(cin)), istream_iterator<int>());
partial_sort(v.begin(), v.begin() + sort_end, v.end());
copy(v.begin(), v.begin() + sort_end, ostream_iterator<int>(cout, " "));
cout.put('\n');
return 0 ;
}
: (단, 10보다 큰 사이즈의 배열을 사용하면 안된다.)
그런데 문제는 이와 같이 크기가 10으로 고정된 배열을 사용해야 한다는 겁니다.
배열이 아닌 다른 컨테이너를 쓸 수 있다면, 연관 컨테이너인 multiset을 사용하는 방법이 있습니다.
int main()
{
const int set_size = 10;
multiset<int> ms;
int input;
cout << "Enter 10 numbers: ";
for (int i = 0; i < set_size; ++i) {
cin >> input;
ms.insert(input);
}
cout << "Enter more numbers. Press [Ctrl+Z] and Enter to quit.\n";
multiset<int>::reverse_iterator ri;
while (cin >> input) { // 주의: 컨테이너의 마지막 원소의 위치는
ri = ms.rbegin(); // end()가 아니라,rbegin()입니다.
if (input < *ri) {
ms.erase((++ri).base()); // ri가 가리키는 요소를 삭제하는 방법
ms.insert(input);
}
}
copy(ms.begin(), ms.end(), ostream_iterator<int>(cout, " "));
cout.put('\n');
return 0 ;
}
또는 이와 유사한 방법으로서, list를 sort 멤버함수로 정렬한 후,
원소를 삽입할 위치를 이진 검색 알고리듬인 lower_bound 나 upper_bound 또는 equal_range으로 검색하여 새 원소를 삽입/삭제하는 방법도 있습니다.
이상의 방법의 복잡도는 O(N log N)으로서 상당히 빠릅니다.
그러나 여기서는 배열을 써야 한다는 조건이 있으므로, 다르게 구현해야 합니다.
임문환님의 방법과 같이 새 값을 삽입할 때마다 max_element() 알고리듬으로 위치를 검색해야 한다면, O(N^2)의 복잡도를 갖게 되므로 효율이 떨어지는 방법입니다.
즉, 배열을 multiset과 같이 원소의 삽입, 삭제에 O(log N)이 걸리도록 하는 방법을 사용해야 합니다. 이러한 자료구조를 힙(heap)라고 합니다. 힙 자체에 대한 자세한 설명은 모든 자료구조 책에 다 나와있습니다.
STL에서도 일반적인 시퀀스 컨테이너를 힙으로 사용할 수 있게하는 알고리듬을 제공합니다.
이에 대해서는 제가 C/C++ Tip'N Tricks에 간단한 소개를 올렸습니다.
http://www.borlandforum.com/impboard/impboard.dll?action=read&db=cpp_tip&no=21
여기서는 이들 네가지 STL 힙 알고리듬을 이 문제에 적용하여 풀어보겠습니다.
int main()
{
const int heap_size = 10;
int input, heap[heap_size];
ostream_iterator<int> out(cout, " "); // 출력 반복자 정의
cout << "Enter 10 numbers: ";
// heap[0..9]까지 입력받음
for (int i = 0; i < heap_size; ++i) {
cin >> input;
heap[i] = input;
}
// heap[0..9]를 힙으로 만듦: O(N) 복잡도
make_heap(&heap[0], &heap[heap_size]);
#ifdef _DEBUG // 디버그 모드에서는 힙의 내용 출력
cout << "After make_heap : ";
copy(&heap[0], &heap[heap_size], out); cout.put('\n');
#endif
pop_heap( &heap[0], &heap[heap_size]); // 가장 큰 값을 pop: O(log N)
#ifdef _DEBUG
cout << "After pop_heap : ";
copy(&heap[0], &heap[heap_size], out); cout.put('\n');
#endif
cout << "Enter more numbers. Press [Ctrl+Z] and Enter to quit.\n";
while (cin >> input) {
heap[heap_size - 1] = input; // push할 원소를 마지막에 놓음
push_heap(&heap[0], &heap[heap_size]); // 힙에 push: O(log N)
#ifdef _DEBUG
cout << "After push_heap : ";
copy(&heap[0], &heap[heap_size], out); cout.put('\n');
#endif
pop_heap( &heap[0], &heap[heap_size]); // 가장 큰 값을 pop: O(log N)
#ifdef _DEBUG
cout << "After pop_heap : ";
copy(&heap[0], &heap[heap_size], out); cout.put('\n');
#endif
}
// 힙 전용 정렬 알고리듬: sort보다 상수배 만큼 빠릅니다. 그러므로 O(N log N)
sort_heap(&heap[0], &heap[heap_size]);
cout << "After sort_heap : "; // 당연히 sort_heap 후에는 더이상 힙이 아닙니다.
copy(&heap[0], &heap[heap_size], out); cout.put('\n');
return 0 ;
}
결과는 다음과 같습니다.
Enter 10 numbers: 3 4 5 6 7 5 6 7 8 9
After make_heap : 9 8 6 7 7 5 5 3 6 4
After pop_heap : 8 7 6 7 4 5 5 3 6 9
Enter more numbers. Press [Ctrl+Z] and Enter to quit.
1
After push_heap : 8 7 6 7 4 5 5 3 6 1
After pop_heap : 7 7 6 6 4 5 5 3 1 8
2
After push_heap : 7 7 6 6 4 5 5 3 1 2
After pop_heap : 7 6 6 3 4 5 5 2 1 7
3
After push_heap : 7 6 6 3 4 5 5 2 1 3
After pop_heap : 6 6 5 3 4 5 3 2 1 7
4
After push_heap : 6 6 5 3 4 5 3 2 1 4
After pop_heap : 6 4 5 3 4 5 3 2 1 6
^Z
After sort_heap : 1 2 3 3 4 4 5 5 6 6
참고로, partial_sort도 힙 정렬 알고리듬을 사용하여 구현되어 있습니다.
이와 같이 사용할 수 있는 공간이 제한될 때는 힙이 유용하게 사용됩니다.
