merge, lower_bound, upper_bound C++

개요

 

C++ 표준 라이브러리에서 merge, lower_bound, upper_bound는 모두 정렬된 시퀀스를 처리하는 데 사용되는 알고리즘이다. algorithm을 include 해야 사용할 수 있다.

 

1. merge 알고리즘

merge는 두 개의 정렬된 시퀀스를 병합하여 하나의 정렬된 시퀀스를 생성하는 알고리즘, 두 입력 시퀀스는 정렬되어 있어야 하며, 병합된 결과도 정렬된 상태로 유지된다.

사용법

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2,
                OutputIt d_first );

매개변수

• first1, last1: 첫 번째 정렬된 시퀀스의 범위.
• first2, last2: 두 번째 정렬된 시퀀스의 범위.
• d_first: 병합된 결과를 저장할 위치의 시작.

반환값

병합된 결과의 마지막 위치 다음의 반복자(OutputIt).

 

2. lower_bound 알고리즘

lower_bound는 정렬된 시퀀스에서 특정 값보다 크거나 같은 첫 번째 요소를 찾는 데 사용되는 알고리즘, 이진 검색(binary search)을 사용하여 효율적으로 검색

사용법

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );​

매개변수

• first, last: 검색할 범위.
• value: 찾고자 하는 값.

반환값

찾고자 하는 값보다 크거나 같은 첫 번째 요소의 위치를 가리키는 반복자(ForwardIt). 만약 그런 요소가 없다면 last를 반환

 

3. upper_bound 알고리즘

upper_bound는 정렬된 시퀀스에서 특정 값보다 큰 첫 번째 요소를 찾는 데 사용되는 알고리즘,마찬가지로 이진 검색(binary search)을 사용

사용법

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

매개변수

• first, last: 검색할 범위.
• value: 찾고자 하는 값.

반환값

찾고자 하는 값보다 큰 첫 번째 요소의 위치를 가리키는 반복자(ForwardIt). 만약 그런 요소가 없다면 last를 반환

 

예제

1. merge 알고리즘

 

코드

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 3, 5, 7};
    std::vector<int> v2 = {2, 4, 6, 8};
    std::vector<int> v3(8);

    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

    for(int n : v3) {
        std::cout << n << ' ';
    }
    return 0;
}

 

출력

1 2 3 4 5 6 7 8

 

이 코드는 두 개의 정렬된 벡터 v1, v2를 병합하여 벡터 v3에 저장하고, 병합된 결과를 출력한다.

 

2. lower_bound 알고리즘

코드

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 3, 5, 7, 9 };

    auto it = std::lower_bound(v.begin(), v.end(), 6);

    if (it != v.end()) {
        std::cout << "배열 내 6보다 크거나 같은 첫번째 수는 " << *it << "입니다.\n";
    }
    else {
        std::cout << "6이 배열 내 가장 큰 값입니다.\n";
    }
    return 0;
}

 

출력

배열 내 6보다 크거나 같은 첫번째 수는 7입니다.

 

 

이 코드는 벡터에서 6보다 크거나 같은 첫 번째 요소를 찾고, 해당 값을 출력한다.

 

3. upper_bound 알고리즘

코드

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9};

    auto it = std::upper_bound(v.begin(), v.end(), 6);

    if (it != v.end()) {
        std::cout << "배열 내 6보다 큰 첫번째 수는 " << *it << "입니다.\n";
    } else {
        std::cout << "6이 배열 내 가장 큰 값입니다.\n";
    }
    return 0;
}

 

출력

배열 내 6보다 큰 첫번째 수는 7입니다.

 

실습

 

1. 배열 내 특정 수보다 큰 숫자의 개수 찾기

n개의 수를 가진 배열을 만들고, m개의 질의를 통해 입력한 수보다 큰 숫자의 개수를 출력하기

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<int> lst;

int query(int val) {
	return lst.end() - upper_bound(lst.begin(), lst.end(), val);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	lst.resize(n);
	for (int i = 0; i < n; i++) cin >> lst[i];
	sort(lst.begin(), lst.end());
	cin >> m;
	while (m--) {
		int c; cin >> c;
		cout << "배열 내 " << c << "보다 큰 숫자의 개수 : " << query(c) << "개\n";
	}
}

 

입력

15
1214 1231 151 1513 2145 12315 321 2145 2154 21354 1 2 3 4 5
5
252
3
2146
21578
215

 

출력

배열 내 252보다 큰 숫자의 개수 : 9개
배열 내 3보다 큰 숫자의 개수 : 12개
배열 내 2146보다 큰 숫자의 개수 : 3개
배열 내 21578보다 큰 숫자의 개수 : 0개
배열 내 215보다 큰 숫자의 개수 : 9개