C++ STL 자료구조 std::set

C++에는 참 다양한 자료구조가 STL로 구현되어있다. 대표적으로 vector, queue, stack 등이 있으며 단순 선형 자료구조 이외에도 map이나 Linked List 등도 있다. 그중에서도 최근에 굉장히 유용함을 알게 된 자료구조가 있어서 이렇게 글을 남겨본다.

 

본래 프로그래밍 언어로 C++을 처음 접했으나 모종의 이유로 파이썬으로 대부분의 규모가 큰 코드들을 많이 작성했었는데, 그래서 어떤 기능을 가지는 프로그램을 만들고 싶을 때 파이썬으로 구현하는 일이 많았고 파이썬의 라이브러리를 빠삭하게 알게 되었다. 파이썬의 set, list, deque, dictionary 등을 매우 자주 쓰고 익숙해지다보니 정작 문제를 풀 때 사용하기에는 적합하지 않았다. 딕셔너리도 풀라고 만든 문제는 대부분 실버에서 포켓몬도감 같은 문자열로 뭔갈 진행해야하는 상황밖에 없었기 때문이다. 그러하여 모두가 웰논이라고 하는 문제들을, 모두가 간단히 자료구조를 써서 푸는 문제를 이해하지 못하는 상황이 잦았다.

 

심지어 학교에서 자료구조 수업을 진즉에 수강 완료한 상태였다. 하지만 학교수업조차 파이썬으로 진행되어 라이브러리에서 사용되는 자료구조는 고사하고 큐나 스택 구현도 리스트로 대충 때우고 넘어간지라 뭔지만 알지 실제로는 잘 쓰지 못했다. 다행이도 큐, 스택, 우선순위 큐와 같은 간단한 자료구조들은 파이썬에도 deque, heap등이 있어서 사용할 순 있었지만 한계가 명확하였다.

 

그래서 좀더 넓은 시야를 가지기 위해 C++ STL을 탐방하고, 내가 heap으로 떼워서 푼 문제들을 다른 사람들은 어떻게 풀었는지도 살펴보며, 그리고 내가 풀어보지 않았던 태그들의 문제들을 보며 다른 자료구조들을 문제에서 어떻게 활용해야하는지 찾아보았다. 그러다 C++에서 Set 자료구조를 알게 되었다.

 

---

 

C++에서 셋은 아래와 같은 코드로 사용할 수 있다.

#include<set>
using std::set;
set<int> s;

다른 STL과 마찬가지로 $<>$ 사이에 타입을 정해주어 사용하고, 비교 연산이 잘 정의된 구조체나 클래스도 사용할 수 있다. 파이썬에서 set은 단순히 중복이 없고, 내부 요소들의 순서가 무작위적이고, 삽입과 제거 연산이 빠른 자료구조 정도로만 알고있었다. 하지만 C++에서 set은 오히려 heap과 비슷하다. Binary Search Tree로 구현되어있으며 구성요소들이 중복 없이 정렬된 상태로 유지된다. $\mathcal O (log N)$으로 삽입과 제거 연산을 수행할 수 있다. 여기서 $N$은 set의 크기이다. Binary Search Tree로 구현된 만큼 삽입할 때는 Tree의 Root부터 내려가며 비교하여 위치를 찾아가고, 만약 동일한 노드에 도착하면 삽입 연산을 수행하지 않는다. 그러하여 어쩌면 우선순위 큐와 사용처가 비슷해보이지만, set은 내부 요소를 순회할 수 있고 어떤 요소가 있는지, 없다면 어디에 위치할지 lower_bound와 upper_bound로 이분 탐색을 수행할 수 있다. 아래는 여러가지 방법으로 셋을 사용하는 예시이다. 

set<int> s;
vector<int> v = { 1, 2, 5 };
s.insert(v.begin(), v.end());
auto result = s.insert(1);
cout << result.second << '\n'; // false
int a = 3, b = 1;
auto ub = s.upper_bound(a);
auto lb = s.lower_bound(b);
cout << *ub << '\n'; // 5
cout << (lb == s.begin()) << '\n'; // true

insert 함수는 pair<it, bool>을 리턴하며 삽입이 성공하면(set에 원소가 없었다면) 그 위치에 해당하는 이터레이터와 true, 실패하면 begin과 false를 반환한다.(잘 안쓴다)

 

bound 함수의 반환값의 타입 auto는 set<int>::iterator로, vector에서처럼 set을 이터레이터로 순회할 수 있다. 물론 구현체가 다르기에 인덱스는 사용할 수 없다. 만약에 find 함수를 사용했을 때나 bound 함수를 사용했을 때 bound의 값이 set 내부에 없다면 s.end()(혹은 lower_bound의 경우 s.begin())를 반환한다. 순회할 때도 begin부터 시작한다면 이터레이터가 end와 같은지 비교하여 종료조건을 설정할 수 있다. 주의할 점은 begin은 역참조가 되지만 end는 런타임 에러를 뿜는다. 반복문에 이터레이터를 적절히 쓰는지 잘 확인해주자.

vector<int> v;
set<int> s;
auto it = s.begin();
while (it != s.end()) {
    v.push_back((*it));
    it = next(it);
}

즉 set은 내부 요소를 항상 정렬시켜놓는 컨테이너처럼 사용할 수 있다. 물론 이름의 본연답게 중복을 제거하는 용도로도 사용할 수 있겠지만, 정렬된 컨테이너를 활용하여 사용할 방안이 다양하다.

 

---

 

번외로 set의 삽입, 제거, 탐색 연산 속도를 $\mathcal O(1)$으로 수행하는 unordered_set 자료구조도 있다.

#include<unordered_set>
using namespace std;
unordered_set<int> us;

이는 BST가 아닌 해시로 구현되어있으며 파이썬의 set과 동일한 기능을 가지고 있다. 물론 순회가 안되고 정렬된 기능도 사용할 수 없어 데이터의 크기가 매우 큰데 중복을 꾸준히 확인해야 할 경우에 사용한다.

 

그리고 중복을 제거하지 않고 정렬되는 기능만 사용하는 multiset 자료구조 또한 <set> 헤더에 존재한다.

 

?

 

그렇다. set을 딱히 중복 제거 용도로 사용하지 않고 싶다는 말이다. 정렬 상태를 유지해주는 것만으로 충분하다는 것이다. multiset은 BBST로 구현되어 있으며, 이로인해 파이썬에서는 Splay Tree 등을 구현해야만 사용할 수 있는 BBST를 간단히 STL로 만나볼 수 있다.

 

---

 

 

noj.am/23057

23057번: 도전 숫자왕

이문제는 set을 중복 제거용으로 쓰면 좋다. unordered_set을 사용해도된다. 다만 multiset은 안된다.

 

 

noj.am/11917

11917번: 이상한 수열

이문제는 set의 성질을 아주 잘 활용하는 문제이다. 구현이 복잡하지 않고 조금 생각하여 어떤식으로 set을 굴려야 할지 생각해보면 set의 삽입, 중복 제거, 탐색하는 성질을 모두 활용하여 풀 수 있다. M의 범위가 1부터인것을 유의하자.

 

 

noj.am/6142

6142번: Gourmet Grazers

이 문제는 우선순위 큐로 구현하면 매우 복잡할 것 같은 문제이다. 간략하게 설명하자면 개별 요소를 잘 정렬해서 페어를 쓰든 구조체를 쓰든 해서 적절하게 멀티셋으로 굴리면 된다. 어떤 요소가 더 중요한지 잘 판단하고 요소간 중요도를 나누어야한다.