C++ Algorithm Numeric | accumulate·reduce·inner_product 완벽 정리

· 28분 읽기 · 수정 중급 튜토리얼
C++ Algorithm Numeric | accumulate·reduce·inner_product 완벽 정리

이 글의 핵심

C++ <numeric> 헤더의 수치 알고리즘—accumulate, reduce, transform_reduce, partial_sum 등을 병렬 실행 정책과 함께 실전 예제로 정리합니다.

들어가며

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

이 글을 읽으면

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

목차

  1. 기본 알고리즘
  2. 실전 구현
  3. 고급 활용
  4. 성능 비교
  5. 실무 사례
  6. 트러블슈팅
  7. 마무리

기본 알고리즘

주요 알고리즘 목록

알고리즘용도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(),
        0
    );
    
    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(),
        0.0
    );
    
    double weight_sum = std::reduce(
        std::execution::par,
        weights.begin(), weights.end(),
        0.0
    );
    
    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; }),
        0
    );
    
    std::cout << "짝수 합: " << sum << std::endl;  // 6 (2+4)
    
    return 0;
}

성능 비교

accumulate vs reduce 벤치마크

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

알고리즘실행 정책시간배속
accumulate-25ms1x
reduceseq26ms1x
reducepar8ms3.1x
reducepar_unseq6ms4.2x

결론: 병렬 실행으로 4배 개선

메모리 사용량

알고리즘추가 메모리비고
accumulateO(1)In-place
reduceO(1)In-place
partial_sumO(n)출력 버퍼
inclusive_scanO(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(),
            0.0
        );
        
        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

참고 자료

한 줄 정리: 수치 연산은 <numeric> 알고리즘으로 간결하게 표현하고, 대용량 데이터는 병렬 실행 정책으로 최적화한다.