🧰 STL 알고리즘 3대장: sort, find, transform 제대로 써먹기

야, 너 혹시 아직도 배열 정렬하려고 버블 정렬 for문 두 겹 짜고 있어? 아니면 벡터에서 값 하나 찾으려고 for (int i = 0; ...) 돌리면서 flag = true 세우고 있진 않고? 😅
괜찮아, 다들 그렇게 시작해. 근데 C++에는 이미 검증된 고성능 도구 상자가 기본으로 들어 있어. 그게 바로 STL 알고리즘이야.

오늘은 그중에서도 실무와 코딩 테스트에서 가장 자주 쓰는 3대장, std::sort, std::find, std::transform을 친구한테 설명하듯 하나씩 뜯어볼 거야. 시간 복잡도 같은 팩트도 정확히 챙기고, 흔히 밟는 지뢰도 같이 피해가 보자고.

🧠 먼저 STL 알고리즘의 철학부터

STL(Standard Template Library)은 크게 컨테이너(vector, list, map 등), 반복자(iterator), 알고리즘(sort, find 등) 세 축으로 이뤄져 있어. 여기서 핵심 포인트는 알고리즘이 컨테이너를 직접 모른다는 거야.

알고리즘은 오직 반복자 한 쌍만 받아. 보통 first와 last인데, 범위는 반열린 구간 [first, last)야. 즉 first는 포함, last는 포함하지 않아. 그래서 v.end()는 마지막 원소 "다음" 위치를 가리키는 거고.
이 설계 덕분에 같은 std::find를 vector, list, deque, 심지어 일반 C 배열(포인터도 반복자처럼 동작하니까)에도 쓸 수 있어. 컨테이너 N개 × 알고리즘 M개를 N×M번 구현할 필요 없이 N+M으로 끝나는 거지. 이게 바로 제네릭 프로그래밍의 매력이야. ✨

📊 1. std::sort — 정렬은 그냥 이거 쓰면 돼

기본 사용법

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

int main() {
    std::vector<int> v = {5, 2, 9, 1, 7};
    std::sort(v.begin(), v.end());          // 오름차순: 1 2 5 7 9
    for (int x : v) std::cout << x << ' ';
}

기본 비교는 operator<야. 그래서 아무것도 안 넘기면 오름차순이 돼. 내림차순은 비교 함수를 넘겨주면 끝.

std::sort(v.begin(), v.end(), std::greater<int>());   // 9 7 5 2 1
// C++14부터는 std::greater<>() 처럼 타입 생략 가능
std::sort(v.rbegin(), v.rend());   // 역방향 반복자로 오름차순 = 결과적으로 내림차순

성능 팩트: 얼마나 빨라?

C++11 표준부터 std::sort는 최악의 경우에도 O(N log N) 번의 비교를 보장하도록 규정돼 있어. (C++03 시절엔 "평균" O(N log N)만 요구했었어.)
그래서 주요 구현체(GCC의 libstdc++, LLVM의 libc++, MSVC STL)는 보통 인트로소트(Introsort)를 써. 퀵소트로 달리다가 재귀 깊이가 너무 깊어지면 힙소트로 갈아타고, 구간이 작아지면 삽입 정렬로 마무리하는 하이브리드 방식이야. 퀵소트의 평균 속도 + 힙소트의 최악 보장, 둘 다 챙기는 영리한 녀석이지. 😎

람다로 커스텀 정렬하기

실전에선 구조체를 정렬하는 일이 훨씬 많아. 예를 들어 학생을 점수 내림차순, 점수가 같으면 이름 오름차순으로 정렬해보자.

struct Student {
    std::string name;
    int score;
};

std::vector<Student> s = {{"민수", 90}, {"지영", 95}, {"철수", 90}};

std::sort(s.begin(), s.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;  // 점수 내림차순
    return a.name < b.name;                            // 이름 오름차순
});

더 깔끔하게 하고 싶다면 std::tie를 쓰는 트릭도 있어. 튜플끼리 사전순 비교를 해주거든.

#include <tuple>
std::sort(s.begin(), s.end(), [](const Student& a, const Student& b) {
    return std::tie(b.score, a.name) < std::tie(a.score, b.name);
});

점수 쪽만 a, b 순서를 뒤집어서 내림차순을 만든 거야. 처음엔 헷갈리는데 익숙해지면 은근 중독돼. 🤓

🚨 가장 무서운 지뢰: Strict Weak Ordering

비교 함수는 아무렇게나 짜면 안 돼. 표준은 비교 함수가 엄격한 약순서(strict weak ordering)를 만족하라고 요구해. 쉽게 말하면 이거야:

제일 흔한 실수가 return a <= b;야. 이러면 comp(a, a)가 true가 돼서 ①번을 깨뜨려. 결과는? 정의되지 않은 동작(UB)이야. 정렬이 이상하게 되거나, 구현에 따라 배열 범위를 넘어 읽다가 프로그램이 터질 수도 있어. 실제로 코딩 테스트에서 "로컬에선 되는데 제출하면 런타임 에러" 나는 단골 원인이 이거야.

sort의 친척들

안정 정렬(stable)이 뭐냐면, 값이 같은 원소들의 기존 순서가 정렬 후에도 그대로 유지되는 성질이야. std::sort는 이걸 보장하지 않아. 예를 들어 "이미 이름순으로 정렬된 리스트를 점수순으로 다시 정렬하되, 동점자는 이름순 유지" 같은 요구라면 std::stable_sort가 정답이야.

그리고 "상위 10명만 필요해!" 같은 상황에서 백만 개 전체를 정렬하는 건 낭비야. 이럴 땐 partial_sort, 중앙값 하나만 필요하면 nth_element. 도구를 상황에 맞게 고르는 게 진짜 고수의 감각이지.

std::vector<int> v = {9, 4, 7, 1, 8, 2, 6};
std::partial_sort(v.begin(), v.begin() + 3, v.end());   // 앞 3개: 1 2 4 (나머지는 순서 미정)

std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
int median = v[v.size()/2];   // 중앙값 6

🔍 2. std::find — 찾아라, 그 원소를!

기본 사용법

std::find는 범위를 앞에서부터 순서대로 훑으면서 값이 같은(==) 첫 번째 원소의 반복자를 돌려줘. 못 찾으면? last를 돌려줘. nullptr도 -1도 아니야. 이게 진짜 중요해!

std::vector<int> v = {3, 8, 5, 1, 5};

auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) {
    std::cout << "찾음! 인덱스: " << std::distance(v.begin(), it);  // 2
} else {
    std::cout << "없음";
}

반복자에서 인덱스를 얻고 싶을 땐 std::distance(v.begin(), it) 또는 vector처럼 랜덤 액세스라면 it - v.begin()을 쓰면 돼.

find의 가족: find_if, find_if_not

"특정 값"이 아니라 "조건"으로 찾고 싶을 때가 더 많잖아? 그럴 땐 find_if야.

// 첫 번째 짝수 찾기
auto it = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

// 점수 90점 이상인 첫 학생 찾기
auto st = std::find_if(s.begin(), s.end(),
                       [](const Student& a) { return a.score >= 90; });

// 조건을 만족하지 "않는" 첫 원소 (C++11)
auto it2 = std::find_if_not(v.begin(), v.end(), [](int x) { return x > 0; });

참고로 단순히 "있냐 없냐"만 궁금하면 std::any_of, std::all_of, std::none_of가 의도를 더 잘 드러내. 개수가 궁금하면 std::count / std::count_if.

성능 팩트: find는 언제 쓰면 안 될까?

std::find는 선형 탐색이라 최대 N번 비교해. 즉 O(N). 원소가 몇 개 안 되거나 한두 번만 찾을 땐 이게 최고야. 근데 큰 데이터에서 반복적으로 검색해야 한다면 얘기가 달라져.

백만 개면 log₂(1,000,000) ≈ 19.9니까 이진 탐색은 약 20번이면 끝나. 차이가 엄청나지? 그래서 상황별로 이렇게 골라 써.

std::sort(v.begin(), v.end());
bool exists = std::binary_search(v.begin(), v.end(), 5);   // true/false만 반환

auto lb = std::lower_bound(v.begin(), v.end(), 5);   // 5 이상인 첫 위치
auto ub = std::upper_bound(v.begin(), v.end(), 5);   // 5 초과인 첫 위치
auto cnt = ub - lb;                                   // 5의 개수

문자열에서도 쓸 수 있어

std::string str = "hello world";
auto it = std::find(str.begin(), str.end(), 'w');   // 'w' 위치
// 부분 문자열 검색은 std::string::find 멤버나 std::search가 적합

🔄 3. std::transform — 데이터 변신 공장

기본 사용법 (단항 버전)

std::transform은 범위의 각 원소에 함수를 적용해서 그 결과를 출력 위치에 써. 함수형 언어의 map이랑 같은 개념이야. 파이썬의 map()이나 자바스크립트의 array.map() 써봤으면 바로 감 올 거야.

std::vector<int> v = {1, 2, 3, 4};
std::vector<int> out(v.size());     // 크기를 미리 확보!

std::transform(v.begin(), v.end(), out.begin(),
               [](int x) { return x * x; });   // out = 1 4 9 16

반환값은 마지막으로 쓴 원소 다음 위치의 출력 반복자야. 이어서 뭔가를 더 쓰고 싶을 때 유용해.

🚨 지뢰: 출력 공간 확보

제일 많이 하는 실수가 이거야.

std::vector<int> out;   // 비어 있음!
std::transform(v.begin(), v.end(), out.begin(), f);   // ❌ UB! 빈 공간에 쓰기

transform은 공간을 알아서 늘려주지 않아. 그냥 주어진 위치에 덮어쓸 뿐이야. 해결책은 두 가지.

// 방법 1: 크기 미리 확보
std::vector<int> out(v.size());
std::transform(v.begin(), v.end(), out.begin(), f);

// 방법 2: back_inserter로 push_back 하게 만들기
#include <iterator>
std::vector<int> out2;
out2.reserve(v.size());   // 재할당 줄이기용 (선택)
std::transform(v.begin(), v.end(), std::back_inserter(out2), f);

제자리 변환 (in-place)

출력 위치를 입력의 시작으로 주면 원본을 그대로 덮어쓸 수 있어. 표준이 이걸 명시적으로 허용해.

std::transform(v.begin(), v.end(), v.begin(), [](int x) { return x * 2; });

이항 버전: 두 범위를 합치기

입력 범위를 두 개 받아서 원소 쌍마다 함수를 적용하는 버전도 있어.

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {10, 20, 30};
std::vector<int> out(a.size());

std::transform(a.begin(), a.end(), b.begin(), out.begin(), std::plus<>());
// out = 11 22 33

실전 예제: 문자열 대소문자 변환

이거 진짜 자주 쓰는데, 숨은 함정이 하나 있어.

#include <cctype>
std::string s = "Hello STL";

// ❌ 위험할 수 있음
// std::transform(s.begin(), s.end(), s.begin(), ::toupper);

// ✅ 안전한 방법
std::transform(s.begin(), s.end(), s.begin(),
               [](unsigned char c) { return std::toupper(c); });

왜 굳이 unsigned char로 받냐고? std::toupper는 인자가 unsigned char로 표현 가능한 값이거나 EOF여야 한다고 규정돼 있어. 그런데 char가 signed인 환경(x86의 대부분 컴파일러가 그래)에서 한글 같은 멀티바이트 문자의 바이트는 음수가 될 수 있고, 그걸 그대로 넘기면 UB야. 게다가 std::toupper는 <locale>에 오버로드가 있어서 함수 이름만 넘기면 모호성 컴파일 에러가 날 때도 있고. 람다로 감싸면 두 문제가 한 번에 해결돼. 👍

타입 변환도 자유자재

std::vector<int> nums = {1, 2, 3};
std::vector<std::string> strs;
std::transform(nums.begin(), nums.end(), std::back_inserter(strs),
               [](int n) { return "#" + std::to_string(n); });
// strs = "#1" "#2" "#3"

// 구조체에서 특정 필드만 뽑기
std::vector<std::string> names;
std::transform(s_list.begin(), s_list.end(), std::back_inserter(names),
               [](const Student& st) { return st.name; });

🧩 세 녀석 합체! 실전 미니 프로젝트

이제 배운 걸 한 번에 써보자. 상황: 쇼핑몰 상품 목록에서 가격에 할인율 적용 → 가격순 정렬 → 특정 상품 찾기.

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

struct Item {
    std::string name;
    double price;
};

int main() {
    std::vector<Item> items = {
        {"키보드", 50000}, {"마우스", 20000},
        {"모니터", 200000}, {"헤드셋", 80000}
    };

    // 1) transform: 전 상품 10% 할인 (제자리 변환)
    std::transform(items.begin(), items.end(), items.begin(),
                   [](Item it) { it.price *= 0.9; return it; });

    // 2) sort: 가격 오름차순
    std::sort(items.begin(), items.end(),
              [](const Item& a, const Item& b) { return a.price < b.price; });

    // 3) find_if: 10만 원 이상인 첫 상품
    auto it = std::find_if(items.begin(), items.end(),
                           [](const Item& i) { return i.price >= 100000; });

    if (it != items.end())
        std::cout << "고가 첫 상품: " << it->name << " (" << it->price << "원)\n";
    // 출력: 고가 첫 상품: 모니터 (180000원)
}

참고로 정렬된 데이터니까 3번은 std::partition_point나 lower_bound로 O(log N)에 찾을 수도 있어. 이렇게 "앞 단계 결과를 활용해 다음 단계 알고리즘을 고르는" 감각이 쌓이면 코드 리뷰에서 칭찬받는 거야. 🏆

🚀 C++20 Ranges: 더 짧고 더 안전하게

C++20부터는 std::ranges 네임스페이스에 범위 기반 알고리즘이 추가됐어. begin(), end()를 일일이 안 써도 되고, 프로젝션(projection)이라는 강력한 기능도 생겼어.

#include <algorithm>
#include <ranges>

std::ranges::sort(v);                               // 범위 통째로
std::ranges::sort(items, {}, &Item::price);         // 프로젝션: price 기준 정렬
auto it = std::ranges::find(items, "마우스", &Item::name);  // name 필드로 검색

// views로 지연 평가 파이프라인
auto evens_squared = v
    | std::views::filter([](int x) { return x % 2 == 0; })
    | std::views::transform([](int x) { return x * x; });

프로젝션 덕분에 "가격 기준으로 정렬" 같은 걸 람다 없이 &Item::price 하나로 끝낼 수 있어. 또 ranges 알고리즘은 콘셉트(concepts)로 제약이 걸려 있어서 list에 sort를 쓰는 실수를 하면 훨씬 읽기 쉬운 에러가 나와. 그리고 views::transform은 즉시 계산하지 않고 값을 꺼낼 때 계산(지연 평가)한다는 점이 std::transform과의 큰 차이야.

⚡ 보너스: 병렬 실행 정책 (C++17)

C++17부터 많은 알고리즘이 실행 정책을 첫 인자로 받을 수 있어.

#include <execution>
std::sort(std::execution::par, v.begin(), v.end());
std::transform(std::execution::par_unseq, v.begin(), v.end(), v.begin(), f);

seq(순차), par(병렬), par_unseq(병렬+벡터화)가 있고, C++20에선 unseq가 추가됐어. 단, 데이터가 작으면 스레드 관리 비용 때문에 오히려 느려질 수 있고, 함수 안에서 공유 데이터를 건드리면 데이터 레이스가 생기니 조심해. GCC에선 구현에 따라 Intel TBB 링크(-ltbb)가 필요할 수 있어.

📋 한눈에 정리

📚 참고 자료

• cppreference — std::sort: https://en.cppreference.com/w/cpp/algorithm/sort
• cppreference — std::find, std::find_if: https://en.cppreference.com/w/cpp/algorithm/find
• cppreference — std::transform: https://en.cppreference.com/w/cpp/algorithm/transform
• cppreference — Named requirements: Compare: https://en.cppreference.com/w/cpp/named_req/Compare
• cppreference — std::toupper: https://en.cppreference.com/w/cpp/string/byte/toupper
• cppreference — Constrained algorithms (C++20): https://en.cppreference.com/w/cpp/algorithm/ranges