Tutorial: STL Set 4 timer 1초 memory 256MB

(반복자 관련 설명을 제외한다면) 지난 시간 까지 배운 것은 크게 3가지이다. 

Set에 원소를 삽입, 삭제하는 방법과 Set에서 원소를 검색하는 방법까지를 배웠다.

사실 자료를 삽입하고, 자료 존재 유무만 검색해야 한다면, 

Set 자료구조보다는 Hash Table을 쓰는 것이 훠~~~ㄹ씬 빠르고 효율적이다.

그럼에도 불구하고 Set을 굳이 배워서 쓰는 이유가 있다면 무엇일까? 

오늘은 Hash Table에는 없고, Set에만 있는 기능인 lower_bound와 upper_bound에 대해서 알아보도록 하자.

정렬된 배열에서의 lower_bound(x)와 upper_bound(x)의 정의는 다음과 같다.

lower_bound(x): x보다 크거나 같은 원소 중 가장 왼쪽 원소의 주소

upper_bound(x): x보다 큰 원소 중 가장 왼쪽 원소의 주소

사실 이 둘은 STL 함수로 이미 작성되어있으며, 상당수가 “이진 탐색 함수”로만 알고 있고, 정확한 뜻은 잘 모르고 있다. 

왜 굳이 이름을 lower bound와 upper bound로 지었나 궁금하다면, 아래 그림을 한번 슬며시 보도록 하자. 

순회를 lower_bound(3)부터 시작해서, upper_bound(3)이 나올 때까지 주소를 증가시키면서 이동하면, 

3이 존재하는 모든 주소를 순회할 수 있다. 

즉, 아래 한계값(lower bound)부터 위 한계값(upper bound)까지 순회하라~ 라는 의미를 담아 이름을 저렇게 지은 것이다.

자 이제 정의도 알았으니 set에서 사용법을 알아보자.

당연히 정의 자체는 다르지 않으며, 주소 대신 반복자를 반환한다는 점만 다르다.

아래 코드를 참고하자.

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
 
int main()
{
    set<int> st; ///set이름에 조금 변화를 줘 보았다.
    
    st.insert({1,4,10,14,16});
    
    set<int>::iterator lb = st.lower_bound(10); /// 반복자의 정식 선언
    auto ub = st.upper_bound(10);  ///auto가 자료형을 자동으로 set<int>::iterator로 추정해준다.
    
 
/* 1. 제일 직관적인 사용법 */
 
    printf("10이상의 원소중에 가장 작은 원소 : %d\n", *lb); ///lower_bound의 정의 그대로
    printf("10을 초과하는 원소중에 가장 작은 원소 : %d\n", *ub); ///upper_bound의 정의 그대로
    
 
/* 2. 응용법 */
 
   ///가장 작은 10을 초과하는 원소 바로 왼쪽엔 당연히, 가장 큰 10이하의 원소가 있다.
    printf("10이하의 원소중에 가장 큰 원소 : %d\n", *prev(ub));
   ///마찬가지 
    printf("10미만의 원소중에 가장 큰 원소 : %d\n", *prev(lb)); 
    
/*3. 주의사항 1 */
 
   ///20이상의 원소가 없으므로, set의 끝을 반환.
    lb = st.lower_bound(20);
    if(lb==st.end()) printf("20이상의 원소가 없습니다.\n");
///end()와 일치하는지 확인하지 않고 *lb를 사용하게 되면, 런타임 에러가 난다.
 
/*4. 주의사항 2 */
 
   ///-5이하의 원소가 없으므로, ub는 당연히 set의 시작을 가리킨다.
    ub = st.upper_bound(-5);
    if(ub == st.begin()) printf("-5이하의 원소가 없습니다.\n");
 
///begin()을 가리키는 경우, prev(ub)을 가리키게 하면 런타임 에러가 난다.
 
    return 0;
}
 

위 코드만 제대로 이해하면 거저 먹기인 연습문제를 풀어보고, 다음으로

넘어갈 수 있도록 하자.

[연습문제]

늘 하던 삽입, 삭제 작업에 더해서,

다음 2개의 작업을 추가해 4개의 작업을 하는

프로그램을 작성하라.

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

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

- b □ : □ 이상의 원소 중 제일 작은 값을 출력하라. 없다면 아무 것도 하지 않는다.​

- s □ : □ 이하의 원소 중 제일 큰 값을 출력하라. 없다면 아무 것도 하지 않는다.​

※ 인자한 쌤이 허락한다. 튜토리얼 1번문제의 코드를 수정하여도 좋다고.