0. 정렬된 범위 알고리즘
- 정렬된 구간에서만 동작하는 알고리즘
- 원소가 같음 비교시 a==b 연산 사용 안함
- 원소가 같은 비교시 !(a<b) && !(b<a) 사용
1. 정렬 알고리즘 리스트
| 알고리즘 |
설명 |
| binary_search(b,e,x) |
구간 [b,e)의 순차열에 x와 같은 원소가 있는가? |
| binary_search(b,e,x,f) |
구간 [b,e)의 순차열에 x와 같은 원소가 있는가? f를 비교에 사용 |
| includes(b,e,b2,e2) |
구간 [b2,e2)의 모든 원소가 구간 [b,e)에도 있는가? |
| includes(b,e,b2,e2,f) |
구간 [b2,e2)의 모든 원소가 구간 [b,e)에도 있는가? f를 비교에 사용 |
| p=lower_bound(b,e,x) |
p는 구간 [b,e) 순차열에서 x와 같은 첫 원소의 반복자 |
| p=lower_bound(b,e,x,f) |
p는 구간 [b,e) 순차열에서 x와 같은 첫 원소의 반복자. f는 비교에 사용 |
| p=upper_bound(b,e,x) |
p는 구간 [b,e) 순차열에서 x 보다 큰 첫 원소의 반복자 |
| p=upper_bound(b,e,x,f) |
p는 구간 [b,e) 순차열에서 x 보다 큰 첫 원소의 반복자. f를 비교에 사용 |
| pair(p1,p2)=equal_range(b,e,x) |
구간 [p1,p2)의 순차열은 구간 [b,e)의 순차열에서 x와 같은 원소의 구간. [lower_bound(), upper_bound())의 순차열과 같음 |
| pair(p1,p2)=equal_range(b,e,x,f) |
equal_range(b,e,x)와 동일. f를 비교에 사용 |
| p=merge(b,e,b2,e2,t) |
구간[b,e)의 순차열과 구간 [b2,e2)의 순차열을 합병해 [t,p)에 저장 |
| p=merge(b,e,b2,e2,t,f) |
merge(b,e,b2,e2,t)과 동일. f를 비교에 사용 |
| inplace_merge(b,m,e) |
정렬된 [b,m) 순차열과 [m,e) 순차열을 [b,e)순차열로 합병 |
| inplace_merge(b,m,e,f) |
inplace_merge(b,m,e,f)와 동일. f를 비교에 사용 |
| p=set_union(b,e,b2,e2,t) |
구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 합집합으로 [t,p)에 저장 |
| p=set_union(b,e,b2,e2,t,f) |
set_union(b,e,b2,e2,t)와 동일. f를 비교에 사용 |
| p=set_intersection(b,e,b2,e2,t) |
구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 교집합으로 [t,p)에 저장 |
| p=set_intersection(b,e,b2,e2,t,f) |
set_intersection(b,e,b2,e2,t)과 동일. f를 비교에 사용 |
| p=set_difference(b,e,b2,e2,t) |
구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 차집합 [t,p)에 저장 |
| p=set_difference(b,e,b2,e2,t,f) |
set_difference(b,e,b2,e2,t)과 동일. f를 비교에 사용 |
| p=set _symmetric_difference(b,e,b2,e2,t) |
구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 대칭 차집합으로 [t,p)에 저장 |
| p=set _symmetric_difference(b,e,b2,e2,t,f) |
set _symmetric_difference(b,e,b2,e2,t)와 동일. f를 비교에 사용 |
2. 상세 예시
-
binary_search(b,e,x)
- 구간 [b,e)에서 x와 같은 원소가 있음 true
vector<int> v = {10,20,30,40,50};
bool b = binary_search(v.begin(), v.end(), 20);
// b = true
- binary_search(b,e,x,f)
bool Pred(int left, int right){
return 3 < right - left;
} // 오른쪽이 왼쪽보다 3보다 크면 참
vector<int> v = {40,46,12,80,10,47,30,55,90,53};
sort(v.begin(), v.end(), Pred);
// 조건자에 의한 정렬
// v = {12,10,30,40,46,47,55,53,80,90}
// 12와 10의 차이가 3보다 작기 때문에 12가 앞
// 55와 53의 차이가 3보다 작기 때문에 55가 앞
bool b = binary_search(v.begin(), v.end(), 32, Pred);
// b = true
// !Pred(30,32) => true 이고,
// !Pred(32,30) => true 이므로,
// 참조건 (!Pred(30,32)&&!Pred(32,30)) = true
- includes(b,e,b2,e2)
- [b,e) 에 [b2,e2)가 포함되면 true
vector<int> v = {10,20,30,40,50};
vector<int> v2 = {10,20,40};
vector<int> v3 = {10,20,60};
bool b1 = includes(v1.begin(), v1.end()
,v2.begin(), v2.end());
// b1 = true
// v2는 v에 포함되므로
bool b2 = includes(v1.begin(), v1.end(), v2.begin(), v2.end());
// b2 = false
// v3의 60은 v에 포함되지 않으므로
//조건자 사용
sort(v1.begin(), v1.end(), greater<int>());
sort(v2.begin(), v2.end(), greater<int>());
b1 = includes(v1.begin(), v1.end()
, v2.begin(), v2.end()
, greater<int>())
- lower _bound, upper _bound, equal_range
- 찾는 원소가 여러 개 일 때 반복자 반환
- lower_bound : 첫 원소의 반복자 반환
- upper_bound : 마지막 다음 원소 반복자 반환
- equal_range : [lower_bound, upper_bound) pair 반환
vector<int> v = {10,20,30,30,30,40,50};
auto lower = lower_bound(v.begin(), v.end(), 30);
auto upper = upper_bound(v.begin(), v.end(), 30);
auto eual = equal_range(v.begin(), v.end(), 30);
// lower = 첫 30을 가리킴
// upper = 마지막 30의 다음 40을 가리킴
// eqaul = (lower,upper)의 pair 형태
- merge(b,e,b2,e2,t)
vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {20,30,60};
vector<int> v3(10);
auto iter = merge(v1.begin(), v1.end()
,v2.begin(), v2.end()
,v3.begin());
// v3 = {10,20,20,30,30,40,50,60,0,0};
// iter -1 => 60을 가리킴
- inplace_merge(b,m,e)
- 하나의 순차열이 두 구간으로 정렬되어 있을 때
- 하나의 구간으로 정렬 가능
vector<int> v = {10,20,30,40,50,20,30,60};
// v => 10,20,30,40,50 과
// 20,30,60 의 두 개의 구간으로 정렬되어 있음
inplace_merge(v.begin(), v.begin()+5, v.end());
// v = {10,20,20,30,30,40,50,60} 으로 정렬됨
3. 집합 관련 알고리즘
- set_union(b,e,b2,e2,t)
- set_intersection(b,e,b2,e2,t)
- set_difference(b,e,b2,e2,t)
- set_ symmetric_difference(b,e,b2,e2,t)
vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {20,30,60};
vector<int> v3(10);
// 1. 합집합
auto iter = set_union(
v1.begin(), v1.end()
,v2.begin(), v2.end()
,v3.begin());
// v3 = {10,20,30,40,50,60,0,0,0,0}
// iter - 1 => 60을 가리킴
// 2. 교집합
auto iter = set_intersection(
v1.begin(), v1.end()
,v2.begin(), v2.end()
,v3.begin());
// v3 = {20,30,0,0,0,0,0,0,0,0}
// iter - 1 => 30을 가리킴
// 3.차집합
auto iter = set_difference(
v1.begin(), v1.end()
,v2.begin(), v2.end()
,v3.begin());
// v3 = {10,40,50,0,0,0,0,0,0,0}
// iter - 1 => 50을 가리킴
// 4. 대칭 차집합
auto iter = set_symmetric_difference(
v1.begin(), v1.end()
,v2.begin(), v2.end()
,v3.begin());
// v3 = {10,40,50,60,0,0,0,0,0,0}
// iter - 1 => 60을 가리킴
참고
- 뇌를 자극하는 C++ STL
