💡 퀵 접속: cpp.kr/partial_sum

partial_sum

C++ 표준 라이브러리의 알고리즘으로, 범위의 각 위치까지의 부분 합을 계산합니다. 각 위치의 결과는 해당 위치까지의 모든 요소의 합이 됩니다.

기본 사용법

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(5);
    
    // 부분 합 계산
    std::partial_sum(v.begin(), v.end(), result.begin());
    
    // 결과 출력
    std::cout << "원본 벡터: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    std::cout << "부분 합: ";
    for (int x : result) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

실행 결과:

원본 벡터: 1 2 3 4 5
부분 합: 1 3 6 10 15

커스텀 연산 사용

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(5);
    
    // 곱셈을 사용한 부분 합 계산
    std::partial_sum(v.begin(), v.end(), result.begin(),
                    std::multiplies<int>());
    
    // 결과 출력
    std::cout << "원본 벡터: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    std::cout << "부분 곱: ";
    for (int x : result) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

실행 결과:

원본 벡터: 1 2 3 4 5
부분 곱: 1 2 6 24 120

사용자 정의 타입에서 사용

#include <iostream>
#include <vector>
#include <numeric>
#include <string>

struct Point {
    int x, y;
    
    Point operator+(const Point& other) const {
        return {x + other.x, y + other.y};
    }
};

int main() {
    std::vector<Point> points = {
        {1, 2}, {3, 4}, {5, 6}, {7, 8}
    };
    std::vector<Point> result(4);
    
    // 점들의 부분 합 계산
    std::partial_sum(points.begin(), points.end(), result.begin());
    
    // 결과 출력
    std::cout << "원본 점들:" << std::endl;
    for (const auto& p : points) {
        std::cout << "(" << p.x << ", " << p.y << ") ";
    }
    std::cout << std::endl;
    
    std::cout << "부분 합:" << std::endl;
    for (const auto& p : result) {
        std::cout << "(" << p.x << ", " << p.y << ") ";
    }
    std::cout << std::endl;
    
    return 0;
}

실행 결과:

원본 점들:
(1, 2) (3, 4) (5, 6) (7, 8)
부분 합:
(1, 2) (4, 6) (9, 12) (16, 20)

참고사항

partial_sum은 numeric 헤더에 정의되어 있습니다.
기본적으로 + 연산자를 사용하여 부분 합을 계산합니다.
커스텀 연산을 제공할 수 있습니다.
시간 복잡도는 O(n)입니다 (n은 범위의 크기).
결과를 저장할 범위는 충분한 크기여야 합니다.
원본 범위는 수정하지 않습니다.

함수	설명
partial_sum(first, last, result)	기본 + 연산자를 사용하여 부분 합 계산
partial_sum(first, last, result, op)	커스텀 연산을 사용하여 부분 합 계산