[์•Œ๊ณ ๋ฆฌ์ฆ˜] lower_bound, upper_bound

lower_bound, upper_bound

lower_bound, upper_bound๋ฅผ int ํƒ€์ž…๊ณผ pair<>์—์„œ๋„ ์‚ฌ์šฉํ•ด๋ด…์‹œ๋‹ค.

algorithm ํ—ค๋”

lower_bound, upper_bound๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„  algorithm ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.

#include

์„ ์–ธ

lower_bound(์‹œ์ž‘ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ๋ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ์ง€์ • ๊ฐ’)

upper_bound(์‹œ์ž‘ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ๋ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ์ง€์ • ๊ฐ’)

๋ฆฌํ„ด ๊ฐ’

vector์—์„œ lower_bound, upper_bound๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ์˜ ๋ฆฌ ๊ฐ’์„ ์•Œ์•„๋ด…์‹œ๋‹ค.

lower_bound

lower_bound๋Š” vector์˜ ์‹œ์ž‘ ์ดํ„ฐ๋ ˆ์ดํ„ฐ์™€ ๋ ์ดํ„ฐ๋ ˆ์ดํ„ฐ ์‚ฌ์ด์—์„œ ์ง€์ •ํ•œ ๊ฐ’ ์ด์ƒ์„ ๊ฐ€์ง€๋Š” ์ตœ์ดˆ์˜ ์ดํ„ฐ๋ ˆ์ดํ„ฐ๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.

upper_bound

upper_bound๋Š” vector์˜ ์‹œ์ž‘ ์ดํ„ฐ๋ ˆ์ดํ„ฐ์™€ ๋ ์ดํ„ฐ๋ ˆ์ดํ„ฐ ์‚ฌ์ด์—์„œ ์ง€์ •ํ•œ ๊ฐ’๋ณด๋‹ค ๋” ํฐ ๊ฐ’์„ ๊ฐ€์ง€๋Š” ์ตœ์ดˆ์˜ ์ดํ„ฐ๋ ˆ์ดํ„ฐ๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.

์ธ๋ฑ์Šค ๋ฐ˜ํ™˜

vector๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ฒซ ์ดํ„ฐ๋ ˆ์ดํ„ฐ ๊ฐ’์„ ๋นผ์ฃผ๋ฉด ์ธ๋ฑ์Šค๊ฐ€ ๋ฐ˜ํ™˜๋ฉ๋‹ˆ๋‹ค.

lower_bound(v.begin(), v.end(), num) - v.begin();

upper_bound(v.begin(), v.end(), num) - v.begin();

์˜ˆ์ œ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    vector<int> adj= {2,4,6,1,7,8,3,1,5,7,9,3,2,1};
    sort(adj.begin(),adj.end());
    for(int i=0; i<adj.size();i++) cout << adj[i] << ' ';
    // 1 1 1 2 2 3 3 4 5 6 7 7 8 9
    cout << '\n';
    int lowBoundIndex = lower_bound(adj.begin(),adj.end(), 4) - adj.begin();
    int upperBoundIndex = upper_bound(adj.begin(),adj.end(),4) - adj.begin();
    cout << lowBoundIndex << ' ' << upperBoundIndex << '\n';
    // 7, 8
    return 0;
}

pair<int,int>๋ฅผ ์ ์šฉํ•œ ์˜ˆ์ œ

๋น„๊ต์˜ ๊ธฐ์ค€์ด ๋  bool์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค๊ณ  ๊ทธ ํ•จ์ˆ˜๋ฅผ ๋„ค ๋ฒˆ์งธ ์ธ์ž๋กœ ์ถ”๊ฐ€ํ•˜๊ณ , ์„ธ ๋ฒˆ์งธ ์ธ์ž์—๋Š” make_pair()๋กœ ์ง€์ • ๊ฐ’์„ pair๋กœ ์„ ์–ธํ•ด ์ค๋‹ˆ๋‹ค.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(const pair<int, int> &a, const pair<int,int> &b) {
    return a.first < b.first;
}
int main(){
    vector<pair<int,int>> adj= { {1,3},{2,5},{2,9},{9,20},{10,25},{5,2},{7,2},{8,9} };
    sort(adj.begin(),adj.end());
    for(int i=0; i<adj.size();i++) cout << adj[i].first << ' ' << adj[i].second << " | ";
    // 1 3 | 2 5 | 2 9 | 5 2 | 7 2 | 8 9 | 9 20 | 10 25 | 
    cout << '\n';
    int lowBoundIndex = lower_bound(adj.begin(),adj.end(), make_pair(5,0),comp) - adj.begin();
    int upperBoundIndex = upper_bound(adj.begin(),adj.end(),make_pair(5,0),comp) - adj.begin();
    cout << lowBoundIndex << ' ' << upperBoundIndex << '\n';
    // 3, 4
    return 0;
}