연속 구간 합 구하기

---

연속 구간의 합을 구하는 문제가 출제가 되면 partial_sum을 사용해 효율적으로 구할 수 있다.

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4};
    vector<int> psum(4);

    partial_sum(v.begin(), v.end(), psum.begin());

    cout << psum[0] << endl; // 1
    cout << psum[1] << endl; // 3 (1 + 2)
    cout << psum[2] << endl; // 6 (1 + 2 + 3)
    cout << psum[3] << endl; // 10 (1 + 2 + 3 + 4)
    
    int sum = psum[3] - psum[1]; // 구간 [2, 4]의 합
}

유니크 값 구하기

---

unique는 연속된 중복 원소를 제거하여 (끝 위치) iterator를 반환하는 함수다.
unique는 정렬이 필수이다. 왜냐면, 방금 얘기했듯 연속된 중복 원소만 제거할 수 있기 때문이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 4, 4, 2, 2, 2, 5, 1};
    sort(v.begin(), v.end()); // 정렬 필수! {1, 1, 2, 2, 2, 4, 4, 5} 이렇게 되겠죠?

    auto newEnd = unique(v.begin(), v.end()); // 이건 아래에서 자세히 설명
    v.erase(newEnd, v.end()); // 중복되는 구간 전부 삭제!

    for (int x : v) cout << x << " ";
}

1. {1, 1, 2, 2, 2, 4, 4, 5}를 기반으로 unique 동작 시작
2. 첫 번째 1을 보고 유지
3. 두 번째 1은 중복, 그 자리에 다음 비중복 원소인 2를 복사 → {1, 2, 2, 2, 2, 4, 4, 5}
4. 첫 번째 2를 보고 유지
5. 두 번째, 세 번째 2는 중복이므로 중복 첫 시작되는 자리에 다음 비중복 원소인 4를 복사 → {1, 2, 4, 2, 2, 4, 4, 5}
6. 첫 번째 4를 보고 유지
7. 두 번째 4는 중복이므로 그 자리에 다음 비중복 원소인 5를 복사 → {1, 2, 4, 5, 2, 4, 4, 5}
8. 5를 보고 유지 → 최종 상태: {1, 2, 4, 5, , , , }
   a. 여기서 _는 유효하지 않은 값을 의미.

그래서 unique는 erase랑 같이 사용을 해줘야 중복 제거가 깔끔하게 완료됨.

빠른 이진 탐색

---

lower_bound / upper_bound는 정렬된 구간에서의 이진 탐색을 깔끔하게 제공해준다.

위 그림 기반으로 {1, 4, 6, 9, 15, 20, 30}에서 6을 찾는다고 가정을 해보자.

• 너 9보다 커? → 작어
• 너 4보다 커? → 커
• 정답은 6!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 4, 4, 5, 7, 8};
    auto lb = lower_bound(v.begin(), v.end(), 4);
    auto ub = upper_bound(v.begin(), v.end(), 4);
    
    cout << (lb - v.begin()) << endl; // 2
    cout << (ub - v.begin()) << endl; // 4
}

lower_bound는 x 이상의 값이 처음 나오는 위치를 찾는 것. upper_bound는 x 초과의 값이 처음 나오는 위치를 찾는 것d이다 그래서, cout의 결과가 저런식으로 나온다.