[인프런] 4) 10주차 c++ 알고리즘

unique()

: 유니크는 범위 안에 중복요소를 제거해줌 , O(n) 시간복잡도

이때 auto it = unique(v.begin(), v.end()) 의 it은 중복이없는걸 채워지고 나머지는 그대로 채워주는 특성을 가지고 이고 중복이후의 iterator를 반환.

또 특성으로는 앞에서 부터 순차적으로 중복을 제거하기에 sort와 같이 사용해야함. 

 

중복제거가 끝난후에 나머지값을 제거할때는 erase(제거시작 이터 , 제거 종료 이터)를 사용한다. 아래 처럼 하면 깔끔하게 뒤가 제거됨!

lower_bound() 와 upper_bound()

이분탐색이라고 말하고 정렬된 배열 에서 특정 지점의 첫번째 지점 혹은 초과지점의 어떤값을 찾기위해서 lower_bound() 혹은 upper_bound() 함수를 사용할 수 있다. 

이 피규어에서 3으로 배열된 벡터에서 3이전에 위치하는 인덱스나 수를 알기위해서는 아래처럼사용할 수 있고 이또한 lower_bound는 iterator로 3을가리키지만 -a.begin()을 통해 2로 감소되며 이는 int 2를 가리키게된다 upper_bound또한 동일한 로직으로 사용될수 있다. 

cout << lower_bound(a.begin(), a.end(), 3) - a.begin() << "\n"; // 2
cout << upper_bound(a.begin(), a.end(), 3) - a.begin() << "\n"; // 5

accumulate()

배열안에 있는 총 합을 구함

int sum = accumulate(v.begin(), v.end(), 0);

max_element()

벡터에서 최대값을 알고싶거나 최대값을 지칭하는 인덱스를 알고싶을때 서술.

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int a = *max_element(v.begin(), v.end());
auto b = max_element(v.begin(), v.end());
cout << a << '\n'; // 10// *max_element로 해주면 값을 반환해줌
cout << (int)(b - v.begin()) << '\n';  // b 는 인덱스이고 보통 이터레이터 반환은 다음것을 반환하는데
이때 -1을 begin으로 해줌으로써 9번쨰가 나옴