Tutorial: STL Set 1 timer 1초 memory 512MB

Set은 말 그대로 집합이다.

자료의 삽입, 삭제, 검색 등을 O(log n)만에 처리해주는 자료구조이다.

Heap을 처음 배울 때는 내부 구조를 직접 구현해보는 과정을 거쳤던 기억이 있을 것이다. 

그러나 Set의 경우는 내부 구조가 너무 어려우므로, 사용방법을 익히는 것만으로도 충분하다.

(Set의 내부 구조를 지금 당장 이해하기는 너무 어려우나, 자신이 “궁금증을 해결하지 못하면 불면증에 걸리는 스타일”이라면, 추후에 Red and Black Tree라는 것을 검색해보길 바란다.)

오늘은 맛보기만

우선 Set의 기본적인 사용방법은 다음과 같다. 우선 원소의 삽입, 삭제와 전체 원소를 출력하는 작업만 연습해 보자.

#include <stdio.h>
#include <algorithm>

#include <set> //set을 사용하려면 이 헤더파일이 필요하다.

using namespace std;

int main()
{
    set<int> s;  /// int형 자료를 넣을 수 있는 집합 s를 하나 만든다.
    s.insert(3);  /// 집합 s에 3을 넣는다.
    s.insert(5);
    s.insert(3);  /// 3이 이미 있으므로, 이 삽입작업은 아무 효과가 없다.
    s.insert(6);
    s.insert(9);
    s.insert(2);

    s.erase(3); ///집합에서 3을 삭제.
    s.erase(10); ///집합에 10이 없으므로 이 삭제작업은 무효하다.

    for(int element: s){
        printf("%d " , element);
    }
    return 0;
}

마지막 부근의 for문은 “s의 모든 원소 element에 대해 순회하라” 라는 뜻인데, for문의 또 다른 용법 중에 하나이다. 배열이나 vector 등에서도 쓸 수 있으므로, 아직 모르고 있었다면 익혀두는 것이 좋다.

출력결과는 아래와 같다.

2 5 6 9

자세히 보면, 원소 삽입 순서에 상관없이 크기의 오름차순으로 순회한다는 것을 알 수 있다 (5와 6을 먼저 insert했지만, 2가 먼저 출력된다). 이처럼 set은 집합 내의 원소를 항상 정렬된 순서로 유지해준다는 특징이 있는데, 이것이 set의 막강한 장점이며, set 자료구조를 선택하는 주된 이유가 된다.

이제 아래 연습문제를 풀고, 다음으로 넘어가보자.

연습문제

정수형 자료를 저장할 수 있는 집합(set)을 선언한 후, 다음 2가지 작업을 순서대로 처리한 후에 남아있는 자료를 오름차순으로 출력하는 프로그램을 작성하라

• i □ : □가 없다면 집합에 추가한다.

• r □ : 집합 내에 □가 있다면 삭제한다. 없다면 아무 것도 하지 않는다. 

반드시 지금 배운 set을 사용한다.​