C++ STL: 4장 - STL 알고리즘

4.1 알고리즘의 기본 개념

STL의 알고리즘(Algorithm)은 컨테이너의 데이터를 효율적으로 처리하기 위한 함수 템플릿 모음입니다. 데이터의 검색, 정렬, 변환 등 다양한 작업을 수행할 수 있으며, 이터레이터(iterator)를 통해 모든 종류의 컨테이너와 함께 사용할 수 있습니다.

알고리즘의 주요 특징

• 컨테이너 독립적 설계
• 템플릿 기반의 제네릭 프로그래밍
• 최적화된 성능 (O(1), O(log n), O(n), O(n log n) 등 다양한 시간 복잡도)

---

4.2 알고리즘의 종류

4.2.1 검색 알고리즘

데이터를 찾고 검색하는 알고리즘입니다.

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // find: 값 찾기
    auto it = std::find(numbers.begin(), numbers.end(), 3);
    if (it != numbers.end()) {
        std::cout << "찾은 값: " << *it << std::endl;
    }
    return 0;
}

4.2.2 정렬 알고리즘

데이터를 정렬하는 알고리즘입니다.

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

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};

    // 기본 정렬 (오름차순)
    std::sort(numbers.begin(), numbers.end());

    // C++11 이상: 사용자 정의 정렬 (람다 함수 사용)
    std::sort(numbers.begin(), numbers.end(),
        [](int a, int b) { return a > b; });  // 내림차순

    // 부분 정렬
    std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());

    return 0;
}

4.2.3 변환 알고리즘

데이터를 변환하거나 수정하는 알고리즘입니다.

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<int> result(numbers.size());

    // transform: 각 요소 변환
    std::transform(numbers.begin(), numbers.end(), result.begin(), [](int x) { return x * 2; });

    // replace: 값 교체
    std::replace(numbers.begin(), numbers.end(), 3, 30); // 3을 30으로 교체

    return 0;
}

4.2.4 수치 알고리즘

수학적 연산을 수행하는 알고리즘입니다.

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 합계 계산
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);

    // 부분합 계산
    std::vector<int> partial_sums(numbers.size());
    std::partial_sum(numbers.begin(), numbers.end(), partial_sums.begin());

    return 0;
}

---

4.3 알고리즘과 이터레이터

STL 알고리즘은 이터레이터(iterator)를 통해 컨테이너와 상호작용합니다. 이를 통해:

• 코드 재사용성 향상
• 일관된 인터페이스 제공
• 다양한 컨테이너 지원

예제

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

int main() {
    // vector에서 사용
    std::vector<int> vec = {1, 2, 3};
    auto vec_it = std::find(vec.begin(), vec.end(), 2);

    // list에서 동일한 알고리즘 사용
    std::list<int> lst = {1, 2, 3};
    auto lst_it = std::find(lst.begin(), lst.end(), 2);

    return 0;
}

---

실전 활용 팁

• 가능하면 STL 알고리즘을 사용하세요. 직접 구현하는 것보다 효율적이고 안전합니다.
• C++11 이상에서는 람다 함수(lambda function)로 알고리즘을 커스터마이즈할 수 있습니다:

std::sort(vec.begin(), vec.end(), [](const int& a, const int& b) { return a > b; }); // 내림차순 정렬

• 알고리즘 선택 시 성능을 고려하세요:
  • 정렬된 데이터: binary_search 사용 (시간 복잡도: O(log n))
  • 안정적 정렬: stable_sort 사용 (시간 복잡도: O(n log n))
  • 부분 정렬만 필요: partial_sort 사용 (시간 복잡도: O(n log k), k는 정렬할 요소 수)