STL 알고리즘을 활용한 컨테이너 조작 기법

비변형 시퀀스 알고리즘

이러한 알고리즘은 원본 컨테이너의 내용을 변경하지 않으며, 요소를 검색하거나 조건을 평가하는 데 사용됩니다.

요소 탐색: find 계열 함수

find(시작, 끝, 값): 지정된 값과 일치하는 첫 번째 요소의 반복자를 반환합니다. 못 찾으면 end()를 반환.
find_if(시작, 끝, 조건함수): 조건을 만족하는 첫 번째 요소를 찾습니다.
find_end(시작, 끝, 하위_시작, 하위_끝): 하위 시퀀스가 마지막으로 나타나는 위치를 반환.

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

std::vector<int> 데이터 = {10, 25, 40, 55, 70};

// 값 40 찾기
auto 위치 = std::find(데이터.begin(), 데이터.end(), 40);
if (위치 != 데이터.end()) {
    std::cout << "발견: " << *위치 << "\n";  // 출력: 40
}

// 50보다 큰 첫 번째 값 찾기
auto 조건_위치 = std::find_if(데이터.begin(), 데이터.end(),
    [](int n) { return n > 50; });
std::cout << "첫 번째 50초과 값: " << *조건_위치 << "\n";  // 출력: 55

// 부분 시퀀스 찾기
std::vector<int> 패턴 = {25, 40};
auto 패턴_위치 = std::find_end(데이터.begin(), 데이터.end(),
                               패턴.begin(), 패턴.end());
if (패턴_위치 != 데이터.end()) {
    std::cout << "패턴 시작 인덱스: " << 패턴_위치 - 데이터.begin() << "\n";
}

카운팅 및 반복 작업

count(시작, 끝, 값): 특정 값의 출현 횟수를 셉니다.
count_if(시작, 끝, 조건): 조건을 만족하는 요소의 수를 셉니다.
for_each(시작, 끝, 함수): 각 요소에 대해 함수를 실행합니다.

std::vector<int> 숫자들 = {1, 3, 3, 7, 9, 3};
int 세기 = std::count(숫자들.begin(), 숫자들.end(), 3);  // 결과: 3

int 홀수_개수 = std::count_if(숫자들.begin(), 숫자들.end(),
    [](int x) { return x % 2 == 1; });  // 결과: 6

// 모든 요소에 3배 적용
std::for_each(숫자들.begin(), 숫자들.end(),
    [](int& val) { val *= 3; });
// 숫자들: {3, 9, 9, 21, 27, 9}

범위 비교 및 조건 검사

equal(시작1, 끝1, 시작2): 두 범위의 요소가 동일한지 확인.
mismatch(시작1, 끝1, 시작2): 처음 불일치하는 위치 쌍을 반환.
all_of, any_of, none_of: 전체/일부/전혀 조건 만족 여부 확인.

std::vector<int> A = {2, 4, 8};
std::vector<int> B = {2, 4, 8};
bool 동일 = std::equal(A.begin(), A.end(), B.begin());  // true

std::vector<int> C = {2, 4, 9};
auto 차이 = std::mismatch(A.begin(), A.end(), C.begin());
if (차이.first != A.end()) {
    std::cout << "불일치: " << *(차이.first) << " vs " << *(차이.second) << "\n";
}

bool 모두_양수 = std::all_of(A.begin(), A.end(),
    [](int x) { return x > 0; });  // true
bool 하나라도_음수 = std::any_of(A.begin(), A.end(),
    [](int x) { return x < 0; });  // false

변형 시퀀스 알고리즘

이 그룹의 알고리즘은 컨테이너 내부의 데이터를 직접 수정하거나 새 위치로 이동시킵니다.

복사 및 변환

copy(시작, 끝, 목적지): 요소를 다른 위치로 복사합니다.
copy_if(시작, 끝, 목적지, 조건): 조건에 맞는 요소만 복사.
transform(시작, 끝, 출력, 함수): 함수를 적용하여 변환된 값을 저장.

std::vector<int> 원본 = {10, 15, 20, 25, 30};
std::vector<int> 대상(원본.size());

std::copy(원본.begin(), 원본.end(), 대상.begin());

std::vector<int> 필터링됨;
std::copy_if(원본.begin(), 원본.end(), std::back_inserter(필터링됨),
    [](int x) { return x >= 20; });  // 결과: {20, 25, 30}

// 제곱 변환
std::vector<int> 제곱값(원본.size());
std::transform(원본.begin(), 원본.end(), 제곱값.begin(),
    [](int x) { return x * x; });

// 두 시퀀스 결합
std::vector<int> X = {1, 2, 3};
std::vector<int> Y = {10, 20, 30};
std::vector<int> 합계(X.size());
std::transform(X.begin(), X.end(), Y.begin(), 합계.begin(),
    [](int a, int b) { return a + b; });  // {11, 22, 33}

내부 재구성

replace/replace_if: 특정 값을 다른 값으로 치환.
remove/remove_if: 조건에 맞는 요소를 논리적으로 제거 (erase와 함께 사용).
unique: 연속 중복 제거.

std::vector<int> 목록 = {5, 3, 5, 1, 5, 7};

// 모든 5를 99로 교체
std::replace(목록.begin(), 목록.end(), 5, 99);

// 50 이상인 값들을 0으로 바꾸기
std::replace_if(목록.begin(), 목록.end(),
    [](int x) { return x >= 50; }, 0);

// 짝수 제거
목록.erase(
    std::remove_if(목록.begin(), 목록.end(),
        [](int x) { return x % 2 == 0; }),
    목록.end()
);

// 인접 중복 제거 전 정렬 필요
std::sort(목록.begin(), 목록.end());
auto 새로운_끝 = std::unique(목록.begin(), 목록.end());
목록.erase(새로운_끝, 목록.end());

순서 조작

reverse: 순서를 뒤집습니다.
rotate: 특정 지점을 중심으로 회전.
shuffle: 요소를 무작위로 섞습니다.

std::vector<char> 문자 = {'a', 'b', 'c', 'd', 'e'};
std::reverse(문자.begin(), 문자.end());  // e d c b a

std::rotate(문자.begin(), 문자.begin() + 2, 문자.end());  // c d e a b

std::random_device rd;
std::mt19937 생성기(rd());
std::shuffle(문자.begin(), 문자.end(), 생성기);

정렬 및 검색 알고리즘

정렬 방법

sort: 일반 정렬 (고속, 불안정).
stable_sort: 안정 정렬 (입력 순서 유지).
partial_sort: 일부만 정렬.

std::vector<int> 배열 = {8, 1, 5, 3, 9, 2};

std::sort(배열.begin(), 배열.end());  // {1,2,3,5,8,9}

// 내림차순 정렬
std::sort(배열.begin(), 배열.end(), std::greater<int>());

// 상위 3개만 정렬
std::partial_sort(배열.begin(), 배열.begin() + 3, 배열.end());

이진 탐색 계열

정렬된 컨테이너에서 효율적인 검색을 제공합니다.

std::vector<int> 정렬됨 = {10, 20, 20, 30, 40};

bool 존재 = std::binary_search(정렬됨.begin(), 정렬됨.end(), 20);

// 20 이상인 첫 번째 위치
auto lb = std::lower_bound(정렬됨.begin(), 정렬됨.end(), 20);

// 20 초과인 첫 번째 위치
auto ub = std::upper_bound(정렬됨.begin(), 정렬됨.end(), 20);

병합 및 집합 연산

merge: 두 정렬된 시퀀스를 하나로 통합.
set_union, set_intersection: 집합 연산 수행.

std::vector<int> V1 = {1, 3, 5, 7};
std::vector<int> V2 = {3, 5, 6, 8};
std::vector<int> 결과;

std::merge(V1.begin(), V1.end(), V2.begin(), V2.end(),
           std::back_inserter(결과));

결과.clear();
std::set_intersection(V1.begin(), V1.end(), V2.begin(), V2.end(),
                      std::back_inserter(결과));  // {3, 5}

힙 및 수치 알고리즘

힙 조작

컨테이너를 힙 자료구조처럼 다룰 수 있습니다.

std::vector<int> 힙_데이터 = {3, 1, 4, 1, 5};

std::make_heap(힙_데이터.begin(), 힙_데이터.end());
힙_데이터.push_back(6);
std::push_heap(힙_데이터.begin(), 힙_데이터.end());

std::pop_heap(힙_데이터.begin(), 힙_데이터.end());
힙_데이터.pop_back();

std::sort_heap(힙_데이터.begin(), 히프_데이터.end());

수치 계산

<numeric> 헤더에 포함된 유용한 함수들입니다.

#include <numeric>

std::vector<int> 수치 = {1, 2, 3, 4, 5};

int 합 = std::accumulate(수치.begin(), 수치.end(), 0);
int 곱 = std::accumulate(수치.begin(), 수치.end(), 1,
                         std::multiplies<int>());

std::vector<int> 누적(수치.size());
std::partial_sum(수치.begin(), 수치.end(), 누적.begin());  // {1,3,6,10,15}

std::iota(수치.begin(), 수치.end(), 100);  // 100,101,102,103,104

핵심 사항 요약

정렬 의존성: binary_search, merge, set_* 함수는 입력이 반드시 정렬되어야 합니다.
제거 패턴: remove_if 후 반드시 erase를 호출해야 실제 크기가 줄어듭니다.
안정성: 요소의 상대 순서를 보장하려면 stable_sort를 사용하세요.

태그: STL 알고리즘 컨테이너 C++ 정렬

5월 22일 20:00에 게시됨

괴물 클럽