안동민 개발노트

컨테이너는 데이터를 저장하고, 반복자는 그 데이터에 접근하는 통로 역할을 합니다.

이제 STL의 마지막 주요 구성 요소이자 가장 강력한 기능 중 하나인 알고리즘(Algorithms) 에 대해 알아보겠습니다.

알고리즘은 컨테이너의 특정 타입에 종속되지 않고, 반복자를 통해 컨테이너의 요소들을 조작하거나 처리하는 일반화된 함수들의 집합입니다.

정렬, 검색, 복사, 변환 등 다양한 작업을 수행하는 함수들이 포함되어 있어, 개발자가 직접 복잡한 로직을 구현할 필요 없이 효율적이고 검증된 코드를 사용할 수 있게 해줍니다.

알고리즘(Algorithms)이란 무엇인가?

알고리즘은 컨테이너의 요소들을 대상으로 특정 작업을 수행하는 함수 템플릿입니다.

STL 알고리즘은 <algorithm>, <numeric>, <functional> 등의 헤더 파일에 정의되어 있으며, 대부분 std:: 네임스페이스 안에 있습니다.

알고리즘의 주요 특징

제네릭 프로그래밍: 컨테이너의 특정 타입에 묶이지 않고, 반복자(iterator)를 통해 작동하므로 모든 표준 컨테이너와 심지어 C-스타일 배열에도 적용할 수 있습니다.
효율성: STL 알고리즘은 고도로 최적화되어 있어, 직접 구현하는 것보다 대부분 더 효율적이고 버그가 적습니다.
재사용성: 한 번 구현된 알고리즘은 다양한 컨테이너와 데이터 타입에 대해 재사용될 수 있습니다.
선형 탐색, 정렬, 복사, 변환, 조건부 실행 등 다양한 기능 제공.

알고리즘의 일반적인 사용법

대부분의 STL 알고리즘은 하나 이상의 반복자 쌍을 매개변수로 받아 범위(Range) 를 지정합니다.

이 범위는 begin() 반복자와 end() 반복자로 정의됩니다. end() 반복자는 항상 "마지막 요소 다음"을 가리키는 점을 기억해야 합니다.

알고리즘 형식

std::알고리즘이름(first_iterator, last_iterator, ... 추가_매개변수 ...);

first_iterator: 범위의 시작을 가리키는 반복자입니다.
last_iterator: 범위의 끝(마지막 요소 다음)을 가리키는 반복자입니다.

주요 알고리즘 범주와 예시

STL 알고리즘은 기능에 따라 여러 범주로 나눌 수 있습니다.

여기서는 자주 사용되는 몇 가지 알고리즘을 소개합니다.

1. 비수정 시퀀스 연산 (Non-modifying Sequence Operations) 컨테이너의 내용을 변경하지 않고, 요소를 읽거나 검색하는 등의 작업을 수행합니다.

std::for_each: 범위 내의 모든 요소에 대해 지정된 함수를 적용합니다.

#include <vector>
#include <algorithm> // for_each
#include <iostream>
#include <numeric>   // for std::accumulate (예시 추가)
void print(int n) {
    std::cout << n << " ";
}
int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << "std::for_each: ";
    std::for_each(v.begin(), v.end(), print); // 각 요소에 대해 print 함수 호출
    std::cout << std::endl; // 출력: 10 20 30 40 50
    // 람다 함수 사용 (C++11 이상)
    std::cout << "std::for_each with lambda: ";
    std::for_each(v.begin(), v.end(), [](int n){
        std::cout << n * 2 << " "; // 각 요소를 두 배로 만들어서 출력
    });
    std::cout << std::endl; // 출력: 20 40 60 80 100

std::find: 특정 값을 검색하여 해당 값을 가리키는 반복자를 반환합니다. 찾지 못하면 end()를 반환합니다.

std::find 사용 예시

    auto it_find = std::find(v.begin(), v.end(), 30);
    if (it_find != v.end()) {
        std::cout << "Found 30 at position: " << std::distance(v.begin(), it_find) << std::endl;
    } else {
        std::cout << "30 not found.\n";
    } // 출력: Found 30 at position: 2

std::count: 범위 내에서 특정 값과 일치하는 요소의 개수를 셉니다.

std::count 사용 예시

    std::vector<int> v2 = {1, 2, 2, 3, 2, 4};
    int count_2 = std::count(v2.begin(), v2.end(), 2);
    std::cout << "Count of 2s: " << count_2 << std::endl; // 출력: 3

std::count_if: 특정 조건(프레디케이트)을 만족하는 요소의 개수를 셉니다.

std::count_if 사용 예시

    int count_even = std::count_if(v2.begin(), v2.end(), [](int n){ return n % 2 == 0; });
    std::cout << "Count of even numbers: " << count_even << std::endl; // 출력: 4
}

2. 수정 시퀀스 연산 (Modifying Sequence Operations) 컨테이너의 내용을 변경하는 작업을 수행합니다.

std::sort: 컨테이너의 요소들을 정렬합니다. 임의 접근 반복자를 지원하는 컨테이너에만 적용됩니다. (예: vector, deque, 배열)

std::sort 사용 예시

#include <vector>
#include <algorithm> // sort
#include <iostream>
#include <list> // list 예시
int main() {
    std::vector<int> v = {5, 2, 8, 1, 9};
    std::sort(v.begin(), v.end()); // 오름차순 정렬
    std::cout << "std::sort (vector): ";
    for (int n : v) std::cout << n << " "; // 출력: 1 2 5 8 9
    std::cout << std::endl;
    // 사용자 정의 비교 함수/람다를 통한 내림차순 정렬
    std::sort(v.begin(), v.end(), std::greater<int>()); // 또는 [](int a, int b){ return a > b; }
    std::cout << "std::sort (desc): ";
    for (int n : v) std::cout << n << " "; // 출력: 9 8 5 2 1
    std::cout << std::endl;
    // std::list는 sort() 멤버 함수를 제공 (양방향 반복자는 std::sort 사용 불가)
    std::list<int> l = {5, 2, 8, 1, 9};
    l.sort(); // list의 멤버 함수 sort 호출
    std::cout << "std::list::sort(): ";
    for (int n : l) std::cout << n << " "; // 출력: 1 2 5 8 9
    std::cout << std::endl;
}

std::copy: 한 범위의 요소를 다른 위치로 복사합니다.

std::copy 사용 예시

#include <vector>
#include <algorithm> // copy
#include <iostream>
int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination(source.size()); // 복사할 크기만큼 미리 할당
    std::copy(source.begin(), source.end(), destination.begin());
    std::cout << "std::copy: ";
    for (int n : destination) std::cout << n << " "; // 출력: 1 2 3 4 5
    std::cout << std::endl;
}

std::transform: 한 범위의 요소를 변환하여 다른 위치(또는 동일한 위치)에 저장합니다.

std::transform 사용 예시

#include <vector>
#include <algorithm> // transform
#include <iostream>
int main() {
    std::vector<int> original = {1, 2, 3, 4, 5};
    std::vector<int> squared(original.size());
    std::transform(original.begin(), original.end(), squared.begin(), [](int n){
        return n * n;
    });
    std::cout << "std::transform (squared): ";
    for (int n : squared) std::cout << n << " "; // 출력: 1 4 9 16 25
    std::cout << std::endl;
}

std::remove: 범위 내에서 특정 값과 일치하는 모든 요소를 "제거"합니다. (실제로 삭제하는 것이 아니라, 유효한 요소들을 앞으로 옮기고, 제거된 요소들은 범위의 끝으로 이동시킨 후, 유효한 요소의 새로운 end 반복자를 반환합니다. 실제로 컨테이너에서 제거하려면 erase와 함께 사용해야 합니다.)

std::remove 사용 예시

#include <vector>
#include <algorithm> // remove
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
    
    auto it = std::remove(v.begin(), v.end(), 2); // 2를 제거
    // v는 이제 {1, 3, 4, 5, X, X, X} 와 유사한 상태 (X는 의미 없는 값)
    // it는 5 다음 위치를 가리킴
    
    v.erase(it, v.end()); // 유효한 요소들만 남도록 실제 제거
    std::cout << "std::remove + erase: ";
    for (int n : v) std::cout << n << " "; // 출력: 1 3 4 5
    std::cout << std::endl;
}

3. 정렬 관련 알고리즘 (Sorting Related Operations)

std::min_element, std::max_element: 범위 내에서 최소/최대 요소를 가리키는 반복자를 반환합니다.

std::min_element, std::max_element 사용 예시

#include <vector>
#include <algorithm> // min_element, max_element
#include <iostream>
int main() {
    std::vector<int> v = {10, 20, 5, 30, 15};
    auto min_it = std::min_element(v.begin(), v.end());
    auto max_it = std::max_element(v.begin(), v.end());
    std::cout << "Min element: " << *min_it << std::endl; // 출력: 5
    std::cout << "Max element: " << *max_it << std::endl; // 출력: 30
}

4. 숫자 관련 알고리즘 (Numeric Operations) - <numeric> 헤더

std::accumulate: 범위 내의 요소들을 합산합니다.

std::accumulate 사용 예시

#include <vector>
#include <numeric>   // accumulate
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    int sum = std::accumulate(v.begin(), v.end(), 0); // 초기값 0
    std::cout << "Sum: " << sum << std::endl; // 출력: 15
    // 문자열 연결도 가능
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    std::string concat = std::accumulate(words.begin(), words.end(), std::string(""));
    std::cout << "Concatenated string: " << concat << std::endl; // 출력: Hello World!
}

사용자 정의 타입과 알고리즘

STL 알고리즘은 템플릿으로 구현되어 있기 때문에, 사용자 정의 타입에도 적용할 수 있습니다.

단, 해당 타입이 알고리즘이 요구하는 연산(예: std::sort의 경우 < 연산자, std::find의 경우 == 연산자)을 지원해야 합니다.

연산자 오버로딩을 통해 이를 가능하게 할 수 있습니다.

사용자 정의 타입과 알고리즘

#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <string>

class Person {
public:
    std::string name;
    int age;

    Person(std::string n, int a) : name(n), age(a) {}

    // << 연산자 오버로딩 (출력용)
    friend std::ostream& operator<<(std::ostream& os, const Person& p) {
        os << "[" << p.name << ", " << p.age << "]";
        return os;
    }
};

// 1. 나이 기준 오름차순 비교 함수 (전역 함수 또는 람다)
bool comparePersonsByAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

// 2. 이름 기준 오름차순 비교를 위한 함수 객체 (Functor)
struct ComparePersonsByName {
    bool operator()(const Person& p1, const Person& p2) const {
        return p1.name < p2.name;
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Charlie", 25},
        {"Bob", 35}
    };

    std::cout << "Original order:\n";
    for (const auto& p : people) {
        std::cout << p << " ";
    }
    std::cout << std::endl;

    // 나이 기준 정렬 (람다 사용)
    std::sort(people.begin(), people.end(), [](const Person& p1, const Person& p2){
        return p1.age < p2.age;
    });
    std::cout << "Sorted by age:\n";
    for (const auto& p : people) {
        std::cout << p << " ";
    }
    std::cout << std::endl; // 출력: [Charlie, 25] [Alice, 30] [Bob, 35]

    // 이름 기준 정렬 (함수 객체 사용)
    std::sort(people.begin(), people.end(), ComparePersonsByName());
    std::cout << "Sorted by name:\n";
    for (const auto& p : people) {
        std::cout << p << " ";
    }
    std::cout << std::endl; // 출력: [Alice, 30] [Bob, 35] [Charlie, 25]

    return 0;
}

알고리즘 사용 시 고려사항

헤더 파일 포함: 사용할 알고리즘이 정의된 적절한 헤더 파일을 포함해야 합니다. 대부분 <algorithm>에 있습니다. 숫자 관련은 <numeric>, 함수 객체는 <functional> 등.
반복자 타입 확인: 알고리즘이 요구하는 반복자 타입(예: 임의 접근 반복자, 양방향 반복자)을 컨테이너가 제공하는지 확인해야 합니다.
Side Effects (부작용): std::remove처럼 컨테이너의 크기를 실제로 변경하지 않고, 요소를 옮겨놓기만 하는 알고리즘들이 있습니다. 이런 경우, 뒤에 erase() 멤버 함수를 호출하여 실제로 제거해야 합니다.
복사 vs 이동 (C++11 이후): std::copy와 std::move 같은 알고리즘은 요소의 복사 또는 이동 의미론을 따릅니다.
성능: STL 알고리즘은 일반적으로 매우 효율적이지만, 대규모 데이터셋에서는 성능 특성(O(N), O(N log N) 등)을 고려해야 합니다.

알고리즘

알고리즘(Algorithms)이란 무엇인가?

알고리즘의 일반적인 사용법

주요 알고리즘 범주와 예시

사용자 정의 타입과 알고리즘

알고리즘 사용 시 고려사항

On this page