[알고리즘 #3] Sorting, Searching, Data Structures(2)

Set

집합을 관리하기 위한  자료구조이다. 

- 구현하려면   C++ 에서는 BST(Balanced binary search tree(red-balck tree)  로 구현한다.

-  c++ set library 이용하면 기본적인 searching 과 update 를 모두 O(log n) 시간에 수행 가능하다.

- c++ 에서는 set 의 element 간에 순서가 정해지지 않은 경우 사용할 수 있는 unordered_set library 또한 지원한다.이는 hash table 로 구현되어 있으며 따라서 모든 연산을 AVERAGE O(1) 에 구현 가능하다. => 경시대회에서는 거의 쓰지않음

 

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

int main() {
set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);
cout << s.count(3) << endl;
cout << s.count(4) << endl;
s.erase(3);
s.insert(4);
cout << s.count(3) << endl;
cout << s.count(4) << endl;
}

cout << s.size() << endl;
for (auto x : s)  //  SET 원소 순회
{
cout << x << endl;
}
auto it = s.find(7); // 원하는 원소를 찾는 과정
if (it == s.end())
{
cout << "7 is not found" << endl;
}

Set  에서 가장 큰 element와 작은 element 찾기

auto first = s.begin();

auto last = s.end(); last--; // end()함수는 마지막이 아닌 마지막 다음 위치를 나타내는 프린터이므로 --해준다.

 

특정 element 이상 첫번째  element 출력

cout << *s.lower_bound(x) << endl;      //x 이상인데 가장 작은 첫번째 element 출력

cout << *s.upper_bound(x) << endl;     

 

 

Map

<key, value> pair 을 관리하기 위한 data structure 이다

- Set 과 마찬가지로 C++ 에서는 balanced binary search tree(red-black tree) 로 map library 를 구현한다.

즉 기본적인 searching과 update 를 모두 O(log n) 시간에 수행 가능하다.

 

- Map 에서 각 Key 는 반드시 Unique 해야 하며 C++ 에서는 중복된 key 값을 허용하는 multimap library 를 따로 지원한다.

- Unordered_set 과 마찬가지로 C++ 에서는 Hash table 로 구현된 unordered_map library 또한 지원한다.  ( 경시대회는 적합x)

map<string, int> m;
m["monkey"] = 4;
m["banana"] = 3;
m["harpsichord"] = 9;
cout << m["banana"] << endl;
//없는 키값 접근시 <해당키, 0> 을 map 에 추가한다.
cout << m["akdljf"] << endl;

if (m.count("banana"))
{
//key exists
// 0 이면 존재 x, 1이면 존재
} for (auto x : m)
{
cout << x.first << " " << x.second << endl;
//x.first = key / x.second = value
}

 

ex) Uva 11572 Unique Snowflakes

주어진 sequence 에서 unique element 만으로 이루어진 가장 긴 substring의 길이를 출력하는 문제

linear search 로 해결할 경우 O(n^2) 시간이 걸림

linear search 를 한번만 수행하면서 같은 원소 k를 만난 경우 1. 현재 저장된 최대 개수 혹은 2. 이전에 마지막으로 k가 저장된 다음 위치로부터 count 한 snowflake 의 개수들 중 하나만 답이 된다. (Why)

다만 모든 종류의 snowflake 에 대해 마지막 위치를 저장할 경우 경우의 수가 10^9이므로 메모리 제한을 넘어갈 것으로 보인다.

 

 

Priority Queue

Insert : element 추가

Findmin : Priority 가 가장 높은 element 반환

Deletemin: Priority 가 가장 높은 element 제거

 

- 보통 findmin 과 그 외 operation 들 간의 balance 를 고려하여 모든 연산을 O(log n) 에 지원하는 binary heap 으로 구현

 

- 'Priority 가 높다' 에는 여러가지 기준이 있으며 priority  가 integer일 때 기준으로 C++ 는 가장 큰 숫자가 (max-heap based), Java 의 경우 가장 작은 숫자(min-heap based) 가 priority 가 가장 높음 ( C++은 내림차순)

- 같은 연산을 기준으로 할 때 priority queue 는 map 보다 훨 씬 빠르다.

 

-size(), empty() 등의 함수 제공

 

-priority queue 를 min-heap based 로 바꾸고 싶을 경우(오름차순) 

1. priority 가 number 인 경우에 한해 각 priority 에 -1을 곱해서 insert 하거나

(꺼낸 다음에 다시 -1 곱해야함을 주의할 것)

2. 아래와 같이 greater를 사용

priority_queue<int, vector<int> , greater<int>> q;

 

- Priority queue 뿐만 아니라 C++ 의 partial_sort  또한 binary heap  으로 구현되어 있다. 

 

priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout << q.top() << endl;
q.pop();
cout << q.top() << endl;
q.pop();
q.push(6);
cout << q.top() << endl;
q.pop();

ex) Uva 1203 Argus

가장 먼저 출력되는 K의 task (Q_num) 을 순서대로 출력하는 것

Priority queue 를 사용하여 가장 period 가 작은 task i를 delete 한 뒤 해당 Q_num 을 출력하고 Q_num + 다음 시간을 다시 priority queue 에 insert 해준다.

예제코드 O(Nlog K) 

 

Union find data Structure

Union find 는 disjoint set들을 관리하기 위하 data structure 로서 , 다음과 같이 3개의 operation 을 지원한다.

 

1. makeset(x) : 단일 element x로 이루어진 set을 하나 생성한다.

2. find(x) : x가 포함된 set을 return 한다.

3. union (x,y) : x가 포함된 set과 y과 포함된 set을 하나의 set으로 합친다.

 

- 위 연산을 C++  set의 vector 로 구현할 수도 있지만 비효율적이다

- Union-find 는 각 set을 rooted tree로 관리하고, 각 tree의 root 를 대표 element 로 지정한다. 각 대표 element 는 rank 를 가지고 있다.

- Rank 는 path compression 을 가정하지 않을 시 해당 tree 의 height 로 정의한다.

- union 시 merged tree의 rank 가 작아지는 쪽으로 union 을 수행한다.