알고리즘

정렬, 검색, 개수 세기, 복사 같은 일은 거의 모든 프로그램에 필요하지만, 직접 구현하면 범위의 끝 처리나 효율에서 실수하기 쉽습니다. 표준 라이브러리의 알고리즘(algorithm)은 이런 일을 반복자 범위에 적용하는 함수 템플릿으로 제공하며, 동작과 시간 복잡도가 표준에 정해져 있습니다.

이 글은 자주 쓰는 알고리즘을 읽기와 검색, 정렬, 복사와 변환, 제거, 누적으로 나누어 보고, 직접 만든 타입에 알고리즘을 적용하는 방법과 C++20의 범위 알고리즘을 소개합니다. 알고리즘은 대부분 <algorithm>에, std::accumulate 같은 수치 연산은 <numeric>에 있습니다.

알고리즘의 형식

알고리즘은 컨테이너가 아니라 반복자의 쌍으로 범위를 받습니다. 컨테이너 전체를 처리할 때는 std::sort(v.begin(), v.end())처럼 begin()과 end()를 넘기고, 일부만 처리할 때는 그 구간의 반복자를 넘깁니다. 그래서 같은 알고리즘을 std::vector, std::deque, 배열에 똑같이 쓸 수 있습니다.

위 그림처럼 알고리즘을 호출하기 전에는 범위가 올바른지, 알고리즘이 요구하는 반복자의 종류를 갖췄는지 확인하고, 호출한 뒤에는 돌려받은 값과 바뀐 범위를 정해진 대로 읽어야 합니다. 많은 알고리즘이 반복자를 돌려주는데, 찾지 못하면 범위의 끝을 돌려주므로 간접 참조하기 전에 끝과 비교합니다.

읽고 찾는 알고리즘

원소를 바꾸지 않고 읽기만 하는 알고리즘입니다. 조건을 넘길 때는 [](int n) { return n % 2 == 0; } 같은 람다 표현식(lambda expression)을 많이 쓰는데, 이름 없는 함수를 그 자리에서 만드는 문법이며 람다 표현식에서 자세히 다룹니다.

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

int main() {
    std::vector<int> v{10, 20, 30, 40, 50};

    std::for_each(v.begin(), v.end(), [](int n) { std::cout << n * 2 << ' '; });
    std::cout << '\n';

    auto it = std::find(v.begin(), v.end(), 30);
    if (it != v.end()) {
        std::cout << std::distance(v.begin(), it) << '\n';
    }

    std::vector<int> w{1, 2, 2, 3, 2, 4};
    std::cout << std::count(w.begin(), w.end(), 2) << ' '
              << std::count_if(w.begin(), w.end(), [](int n) { return n % 2 == 0; }) << '\n';

    std::vector<int> m{10, 20, 5, 30, 15};
    std::cout << *std::min_element(m.begin(), m.end()) << ' '
              << *std::max_element(m.begin(), m.end()) << '\n';
}

20 40 60 80 100
2
3 4
5 30

std::for_each는 각 원소에 함수를 적용합니다. 여기서 람다는 원소를 값으로 받아 두 배를 출력할 뿐이므로 v의 원소는 바뀌지 않으며, 원소를 바꾸려면 int&로 받아야 합니다. std::find는 30을 가리키는 반복자를 돌려주고, std::distance로 그 위치가 인덱스 2임을 구합니다. std::count_if는 조건을 만족하는 원소의 개수를 세고, std::min_element와 std::max_element는 가장 작은 원소와 큰 원소를 가리키는 반복자를 돌려줍니다. 빈 범위에서는 끝을 돌려주므로, 범위가 비어 있을 수 있다면 간접 참조하기 전에 확인합니다.

정렬과 이진 탐색

std::sort는 범위를 오름차순으로 정렬하며, 셋째 인자로 비교 함수를 넘기면 그 순서로 정렬합니다. 임의 접근 반복자가 필요하므로 std::list에는 쓸 수 없고, list는 멤버 함수 sort()를 씁니다.

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

int main() {
    std::vector<int> v{5, 2, 8, 1, 9};
    std::sort(v.begin(), v.end());
    for (int n : v) { std::cout << n << ' '; }
    std::cout << '\n';

    const auto descending = std::greater<int>{};
    std::sort(v.begin(), v.end(), descending);
    for (int n : v) { std::cout << n << ' '; }
    std::cout << '\n';

    std::cout << std::boolalpha
              << std::binary_search(v.begin(), v.end(), 8, descending) << '\n';

    std::list<int> l{5, 2, 8, 1, 9};
    l.sort();
    for (int n : l) { std::cout << n << ' '; }
    std::cout << '\n';
}

1 2 5 8 9
9 8 5 2 1
true
1 2 5 8 9

std::greater<int>는 <functional>에 있는 함수 객체로, 큰 값이 앞에 오게 비교합니다. std::binary_search는 정렬된 범위를 절반씩 줄여 가는 이진 탐색으로 로그 시간에 값을 찾는데, 범위를 정렬한 것과 같은 비교 기준을 넘겨야 합니다. 내림차순으로 정렬한 범위에 기본 비교인 오름차순 기준으로 이진 탐색하면 전제가 맞지 않아 결과를 믿을 수 없습니다. binary_search는 있는지만 bool로 알려 주므로, 위치가 필요하면 같은 기준으로 std::lower_bound를 씁니다.

정렬에 넘기는 비교 함수는 엄격 약순서(strict weak ordering)를 만족해야 합니다. 쉽게 말해 comp(a, a)는 언제나 거짓이고, comp(a, b)가 참이면 comp(b, a)는 거짓이며, 순서가 앞뒤로 모순되지 않아야 합니다. <=로 비교하는 함수는 comp(a, a)가 참이 되어 이 조건을 어기며, 정렬 결과가 틀리거나 범위를 넘어 접근할 수 있습니다. 같은 값끼리의 원래 순서를 지켜야 한다면 std::sort 대신 std::stable_sort를 씁니다.

더 깊이: 정렬 함수의 실제 비용

표준은 std::sort의 알고리즘을 정하지 않고 비교 횟수만 정합니다. 처음의 C++98은 평균 $O(N \log N)$만 요구해서 최악의 경우 $O(N^2)$가 드는 퀵 정렬(quicksort)만으로도 구현할 수 있었지만, 결함 보고 LWG 713으로 최악의 경우에도 $O(N \log N)$이어야 한다고 바뀌었습니다. 그래서 구현들은 퀵 정렬의 최악의 경우를 다른 정렬로 피하는 인트로 정렬(introsort)을 흔히 씁니다. cppreference의 std::sort 설명에 따르면 LLVM의 libc++는 14에 와서야 이 최악의 경우 요구를 지키게 되었습니다.

std::stable_sort의 비용은 쓸 수 있는 메모리에 따라 달라집니다. 이 함수는 정렬할 범위와 같은 크기의 임시 버퍼를 할당하려 하고, 버퍼를 얻으면 $O(N \log N)$번, 얻지 못하면 더 느린 방법으로 $O(N \log^2 N)$번 비교합니다. 같은 값의 원래 순서를 지키는 대가가 추가 메모리이거나 더 많은 비교라는 뜻이므로, 메모리가 빠듯한 환경에서는 이 차이도 함께 따집니다.

복사와 변환

std::copy는 범위를 다른 위치에 복사하고, std::transform은 각 원소에 함수를 적용한 결과를 다른 위치에 씁니다. 결과를 쓸 위치는 원소가 들어갈 공간이 이미 있어야 하므로, 크기를 미리 맞추거나 삽입 반복자를 넘깁니다.

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

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

    std::vector<int> copied(source.size());
    std::copy(source.begin(), source.end(), copied.begin());

    std::vector<int> squared;
    std::transform(source.begin(), source.end(), std::back_inserter(squared),
                   [](int n) { return n * n; });

    for (int n : copied) { std::cout << n << ' '; }
    std::cout << '\n';
    for (int n : squared) { std::cout << n << ' '; }
    std::cout << '\n';
}

1 2 3 4 5
1 4 9 16 25

copied는 원소 다섯 개로 미리 만들어 두고 그 위에 복사했고, squared는 비어 있지만 std::back_inserter가 결과마다 push_back을 불러 원소를 추가합니다. 비어 있는 vector의 begin()에 그대로 복사하면 쓸 공간이 없어 정의되지 않은 동작이 되며, 알고리즘은 결과를 쓸 컨테이너의 크기를 늘려 주지 않습니다.

지우는 알고리즘

std::remove는 이름과 달리 컨테이너에서 원소를 지우지 않습니다. 지울 값이 아닌 원소를 범위의 앞쪽으로 모으고, 그 끝이 되는 새 위치를 돌려줄 뿐이며 컨테이너의 크기는 그대로입니다.

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

int main() {
    std::vector<int> v{1, 2, 3, 2, 4, 2, 5};
    auto newEnd = std::remove(v.begin(), v.end(), 2);
    std::cout << v.size() << ' ';
    v.erase(newEnd, v.end());
    std::cout << v.size() << '\n';
    for (int n : v) { std::cout << n << ' '; }
    std::cout << '\n';
}

7 4
1 3 4 5

std::remove 직후 [v.begin(), newEnd)에는 1 3 4 5가 있지만 크기는 여전히 7이고, newEnd부터 끝까지의 값은 정해지지 않습니다. 컨테이너의 erase로 그 구간을 지워야 실제로 크기가 4가 됩니다. 알고리즘은 반복자만 받으므로 컨테이너의 크기를 바꿀 수 없기 때문입니다. C++20부터는 std::erase(v, 2)와 std::erase_if로 두 단계를 한 번에 할 수 있습니다.

누적

<numeric>의 std::accumulate는 초깃값에서 시작해 원소를 차례로 더한 결과를 돌려줍니다. 앞의 두 인자는 다른 알고리즘처럼 범위를, 셋째 인자는 누적을 시작할 값을 줍니다. 아래 코드는 같은 함수로 정수의 합과 문자열의 연결을 구하므로, 두 호출에서 셋째 인자가 각각 무엇인지 비교해 보세요.

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

int main() {
    std::vector<int> v{1, 2, 3, 4, 5};
    std::cout << std::accumulate(v.begin(), v.end(), 0) << '\n';

    std::vector<std::string> words{"Hello", " ", "World", "!"};
    std::cout << std::accumulate(words.begin(), words.end(), std::string{}) << '\n';
}

15
Hello World!

누적하는 값의 타입은 초깃값의 타입으로 정해집니다. 그래서 문자열을 이어 붙일 때는 초깃값을 std::string{}으로 주어야 하며, ""를 주면 타입이 const char*가 되어 컴파일되지 않습니다. double 원소를 더할 때도 초깃값을 정수 0으로 주면 매 단계의 결과가 int로 잘리므로, 0.0을 줍니다.

직접 만든 타입과 알고리즘

알고리즘은 템플릿이므로 직접 만든 타입에도 쓸 수 있으며, 그 타입이 알고리즘이 쓰는 연산을 지원하면 됩니다. 비교 함수를 넘기면 타입에 <를 정의하지 않아도 정렬할 수 있습니다.

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

struct Person {
    std::string name;
    int age;
};

void print(const std::vector<Person>& people) {
    for (const auto& p : people) {
        std::cout << '[' << p.name << ", " << p.age << "] ";
    }
    std::cout << '\n';
}

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

    std::sort(people.begin(), people.end(),
              [](const Person& a, const Person& b) { return a.age < b.age; });
    print(people);

    std::ranges::sort(people, {}, &Person::name);
    print(people);
}

[Charlie, 25] [Alice, 30] [Bob, 35]
[Alice, 30] [Bob, 35] [Charlie, 25]

첫 정렬은 나이를 비교하는 람다를 넘겨 나이순으로, 둘째 정렬은 C++20의 범위 알고리즘 std::ranges::sort로 이름순으로 정렬했습니다. 범위 알고리즘은 반복자 쌍 대신 컨테이너를 그대로 받고, 셋째 인자로 원소에서 비교할 값을 꺼내는 프로젝션(projection)을 받을 수 있습니다. &Person::name을 넘기면 각 Person의 name으로 비교하며, 둘째 인자 {}는 기본 비교인 오름차순을 쓰겠다는 뜻입니다.

위 그림은 목적별로 대표적인 알고리즘과 호출할 때 지킬 조건을 정리한 것이고, 아래 그림은 호출 전후에 확인할 항목입니다. 필요한 헤더를 직접 포함했는지, 범위와 반복자의 종류가 맞는지, 비교 함수가 엄격 약순서인지, 결과를 쓸 공간이 있는지를 호출 전에, 돌려받은 반복자가 끝인지와 실제 크기가 바뀌었는지를 호출 뒤에 봅니다.

정리

• 알고리즘은 반복자 쌍으로 받은 범위에 연산을 적용하는 함수 템플릿이며, 대부분 <algorithm>과 <numeric>에 있습니다.
• find처럼 위치를 돌려주는 알고리즘은 찾지 못하면 범위의 끝을 돌려주므로, 간접 참조하기 전에 비교합니다.
• std::sort는 임의 접근 반복자와 엄격 약순서를 만족하는 비교 함수가 필요하며, 이진 탐색에는 정렬과 같은 비교 기준을 씁니다.
• copy와 transform의 결과를 쓸 곳에는 공간이 있어야 하며, 없으면 std::back_inserter를 씁니다.
• std::remove는 크기를 바꾸지 않으므로 erase와 함께 쓰거나, C++20의 std::erase를 씁니다.
• std::accumulate의 결과 타입은 초깃값이 정하며, C++20의 범위 알고리즘은 컨테이너와 프로젝션을 직접 받습니다.

연습 문제

1. 초깃값의 타입

std::vector<double> d{0.5, 0.5, 0.5};에 대해 std::accumulate(d.begin(), d.end(), 0)과 std::accumulate(d.begin(), d.end(), 0.0)은 각각 무엇을 돌려주나요?

2. 빈 vector에 복사하기

std::vector<int> src{1, 2, 3}; std::vector<int> dst; 다음에 std::copy(src.begin(), src.end(), dst.begin());를 실행하면 어떻게 되나요? 어떻게 고치나요?

3. 다른 기준으로 한 이진 탐색

sort_and_search.cpp에서 내림차순으로 정렬한 뒤 std::binary_search(v.begin(), v.end(), 8)처럼 비교 함수를 빼고 호출하면 어떻게 되나요?

다음 글 함수 객체에서는 알고리즘에 넘기는 비교와 조건을 함수 객체로 만드는 방법과, 상태를 가진 함수 객체를 다룹니다.