실행 가능한 C++ 문서: 알고리즘

Q: C++의 헤더는 무엇인가요?

은 std::find, std::sort, std::count_if, std::transform 같은 제네릭 함수를 담고 있는 표준 라이브러리 헤더입니다. 이들은 이터레이터 쌍(보통 begin()과 end())으로 기술되는 범위를 대상으로 동작하므로, 같은 알고리즘이 vector, array, string 또는 이터레이터를 제공하는 어떤 컨테이너에서도 동작합니다.

Q: C++에서 vector에 어떤 값이 존재하는지 어떻게 확인하나요?

std::find를 사용합니다: auto it = find(v.begin(), v.end(), target);. it == v.end()이면 값이 없는 것이고, 그렇지 않으면 it는 첫 번째 일치 항목을 가리킵니다. 정확한 값 대신 조건을 검사하려면 술어와 함께 std::any_of를 사용하세요.

Q: std::remove는 왜 실제로는 컨테이너에서 요소를 제거하지 않나요?

알고리즘은 컨테이너가 아니라 이터레이터만 보기 때문에 std::remove는 컨테이너를 줄일 수 없습니다. 남길 요소들을 앞으로 모으고, 새로운 논리적 끝을 가리키는 이터레이터를 반환할 뿐입니다. 남은 부분을 물리적으로 버리려면 뒤이어 v.erase(...)를 호출해야 합니다(erase-remove 관용구).

작성하지 않아도 되는 루프

이전 페이지에서 모든 컨테이너가 이터레이터 - begin()과 end()를 갖춘 가벼운 커서 - 를 내준다는 것을 보았습니다. 바로 이 추상화가 표준 알고리즘이 존재하는 이유 그 자체입니다. 데이터를 검색·계수·변환하고 싶을 때마다 날 for 루프를 작성하는 대신, <algorithm>의 이름 있는 함수를 호출하고 범위를 건네줍니다.

범위란 단지 두 개의 이터레이터입니다. 어디서 시작하고, 어디에서 멈출지의 한 칸 다음입니다. 모든 알고리즘이 이 동일한 이터레이터 언어를 사용하므로, 같은 find가 vector, string, 평범한 배열 어디에서나 동작합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // 16이 범위 [begin, end) 안에 있는가?
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

체득해야 할 패턴: 검색을 하는 알고리즘은 "아무것도 찾지 못함"을 뜻하기 위해 end() 이터레이터를 반환합니다. 결과를 역참조하기 전에 항상 end()와 비교하세요. end()를 역참조하는 것은 정의되지 않은 동작입니다.

술어로 계수하고 검사하기

많은 알고리즘은 술어 - 각 요소에 대해 bool을 반환하는 함수(보통 람다) - 를 받습니다. count_if는 일치 개수를 세고, all_of, any_of, none_of는 범위 전체에 대한 예/아니오 질문에 답합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // 4명 통과
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count(_if 없음)는 조건이 아니라 정확한 값을 세는 더 단순한 사촌입니다. 검사가 "이 특정 값"이 아니라 "규칙에 맞는 무엇이든"이 되는 순간 술어 버전으로 손을 뻗으세요.

범위를 변환하고 축약하기

두 일꾼이 데이터 처리의 대부분을 책임집니다. std::transform은 각 요소를 함수에 통과시켜 매핑하고, std::accumulate(<algorithm>이 아니라 <numeric>에서)는 범위를 하나의 값으로 접습니다.

transform은 결과를 출력 이터레이터를 통해 씁니다. 흔하고 위험한 실수는 출력을 빈 vector로 향하게 하는 것입니다. 알고리즘은 이미 공간이 있다고 가정하고 끝 너머에 씁니다. 대상의 크기를 먼저 지정하거나, 각 결과가 push_back되도록 back_inserter를 사용하세요.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // 비어 있음 - 아직 공간 없음

    // back_inserter는 결과가 도착할 때마다 `squares`를 키운다
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

accumulate는 초깃값에서 시작해 요소를 왼쪽에서 오른쪽으로 결합합니다. 초깃값의 타입이 중요합니다. 0(int)을 넘기면 합이 int에서 계산되어 오버플로하거나 잘릴 수 있습니다.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // 누계가 double로 유지되도록 0.0(double)에서 시작한다.
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

만약 accumulate(prices.begin(), prices.end(), 0)처럼 int 시드로 작성했다면 각 덧셈이 int에서 일어나 센트 단위가 사라졌을 것입니다. 시드 타입이 결과 타입을 조용히 결정합니다.

erase-remove 관용구

여기 모두를 놀라게 하는 함정이 있습니다. std::remove는 컨테이너에서 아무것도 제거하지 않습니다. 알고리즘은 이터레이터만 가지고 있어서 컨테이너의 크기를 바꿀 수 없습니다 - 컨테이너가 존재하는지조차 모릅니다. remove가 실제로 하는 일은 남길 요소를 모두 앞으로 옮기고, 꼬리를 명세되지 않은 상태로 남긴 뒤, 새로운 논리적 끝을 가리키는 이터레이터를 반환하는 것입니다.

// remove 단독으로는 크기가 그대로 - 이게 버그다:
remove(v.begin(), v.end(), 0);  // 무시해 버린 이터레이터를 반환한다
// v는 여전히 원래 크기. 꼬리는 쓰레기

요소를 진짜로 삭제하려면 remove를 컨테이너의 erase와 짝지어야 하며, 그래서 erase-remove 관용구라고 부릅니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove는 0이 아닌 값을 앞으로 모으고 새로운 끝을 반환한다
    // 2. erase는 거기서부터 진짜 끝까지 모두 잘라낸다
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

정확한 값 대신 술어를 쓰려면 remove_if를 사용하세요. C++20에서는 두 단계를 대신 해 주는 자유 함수 std::erase / std::erase_if로 이 번거로운 절차 전체를 건너뛸 수 있습니다: erase(v, 0);.

이터레이터가 유효 기간을 넘기는 것은 본인 책임

알고리즘이 이터레이터를 반환하므로, 그 이터레이터들은 이전 페이지에서 만난 것과 동일한 무효화 규칙의 적용을 받습니다. 이터레이터를 저장한 뒤 컨테이너를 수정하는 것 - 재할당을 유발하는 push_back, 또는 erase - 은 저장된 이터레이터를 댕글링 상태로 만들 수 있고, 그것을 사용하는 것은 정의되지 않은 동작입니다.

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // v의 저장 공간을 재할당할 수 있다
cout << *it;       // BUG: `it`는 이제 해제된 메모리를 가리킬 수 있다

안전한 습관: 알고리즘이 반환한 이터레이터는 컨테이너의 크기를 바꾸거나 재할당할 수 있는 어떤 연산보다 먼저, 즉시 사용하세요. 결과를 바탕으로 컨테이너를 변경해야 한다면 대신 인덱스(it - v.begin())를 잡아 두세요. 인덱스는 재할당에서도 살아남으니까요.

다음: 정렬

이제 검색, 계수, 변환, 축약을 보았지만, 자기만의 페이지를 가질 만큼 중요한 알고리즘이 하나 있습니다. std::sort는 범위를 제자리에서 재배열하고, 데이터가 일단 정렬되면 더 빠른, 정렬된 데이터 전용 알고리즘 집합(binary_search, lower_bound, equal_range)이 열립니다. 다음에는 정렬을 깊이 파고듭니다. 사용자 정의 비교자를 제공하는 방법, sort와 stable_sort의 차이, 그리고 정의되지 않은 동작을 피하기 위해 비교 함수가 지켜야 하는 규칙을 다룹니다.

자주 묻는 질문

C++의 <algorithm> 헤더는 무엇인가요?

<algorithm>은 std::find, std::sort, std::count_if, std::transform 같은 제네릭 함수를 담고 있는 표준 라이브러리 헤더입니다. 이들은 이터레이터 쌍(보통 begin()과 end())으로 기술되는 범위를 대상으로 동작하므로, 같은 알고리즘이 vector, array, string 또는 이터레이터를 제공하는 어떤 컨테이너에서도 동작합니다.

C++에서 vector에 어떤 값이 존재하는지 어떻게 확인하나요?

std::find를 사용합니다: auto it = find(v.begin(), v.end(), target);. it == v.end()이면 값이 없는 것이고, 그렇지 않으면 it는 첫 번째 일치 항목을 가리킵니다. 정확한 값 대신 조건을 검사하려면 술어와 함께 std::any_of를 사용하세요.

std::remove는 왜 실제로는 컨테이너에서 요소를 제거하지 않나요?

알고리즘은 컨테이너가 아니라 이터레이터만 보기 때문에 std::remove는 컨테이너를 줄일 수 없습니다. 남길 요소들을 앞으로 모으고, 새로운 논리적 끝을 가리키는 이터레이터를 반환할 뿐입니다. 남은 부분을 물리적으로 버리려면 뒤이어 v.erase(...)를 호출해야 합니다(erase-remove 관용구).