C++ Algorithm Numeric | accumulate·reduce

들어가며

C++ <numeric> 헤더는 수치 연산에 특화된 알고리즘을 제공합니다. 합계, 곱셈, 내적, 누적 합 등 수학적 연산을 표준 라이브러리로 간결하게 표현할 수 있으며, C++17부터는 병렬 실행 정책을 지원해 대용량 데이터 처리 성능을 크게 향상시킬 수 있습니다.

이 글을 읽으면

• accumulate, reduce, transform_reduce의 차이를 이해합니다
• partial_sum, inclusive_scan, exclusive_scan으로 누적 연산을 구현합니다
• 병렬 실행 정책으로 성능을 최적화합니다
• 실무에서 자주 사용하는 패턴을 익힙니다

---

기본 알고리즘

주요 알고리즘 목록

알고리즘	용도	C++ 버전
accumulate	범위 집계 (순차)	C++98
reduce	범위 집계 (병렬 가능)	C++17
transform_reduce	변환 후 집계	C++17
inner_product	내적	C++98
partial_sum	누적 합	C++98
inclusive_scan	누적 합 (병렬)	C++17
exclusive_scan	누적 합 (현재 제외)	C++17
adjacent_difference	인접 차이	C++98
iota	순차 값 생성	C++11

---

실전 구현

1) accumulate - 범위 집계

시그니처:

template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init);
template<class InputIt, class T, class BinaryOp>
T accumulate(InputIt first, InputIt last, T init, BinaryOp op);

기본 사용

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 합계
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "합: " << sum << std::endl;  // 15
    
    // 곱
    int product = std::accumulate(v.begin(), v.end(), 1, 
        [](int a, int b) { return a * b; });
    std::cout << "곱: " << product << std::endl;  // 120
    
    return 0;
}

커스텀 연산

#include <numeric>
#include <vector>
#include <string>
int main() {
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    
    // 문자열 연결
    std::string sentence = std::accumulate(
        words.begin(), 
        words.end(), 
        std::string(""),
        [](const std::string& a, const std::string& b) {
            return a + b;
        }
    );
    
    std::cout << sentence << std::endl;  // Hello World!
    
    return 0;
}

시간 복잡도: O(n)
공간 복잡도: O(1)

2) reduce - 병렬 집계 (C++17)

시그니처:

template<class ExecutionPolicy, class ForwardIt, class T>
T reduce(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init);

기본 사용

#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
int main() {
    std::vector<int> v(1000000, 1);
    
    // 순차 실행
    auto sum1 = std::reduce(v.begin(), v.end(), 0);
    
    // 병렬 실행
    auto sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0);
    
    // 병렬 + 벡터화
    auto sum3 = std::reduce(std::execution::par_unseq, v.begin(), v.end(), 0);
    
    std::cout << "합: " << sum2 << std::endl;  // 1000000
    
    return 0;
}

accumulate vs reduce

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<double> v = {1.0, 2.0, 3.0, 4.0, 5.0};
    
    // accumulate: 순서 보장 (왼쪽부터)
    double sum1 = std::accumulate(v.begin(), v.end(), 0.0);
    
    // reduce: 순서 보장 안 됨 (병렬 가능)
    double sum2 = std::reduce(v.begin(), v.end(), 0.0);
    
    // 부동소수점은 순서에 따라 결과 미세하게 다를 수 있음
    std::cout << "accumulate: " << sum1 << std::endl;
    std::cout << "reduce: " << sum2 << std::endl;
    
    return 0;
}

주의사항

• reduce는 결합법칙을 가정
• 부동소수점은 순서에 따라 결과 다를 수 있음
• 병렬 실행 시 데이터 경합 주의

---

3) transform_reduce - 변환 후 집계 (C++17)

시그니처:

template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T>
T transform_reduce(ExecutionPolicy&& policy, 
                   ForwardIt1 first1, ForwardIt1 last1,
                   ForwardIt2 first2, T init);

내적 (Dot Product)

#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {2, 2, 2, 2, 2};
    
    // 내적: v1[i] * v2[i]의 합
    int dotProduct = std::transform_reduce(
        std::execution::par,
        v1.begin(), v1.end(),
        v2.begin(),
    );
    
    std::cout << "내적: " << dotProduct << std::endl;  // 30
    
    return 0;
}

제곱합

#include <numeric>
#include <vector>
#include <execution>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 제곱합: sum(v[i]^2)
    int sumOfSquares = std::transform_reduce(
        std::execution::par,
        v.begin(), v.end(),
        0,
        std::plus<>(),
        [](int x) { return x * x; }
    );
    
    std::cout << "제곱합: " << sumOfSquares << std::endl;  // 55
    
    return 0;
}

시간 복잡도: O(n)
공간 복잡도: O(1)

4) inner_product - 내적

시그니처:

template<class InputIt1, class InputIt2, class T>
T inner_product(InputIt1 first1, InputIt1 last1,
                InputIt2 first2, T init);

기본 사용

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    
    // 내적: 1*4 + 2*5 + 3*6 = 32
    int result = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
    
    std::cout << "내적: " << result << std::endl;  // 32
    
    return 0;
}

커스텀 연산

#include <numeric>
#include <vector>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    
    // 합(곱) 대신 곱(합) 사용
    // (1+4) * (2+5) * (3+6) = 5 * 7 * 9 = 315
    int result = std::inner_product(
        v1.begin(), v1.end(), v2.begin(), 1,
        std::multiplies<>(),  // 외부 연산: 곱
        std::plus<>()         // 내부 연산: 합
    );
    
    std::cout << "결과: " << result << std::endl;  // 315
    
    return 0;
}

---

5) partial_sum - 누적 합

시그니처:

template<class InputIt, class OutputIt>
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);

기본 사용

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(v.size());
    
    // 누적 합: [1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5]
    std::partial_sum(v.begin(), v.end(), result.begin());
    
    for (int x : result) {
        std::cout << x << " ";  // 1 3 6 10 15
    }
    std::cout << std::endl;
    
    return 0;
}

누적 곱

#include <numeric>
#include <vector>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(v.size());
    
    // 누적 곱
    std::partial_sum(v.begin(), v.end(), result.begin(), 
        std::multiplies<>());
    
    for (int x : result) {
        std::cout << x << " ";  // 1 2 6 24 120
    }
    
    return 0;
}

---

6) inclusive_scan vs exclusive_scan (C++17)

inclusive_scan

#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(v.size());
    
    // 누적 합 (병렬)
    std::inclusive_scan(
        std::execution::par,
        v.begin(), v.end(),
        result.begin()
    );
    
    for (int x : result) {
        std::cout << x << " ";  // 1 3 6 10 15
    }
    
    return 0;
}

exclusive_scan

#include <numeric>
#include <vector>
#include <execution>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(v.size());
    
    // 누적 합 (현재 원소 제외)
    std::exclusive_scan(
        std::execution::par,
        v.begin(), v.end(),
        result.begin(),
        0  // 초기값
    );
    
    for (int x : result) {
        std::cout << x << " ";  // 0 1 3 6 10
    }
    
    return 0;
}

차이점

• inclusive_scan: 현재 원소 포함
• exclusive_scan: 현재 원소 제외

---

7) adjacent_difference - 인접 차이

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 3, 6, 10, 15};
    std::vector<int> result(v.size());
    
    // 인접 차이: [v[0], v[1]-v[0], v[2]-v[1], ...]
    std::adjacent_difference(v.begin(), v.end(), result.begin());
    
    for (int x : result) {
        std::cout << x << " ";  // 1 2 3 4 5
    }
    
    return 0;
}

---

8) iota - 순차 값 생성

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v(10);
    
    // 1부터 순차 생성
    std::iota(v.begin(), v.end(), 1);
    
    for (int x : v) {
        std::cout << x << " ";  // 1 2 3 4 5 6 7 8 9 10
    }
    
    return 0;
}

---

고급 활용

1) 병렬 실행 정책

실행 정책:

정책	설명	사용 시나리오
seq	순차 실행	기본 (순서 보장)
par	병렬 실행	멀티코어 활용
par_unseq	병렬 + 벡터화	SIMD 최적화

벤치마크

#include <numeric>
#include <vector>
#include <execution>
#include <chrono>
#include <iostream>
int main() {
    std::vector<int> v(10000000, 1);
    
    auto start = std::chrono::high_resolution_clock::now();
    
    // 순차
    auto sum1 = std::reduce(v.begin(), v.end(), 0);
    
    auto mid = std::chrono::high_resolution_clock::now();
    
    // 병렬
    auto sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0);
    
    auto end = std::chrono::high_resolution_clock::now();
    
    auto seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(mid - start).count();
    auto par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - mid).count();
    
    std::cout << "순차: " << seq_time << "ms" << std::endl;
    std::cout << "병렬: " << par_time << "ms" << std::endl;
    std::cout << "배속: " << (double)seq_time / par_time << "x" << std::endl;
    
    return 0;
}

2) transform_reduce 고급 패턴

가중 평균

#include <numeric>
#include <vector>
#include <execution>
double weighted_average(const std::vector<double>& values, 
                       const std::vector<double>& weights) {
    double sum = std::transform_reduce(
        std::execution::par,
        values.begin(), values.end(),
        weights.begin(),
    );
    
    double weight_sum = std::reduce(
        std::execution::par,
        weights.begin(), weights.end(),
    );
    
    return sum / weight_sum;
}
int main() {
    std::vector<double> values = {85, 90, 78, 92};
    std::vector<double> weights = {0.3, 0.3, 0.2, 0.2};
    
    double avg = weighted_average(values, weights);
    std::cout << "가중 평균: " << avg << std::endl;  // 86.7
    
    return 0;
}

3) 범위 기반 누적 (C++20 Ranges)

#include <numeric>
#include <vector>
#include <ranges>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // C++20 ranges
    auto sum = std::accumulate(
        v | std::views::filter([](int x) { return x % 2 == 0; }),
    );
    
    std::cout << "짝수 합: " << sum << std::endl;  // 6 (2+4)
    
    return 0;
}

---

성능 비교

accumulate vs reduce 벤치마크

테스트: 1천만 개 정수 합계

알고리즘	실행 정책	시간	배속
accumulate	-	25ms	1x
reduce	seq	26ms	1x
reduce	par	8ms	3.1x
reduce	par_unseq	6ms	4.2x
결론: 병렬 실행으로 4배 개선

메모리 사용량

알고리즘	추가 메모리	비고
accumulate	O(1)	In-place
reduce	O(1)	In-place
partial_sum	O(n)	출력 버퍼
inclusive_scan	O(n)	출력 버퍼

---

실무 사례

사례 1: 통계 계산 - 평균, 분산, 표준편차

#include <numeric>
#include <vector>
#include <cmath>
#include <execution>
#include <iostream>
class Statistics {
public:
    static double mean(const std::vector<double>& data) {
        if (data.empty()) return 0.0;
        
        double sum = std::reduce(
            std::execution::par,
            data.begin(), data.end(),
        );
        
        return sum / data.size();
    }
    
    static double variance(const std::vector<double>& data) {
        if (data.size() < 2) return 0.0;
        
        double avg = mean(data);
        
        double sum_sq_diff = std::transform_reduce(
            std::execution::par,
            data.begin(), data.end(),
            0.0,
            std::plus<>(),
            [avg](double x) {
                double diff = x - avg;
                return diff * diff;
            }
        );
        
        return sum_sq_diff / (data.size() - 1);
    }
    
    static double stddev(const std::vector<double>& data) {
        return std::sqrt(variance(data));
    }
};
int main() {
    std::vector<double> scores = {85, 90, 78, 92, 88, 76, 95};
    
    std::cout << "평균: " << Statistics::mean(scores) << std::endl;
    std::cout << "분산: " << Statistics::variance(scores) << std::endl;
    std::cout << "표준편차: " << Statistics::stddev(scores) << std::endl;
    
    return 0;
}

사례 2: 금융 계산 - 복리 이자

#include <numeric>
#include <vector>
#include <cmath>
double compound_interest(double principal, double rate, int years) {
    std::vector<double> rates(years, 1.0 + rate);
    
    // 복리: principal * (1+rate)^years
    double multiplier = std::accumulate(
        rates.begin(), rates.end(),
        1.0,
        std::multiplies<>()
    );
    
    return principal * multiplier;
}
int main() {
    double principal = 1000000;  // 100만원
    double rate = 0.05;          // 5% 연이율
    int years = 10;
    
    double result = compound_interest(principal, rate, years);
    std::cout << "10년 후: " << result << "원" << std::endl;
    // 약 1,628,895원
    
    return 0;
}

사례 3: 데이터 분석 - 이동 평균

#include <numeric>
#include <vector>
#include <deque>
#include <iostream>
std::vector<double> moving_average(const std::vector<double>& data, size_t window) {
    std::vector<double> result;
    std::deque<double> window_data;
    double sum = 0.0;
    
    for (size_t i = 0; i < data.size(); ++i) {
        window_data.push_back(data[i]);
        sum += data[i];
        
        if (window_data.size() > window) {
            sum -= window_data.front();
            window_data.pop_front();
        }
        
        if (window_data.size() == window) {
            result.push_back(sum / window);
        }
    }
    
    return result;
}
int main() {
    std::vector<double> prices = {100, 102, 101, 105, 103, 107, 110};
    auto ma = moving_average(prices, 3);
    
    std::cout << "3일 이동 평균: ";
    for (double avg : ma) {
        std::cout << avg << " ";
    }
    // 101 102.67 103 105 106.67
    
    return 0;
}

---

트러블슈팅

문제 1: 초기값 타입 불일치

증상: 컴파일 오류 또는 잘못된 결과

std::vector<int> v = {1, 2, 3, 4, 5};
// ❌ 잘못된 초기값 타입
double sum = std::accumulate(v.begin(), v.end(), 0);  // int로 계산됨
// ✅ 올바른 초기값
double sum = std::accumulate(v.begin(), v.end(), 0.0);

문제 2: 오버플로우

증상: 큰 수의 합계가 음수로 나옴

std::vector<int> v = {1000000, 1000000, 1000000};
// ❌ int 오버플로우
int sum = std::accumulate(v.begin(), v.end(), 0);
// 결과: -1294967296 (오버플로우)
// ✅ long long 사용
long long sum = std::accumulate(v.begin(), v.end(), 0LL);
// 결과: 3000000

문제 3: 부동소수점 정밀도

증상: reduce와 accumulate 결과가 다름

std::vector<double> v = {0.1, 0.2, 0.3, 0.4, 0.5};
// accumulate: 순서 보장
double sum1 = std::accumulate(v.begin(), v.end(), 0.0);
// reduce: 순서 보장 안 됨
double sum2 = std::reduce(v.begin(), v.end(), 0.0);
// 미세한 차이 발생 가능

해결: 순서가 중요하면 accumulate 사용

문제 4: 병렬 실행 데이터 경합

증상: 병렬 실행 시 잘못된 결과

int counter = 0;
// ❌ 데이터 경합
std::for_each(std::execution::par, v.begin(), v.end(),
    [&counter](int x) { counter += x; });  // 경합!
// ✅ reduce 사용
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);

---

마무리

C++ <numeric> 헤더는 수치 연산을 표준 라이브러리로 간결하게 표현할 수 있게 합니다.

핵심 요약

1. 집계
   • accumulate: 순차 집계 (순서 보장)
   • reduce: 병렬 집계 (순서 비보장)
   • transform_reduce: 변환 후 집계
2. 누적
   • partial_sum: 누적 합 (순차)
   • inclusive_scan: 누적 합 (병렬, 현재 포함)
   • exclusive_scan: 누적 합 (병렬, 현재 제외)
3. 기타
   • inner_product: 내적
   • adjacent_difference: 인접 차이
   • iota: 순차 값 생성

선택 가이드

상황	알고리즘
순차 합계	accumulate
병렬 합계	reduce (par)
내적	inner_product 또는 transform_reduce
누적 합	partial_sum 또는 inclusive_scan
순차 생성	iota

코드 예제 치트시트

// 합계
int sum = std::accumulate(v.begin(), v.end(), 0);
// 곱
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>());
// 병렬 합계
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);
// 내적
int dot = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
// 누적 합
std::partial_sum(v.begin(), v.end(), result.begin());
// 순차 생성
std::iota(v.begin(), v.end(), 1);

다음 단계

• 알고리즘 가이드: C++ 알고리즘 완벽 가이드
• 생성 알고리즘: C++ Algorithm Generate
• 힙 알고리즘: C++ Algorithm Heap

참고 자료

• cppreference: https://en.cppreference.com/w/cpp/algorithm
• “C++17 The Complete Guide” - Nicolai M. Josuttis
• “Effective STL” - Scott Meyers 한 줄 정리: 수치 연산은 <numeric> 알고리즘으로 간결하게 표현하며, 대용량 데이터는 병렬 실행 정책으로 최적화한다.

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. C++ 헤더의 accumulate, reduce, transform_reduce, partial_sum, inner_product, iota 등 수치 알고리즘을 실전 예제와 함께 정리합니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ async & launch | std::async·future·launch 정책 완벽 정리
• C++ Parallel Algorithms | ‘병렬 알고리즘’ 가이드
• C++ Execution Policy | ‘실행 정책’ 가이드

---

이 글에서 다루는 키워드 (관련 검색어)

C++, 알고리즘, numeric, reduce, STL, accumulate 등으로 검색하시면 이 글이 도움이 됩니다.