STL 알고리즘

8.4 STL 알고리즘

STL 알고리즘은 컨테이너의 요소를 처리하는 다양한 함수를 제공합니다.

8.4.1 비수정 시퀀스 연산

요소를 수정하지 않고 조사하는 알고리즘:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>  // accumulate

// 홀수 여부 판별 함수
bool isOdd(int n) {
    return n % 2 != 0;
}

int main() {
    std::vector<int> vec = {5, 7, 3, 1, 9, 2, 8, 4, 6};
    
    // all_of: 모든 요소가 조건을 만족하는지 확인
    bool allOdd = std::all_of(vec.begin(), vec.end(), isOdd);
    std::cout << "모든 요소가 홀수인가? " << std::boolalpha << allOdd << std::endl;
    
    // any_of: 적어도 하나의 요소가 조건을 만족하는지 확인
    bool anyOdd = std::any_of(vec.begin(), vec.end(), isOdd);
    std::cout << "홀수가 있는가? " << anyOdd << std::endl;
    
    // none_of: 모든 요소가 조건을 만족하지 않는지 확인
    bool noneOdd = std::none_of(vec.begin(), vec.end(), isOdd);
    std::cout << "홀수가 없는가? " << noneOdd << std::endl;
    
    // for_each: 각 요소에 함수 적용
    std::cout << "모든 요소: ";
    std::for_each(vec.begin(), vec.end(), [](int n) {
        std::cout << n << " ";
    });
    std::cout << std::endl;
    
    // find: 특정 값 찾기
    auto it = std::find(vec.begin(), vec.end(), 9);
    if (it != vec.end()) {
        std::cout << "9의 위치: " << std::distance(vec.begin(), it) << std::endl;
    }
    
    // find_if: 조건을 만족하는 첫 번째 요소 찾기
    auto it2 = std::find_if(vec.begin(), vec.end(), [](int n) {
        return n > 5;
    });
    if (it2 != vec.end()) {
        std::cout << "5보다 큰 첫 번째 요소: " << *it2 << std::endl;
    }
    
    // count: 특정 값의 개수 세기
    int count1 = std::count(vec.begin(), vec.end(), 1);
    std::cout << "1의 개수: " << count1 << std::endl;
    
    // count_if: 조건을 만족하는 요소의 개수 세기
    int oddCount = std::count_if(vec.begin(), vec.end(), isOdd);
    std::cout << "홀수의 개수: " << oddCount << std::endl;
    
    // equal: 두 범위가 같은지 비교
    std::vector<int> vec2 = vec;
    bool areEqual = std::equal(vec.begin(), vec.end(), vec2.begin());
    std::cout << "vec와 vec2가 같은가? " << areEqual << std::endl;
    
    // accumulate: 범위 내 요소의 합계 계산
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "모든 요소의 합: " << sum << std::endl;
    
    // 사용자 정의 누적 함수
    int product = std::accumulate(vec.begin(), vec.end(), 1, 
                                 [](int acc, int val) { return acc * val; });
    std::cout << "모든 요소의 곱: " << product << std::endl;
    
    return 0;
}

8.4.2 수정 시퀀스 연산

요소를 수정하는 알고리즘:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {5, 7, 3, 1, 9, 2, 8, 4, 6};
    
    // copy: 범위를 다른 범위로 복사
    std::vector<int> vec2(vec.size());
    std::copy(vec.begin(), vec.end(), vec2.begin());
    
    std::cout << "vec2 (copy): ";
    for (const auto& elem : vec2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // copy_if: 조건을 만족하는 요소만 복사
    std::vector<int> vec3;
    std::copy_if(vec.begin(), vec.end(), std::back_inserter(vec3),
                [](int n) { return n % 2 == 0; });  // 짝수만 복사
    
    std::cout << "vec3 (짝수만): ";
    for (const auto& elem : vec3) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // transform: 각 요소에 함수를 적용하여 결과를 저장
    std::vector<int> vec4(vec.size());
    std::transform(vec.begin(), vec.end(), vec4.begin(),
                  [](int n) { return n * 2; });  // 각 요소를 2배로
    
    std::cout << "vec4 (2배): ";
    for (const auto& elem : vec4) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // 두 범위를 조합하는 transform
    std::vector<int> vec5 = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    std::vector<int> vec6(vec.size());
    std::transform(vec.begin(), vec.end(), vec5.begin(), vec6.begin(),
                  [](int a, int b) { return a + b; });  // 두 벡터의 대응하는 요소 합
    
    std::cout << "vec6 (vec + vec5): ";
    for (const auto& elem : vec6) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // replace: 특정 값을 다른 값으로 대체
    std::replace(vec2.begin(), vec2.end(), 9, 99);
    
    std::cout << "vec2 (9를 99로 대체): ";
    for (const auto& elem : vec2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // replace_if: 조건을 만족하는 요소를 대체
    std::replace_if(vec2.begin(), vec2.end(),
                   [](int n) { return n < 5; },  // 5보다 작은 요소를
                   0);                           // 0으로 대체
    
    std::cout << "vec2 (5 미만을 0으로 대체): ";
    for (const auto& elem : vec2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // fill: 범위를 특정 값으로 채움
    std::fill(vec2.begin(), vec2.begin() + 3, 100);
    
    std::cout << "vec2 (처음 3개를 100으로): ";
    for (const auto& elem : vec2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // generate: 함수 호출 결과로 범위를 채움
    int value = 1;
    std::generate(vec2.begin(), vec2.end(), [&value]() {
        return value++;  // 1부터 시작하는 연속된 값
    });
    
    std::cout << "vec2 (연속된 값): ";
    for (const auto& elem : vec2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // remove: 특정 값을 제거 (실제로 컨테이너 크기는 변경되지 않음)
    auto new_end = std::remove(vec2.begin(), vec2.end(), 5);
    
    std::cout << "vec2 (5 제거 후, 논리적 끝까지만): ";
    for (auto it = vec2.begin(); it != new_end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // remove_if: 조건을 만족하는 요소 제거
    new_end = std::remove_if(vec2.begin(), vec2.end(),
                            [](int n) { return n % 2 == 0; });  // 짝수 제거
    
    // erase-remove 관용구: 실제로 컨테이너에서 제거
    vec2.erase(new_end, vec2.end());
    
    std::cout << "vec2 (짝수 제거 후): ";
    for (const auto& elem : vec2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // unique: 연속된 중복 요소 제거
    std::vector<int> vec7 = {1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 5};
    auto unique_end = std::unique(vec7.begin(), vec7.end());
    vec7.erase(unique_end, vec7.end());
    
    std::cout << "vec7 (중복 제거 후): ";
    for (const auto& elem : vec7) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // reverse: 범위의 요소 순서를 뒤집음
    std::reverse(vec.begin(), vec.end());
    
    std::cout << "vec (뒤집은 후): ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // rotate: 범위의 요소를 회전
    std::rotate(vec.begin(), vec.begin() + 3, vec.end());
    
    std::cout << "vec (3칸 회전 후): ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // shuffle: 범위의 요소 무작위 섞기
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(vec.begin(), vec.end(), g);
    
    std::cout << "vec (섞은 후): ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

8.4.3 정렬 연산

요소를 정렬하는 알고리즘:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>  // std::greater
#include <string>

struct Person {
    std::string name;
    int age;
    
    // 비교를 위한 연산자 오버로딩
    bool operator<(const Person& other) const {
        return age < other.age;  // 나이로 오름차순 정렬
    }
};

int main() {
    std::vector<int> vec = {5, 7, 3, 1, 9, 2, 8, 4, 6};
    
    // sort: 기본 정렬 (오름차순)
    std::sort(vec.begin(), vec.end());
    
    std::cout << "vec (오름차순 정렬): ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // 내림차순 정렬
    std::sort(vec.begin(), vec.end(), std::greater<int>());
    
    std::cout << "vec (내림차순 정렬): ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // 사용자 정의 비교 함수 사용
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return (a % 2) < (b % 2);  // 짝수가 홀수보다 앞에 오도록
    });
    
    std::cout << "vec (짝수 먼저 정렬): ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // partial_sort: 일부만 정렬
    std::vector<int> vec2 = {5, 7, 3, 1, 9, 2, 8, 4, 6};
    std::partial_sort(vec2.begin(), vec2.begin() + 4, vec2.end());
    
    std::cout << "vec2 (앞 4개만 정렬): ";
    for (const auto& elem : vec2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // stable_sort: 동일한 값의 상대적 순서 유지
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 25},
        {"David", 20}
    };
    
    std::stable_sort(people.begin(), people.end());
    
    std::cout << "people (나이순 안정 정렬):" << std::endl;
    for (const auto& person : people) {
        std::cout << "  " << person.name << ": " << person.age << std::endl;
    }
    
    // nth_element: n번째 요소를 찾아 배치
    std::vector<int> vec3 = {5, 7, 3, 1, 9, 2, 8, 4, 6};
    std::nth_element(vec3.begin(), vec3.begin() + 4, vec3.end());
    
    std::cout << "vec3 (5번째 요소 찾기): ";
    for (const auto& elem : vec3) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    std::cout << "5번째 요소: " << vec3[4] << std::endl;
    
    // is_sorted: 정렬 여부 확인
    bool sorted = std::is_sorted(vec.begin(), vec.end());
    std::cout << "vec가 정렬되어 있는가? " << std::boolalpha << sorted << std::endl;
    
    // binary_search: 정렬된 범위에서 값 찾기 (이진 검색)
    std::sort(vec.begin(), vec.end());  // 이진 검색 전에 정렬 필요
    bool found = std::binary_search(vec.begin(), vec.end(), 7);
    std::cout << "7을 찾았는가? " << found << std::endl;
    
    // lower_bound와 upper_bound: 정렬된 범위에서 값의 경계 찾기
    auto lower = std::lower_bound(vec.begin(), vec.end(), 5);  // 5 이상인 첫 번째 요소
    auto upper = std::upper_bound(vec.begin(), vec.end(), 5);  // 5보다 큰 첫 번째 요소
    
    std::cout << "5 이상인 첫 번째 요소: " << *lower << std::endl;
    std::cout << "5보다 큰 첫 번째 요소: " << *upper << std::endl;
    
    // 값의 범위 계산
    auto range = std::equal_range(vec.begin(), vec.end(), 5);
    std::cout << "5의 범위: " << std::distance(range.first, range.second) << std::endl;
    
    // merge: 두 정렬된 범위 병합
    std::vector<int> vec4 = {1, 3, 5, 7, 9};
    std::vector<int> vec5 = {2, 4, 6, 8, 10};
    std::vector<int> vec6(vec4.size() + vec5.size());
    
    std::merge(vec4.begin(), vec4.end(), vec5.begin(), vec5.end(), vec6.begin());
    
    std::cout << "vec6 (병합 결과): ";
    for (const auto& elem : vec6) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

8.4.4 수치 연산

수치 계산을 위한 알고리즘:

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <iomanip>  // std::setprecision

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // accumulate: 합계 계산
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "합계: " << sum << std::endl;
    
    // 사용자 정의 합계 함수
    int sum_squares = std::accumulate(vec.begin(), vec.end(), 0,
                                     [](int acc, int val) {
                                         return acc + val * val;
                                     });
    std::cout << "제곱의 합: " << sum_squares << std::endl;
    
    // inner_product: 내적 계산
    std::vector<int> vec2 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int dot_product = std::inner_product(vec.begin(), vec.end(), vec2.begin(), 0);
    std::cout << "내적: " << dot_product << std::endl;
    
    // 사용자 정의 내적 함수
    int custom_product = std::inner_product(vec.begin(), vec.end(), vec2.begin(), 0,
                                           std::plus<int>(),      // 외부 연산 (합계)
                                           [](int a, int b) {     // 내부 연산 (곱셈 대신)
                                               return a * (b / 10);  // vec2의 각 요소를 10으로 나눈 후 곱
                                           });
    std::cout << "사용자 정의 내적: " << custom_product << std::endl;
    
    // adjacent_difference: 인접 요소 간의 차이 계산
    std::vector<int> diffs(vec.size());
    std::adjacent_difference(vec.begin(), vec.end(), diffs.begin());
    
    std::cout << "인접 차이: ";
    for (const auto& elem : diffs) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // 사용자 정의 인접 차이 함수 (합계 대신)
    std::vector<int> diffs2(vec.size());
    std::adjacent_difference(vec.begin(), vec.end(), diffs2.begin(),
                            [](int a, int b) { return a + b; });  // 차이 대신 합계
    
    std::cout << "인접 합계: ";
    for (const auto& elem : diffs2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // partial_sum: 부분합 계산
    std::vector<int> partial_sums(vec.size());
    std::partial_sum(vec.begin(), vec.end(), partial_sums.begin());
    
    std::cout << "부분합: ";
    for (const auto& elem : partial_sums) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // 사용자 정의 부분합 함수 (곱으로)
    std::vector<int> partial_products(vec.size());
    std::partial_sum(vec.begin(), vec.end(), partial_products.begin(),
                    std::multiplies<int>());  // 합계 대신 곱
    
    std::cout << "부분곱: ";
    for (const auto& elem : partial_products) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // iota: 연속된 값 생성
    std::vector<int> sequence(10);
    std::iota(sequence.begin(), sequence.end(), 1);  // 1부터 시작
    
    std::cout << "연속된 값: ";
    for (const auto& elem : sequence) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    // 통계 계산 (C++17에서는 <numeric> 헤더에 함수가 추가됨)
    // 여기서는 수동으로 계산
    
    // 평균
    double mean = static_cast<double>(sum) / vec.size();
    std::cout << "평균: " << mean << std::endl;
    
    // 분산
    double variance = 0.0;
    for (int val : vec) {
        variance += (val - mean) * (val - mean);
    }
    variance /= vec.size();
    
    // 표준 편차
    double stddev = std::sqrt(variance);
    
    std::cout << "분산: " << std::fixed << std::setprecision(2) << variance << std::endl;
    std::cout << "표준 편차: " << stddev << std::endl;
    
    return 0;
}