콘텐츠로 이동

C++ Algorithm 헤더 완벽 가이드

개요

<algorithm> 헤더는 C++ STL의 핵심으로, 컨테이너의 요소들을 조작하는 다양한 알고리즘을 제공합니다.

목차

검색 알고리즘

선형 검색

#include <algorithm>
#include <vector>

// find: 값 찾기
auto it = find(vec.begin(), vec.end(), 5);
if (it != vec.end()) {
    cout << "Found at position: " << distance(vec.begin(), it) << endl;
}

// find_if: 조건 만족하는 첫 번째 요소 찾기
auto it = find_if(vec.begin(), vec.end(), [](int x) { return x > 10; });

// find_if_not: 조건 만족하지 않는 첫 번째 요소
auto it = find_if_not(vec.begin(), vec.end(), [](int x) { return x > 0; });

// count: 특정 값의 개수
int cnt = count(vec.begin(), vec.end(), 5);

// count_if: 조건 만족하는 요소의 개수
int cnt = count_if(vec.begin(), vec.end(), [](int x) { return x > 10; });

이진 검색 (정렬된 범위에서)

vector<int> vec = {1, 3, 5, 7, 9, 11, 13};

// binary_search: 값 존재 여부 확인
bool found = binary_search(vec.begin(), vec.end(), 7); // true

// lower_bound: 해당 값 이상이 처음 나타나는 위치
auto it = lower_bound(vec.begin(), vec.end(), 7);

// upper_bound: 해당 값 초과가 처음 나타나는 위치
auto it = upper_bound(vec.begin(), vec.end(), 7);

// equal_range: lower_bound와 upper_bound를 동시에
auto range = equal_range(vec.begin(), vec.end(), 7);
// range.first = lower_bound, range.second = upper_bound

부분 시퀀스 검색

vector<int> haystack = {1, 2, 3, 4, 5, 6, 7, 8};
vector<int> needle = {3, 4, 5};

// search: 부분 시퀀스 찾기
auto it = search(haystack.begin(), haystack.end(), needle.begin(), needle.end());

// search_n: 연속된 n개의 같은 값 찾기
auto it = search_n(haystack.begin(), haystack.end(), 2, 5); // 5가 2번 연속

// find_end: 마지막으로 일치하는 부분 시퀀스
auto it = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());

// find_first_of: 여러 값 중 하나라도 일치하는 첫 번째 요소
vector<int> targets = {3, 7, 9};
auto it = find_first_of(haystack.begin(), haystack.end(), targets.begin(), targets.end());

정렬 알고리즘

기본 정렬

vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

// sort: 일반 정렬 (Quick Sort 기반, 평균 O(n log n))
sort(vec.begin(), vec.end());

// sort with custom comparator
sort(vec.begin(), vec.end(), greater<int>()); // 내림차순
sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });

// stable_sort: 안정 정렬 (같은 값의 상대적 순서 유지)
stable_sort(vec.begin(), vec.end());

// partial_sort: 부분 정렬 (상위 k개만 정렬)
partial_sort(vec.begin(), vec.begin() + 3, vec.end()); // 상위 3개만 정렬

// nth_element: n번째 요소를 올바른 위치에 배치
nth_element(vec.begin(), vec.begin() + 3, vec.end()); // 4번째로 작은 요소를 찾음

정렬 상태 확인

// is_sorted: 정렬되어 있는지 확인
bool sorted = is_sorted(vec.begin(), vec.end());

// is_sorted_until: 정렬이 깨지는 첫 번째 위치 반환
auto it = is_sorted_until(vec.begin(), vec.end());

변경 불가능한 시퀀스 연산

전체 요소 검사

vector<int> vec = {2, 4, 6, 8, 10};

// all_of: 모든 요소가 조건을 만족하는지
bool all_even = all_of(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

// any_of: 하나라도 조건을 만족하는지
bool has_big = any_of(vec.begin(), vec.end(), [](int x) { return x > 5; });

// none_of: 모든 요소가 조건을 만족하지 않는지
bool no_negative = none_of(vec.begin(), vec.end(), [](int x) { return x < 0; });

두 범위 비교

vector<int> vec1 = {1, 2, 3, 4, 5};
vector<int> vec2 = {1, 2, 3, 4, 5};

// equal: 두 범위가 같은지
bool same = equal(vec1.begin(), vec1.end(), vec2.begin());

// mismatch: 첫 번째로 다른 위치의 쌍 반환
auto pair = mismatch(vec1.begin(), vec1.end(), vec2.begin());

// lexicographical_compare: 사전식 순서 비교
bool less = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());

변경 가능한 시퀀스 연산

복사 연산

vector<int> src = {1, 2, 3, 4, 5};
vector<int> dest(5);

// copy: 범위 복사
copy(src.begin(), src.end(), dest.begin());

// copy_if: 조건 만족하는 요소만 복사
copy_if(src.begin(), src.end(), dest.begin(), [](int x) { return x > 2; });

// copy_n: n개 요소 복사
copy_n(src.begin(), 3, dest.begin());

// copy_backward: 뒤에서부터 복사 (겹치는 범위에서 안전)
copy_backward(src.begin(), src.begin() + 3, dest.end());

이동 연산

vector<string> src = {"hello", "world", "test"};
vector<string> dest(3);

// move: 이동 (원본은 유효하지만 불특정 상태)
move(src.begin(), src.end(), dest.begin());

채우기 연산

vector<int> vec(10);

// fill: 값으로 채우기
fill(vec.begin(), vec.end(), 42);

// fill_n: n개 요소를 값으로 채우기
fill_n(vec.begin(), 5, 100);

// generate: 함수 결과로 채우기
generate(vec.begin(), vec.end(), []() { return rand() % 100; });

// generate_n: n개 요소를 함수 결과로 채우기
generate_n(vec.begin(), 5, []() { return rand() % 100; });

// iota: 연속된 값으로 채우기 (C++11)
iota(vec.begin(), vec.end(), 1); // 1, 2, 3, 4, 5...

변환 연산

vector<int> src = {1, 2, 3, 4, 5};
vector<int> dest(5);

// transform: 단항 연산
transform(src.begin(), src.end(), dest.begin(), [](int x) { return x * x; });

// transform: 이항 연산
vector<int> src2 = {1, 1, 1, 1, 1};
transform(src.begin(), src.end(), src2.begin(), dest.begin(), plus<int>());

교체 연산

vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

// replace: 값 교체
replace(vec.begin(), vec.end(), 2, 99);

// replace_if: 조건 만족하는 값 교체
replace_if(vec.begin(), vec.end(), [](int x) { return x > 3; }, 0);

// replace_copy: 교체하여 다른 컨테이너에 복사
vector<int> dest(vec.size());
replace_copy(vec.begin(), vec.end(), dest.begin(), 2, 99);

제거 연산

vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

// remove: 값 제거 (실제로는 뒤로 이동, 크기는 변하지 않음)
auto it = remove(vec.begin(), vec.end(), 2);
vec.erase(it, vec.end()); // 실제 제거

// remove_if: 조건 만족하는 요소 제거
auto it = remove_if(vec.begin(), vec.end(), [](int x) { return x > 3; });
vec.erase(it, vec.end());

// unique: 연속된 중복 요소 제거 (정렬된 상태에서 사용)
sort(vec.begin(), vec.end());
auto it = unique(vec.begin(), vec.end());
vec.erase(it, vec.end());

분할 연산

vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// partition: 조건 만족하는 요소를 앞으로
auto it = partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

// stable_partition: 안정 분할 (상대적 순서 유지)
auto it = stable_partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

// is_partitioned: 분할되어 있는지 확인
bool partitioned = is_partitioned(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

// partition_point: 분할 지점 찾기
auto it = partition_point(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

병합 연산

vector<int> vec1 = {1, 3, 5, 7, 9};
vector<int> vec2 = {2, 4, 6, 8, 10};
vector<int> result(vec1.size() + vec2.size());

// merge: 두 정렬된 범위 병합
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

// inplace_merge: 제자리 병합
vector<int> vec = {1, 3, 5, 2, 4, 6};
sort(vec.begin(), vec.begin() + 3);
sort(vec.begin() + 3, vec.end());
inplace_merge(vec.begin(), vec.begin() + 3, vec.end());

힙 연산

vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

// make_heap: 힙 생성
make_heap(vec.begin(), vec.end()); // max heap

// push_heap: 힙에 요소 추가 (끝에 추가 후 호출)
vec.push_back(10);
push_heap(vec.begin(), vec.end());

// pop_heap: 힙에서 최대값 제거 (맨 뒤로 이동)
pop_heap(vec.begin(), vec.end());
vec.pop_back();

// sort_heap: 힙 정렬
sort_heap(vec.begin(), vec.end());

// is_heap: 힙인지 확인
bool is_heap_check = is_heap(vec.begin(), vec.end());

// is_heap_until: 힙 속성이 깨지는 첫 번째 위치
auto it = is_heap_until(vec.begin(), vec.end());

최대/최소 연산

vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

// min_element, max_element: 최소/최대 요소의 반복자
auto min_it = min_element(vec.begin(), vec.end());
auto max_it = max_element(vec.begin(), vec.end());

// minmax_element: 최소/최대를 동시에
auto minmax = minmax_element(vec.begin(), vec.end());
// minmax.first = min_element, minmax.second = max_element

// min, max: 두 값 중 최소/최대
int smaller = min(10, 20);
int larger = max(10, 20);

// minmax: 두 값의 최소/최대를 동시에
auto result = minmax(10, 20); // {10, 20}

// clamp: 값을 범위 내로 제한 (C++17)
int clamped = clamp(15, 10, 20); // 15 (10 ≤ 15 ≤ 20)
int clamped2 = clamp(5, 10, 20);  // 10 (5 < 10)

수치 연산

#include <numeric>
vector<int> vec = {1, 2, 3, 4, 5};

// accumulate: 누적 합
int sum = accumulate(vec.begin(), vec.end(), 0);
int product = accumulate(vec.begin(), vec.end(), 1, multiplies<int>());

// reduce: 병렬 처리 가능한 누적 연산 (C++17)
int sum2 = reduce(vec.begin(), vec.end(), 0);

// transform_reduce: 변환 후 누적 (C++17)
int sum_of_squares = transform_reduce(vec.begin(), vec.end(), 0, plus<>(), 
                                      [](int x) { return x * x; });

// partial_sum: 부분 합 배열
vector<int> prefix_sum(vec.size());
partial_sum(vec.begin(), vec.end(), prefix_sum.begin());

// adjacent_difference: 인접 차이
vector<int> diff(vec.size());
adjacent_difference(vec.begin(), vec.end(), diff.begin());

// inner_product: 내적
vector<int> vec2 = {1, 1, 1, 1, 1};
int dot_product = inner_product(vec.begin(), vec.end(), vec2.begin(), 0);

집합 연산 (정렬된 범위에서)

vector<int> set1 = {1, 2, 3, 4, 5};
vector<int> set2 = {3, 4, 5, 6, 7};
vector<int> result;

// set_union: 합집합
set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), 
          back_inserter(result));

// set_intersection: 교집합
result.clear();
set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), 
                back_inserter(result));

// set_difference: 차집합
result.clear();
set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), 
               back_inserter(result));

// set_symmetric_difference: 대칭 차집합
result.clear();
set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), 
                        back_inserter(result));

// includes: 부분집합 여부 확인
bool is_subset = includes(set2.begin(), set2.end(), set1.begin(), set1.end());

순열 연산

vector<int> vec = {1, 2, 3};

// next_permutation: 다음 순열
do {
    for (int x : vec) cout << x << " ";
    cout << endl;
} while (next_permutation(vec.begin(), vec.end()));

// prev_permutation: 이전 순열
sort(vec.rbegin(), vec.rend()); // 내림차순으로 정렬
do {
    for (int x : vec) cout << x << " ";
    cout << endl;
} while (prev_permutation(vec.begin(), vec.end()));

// is_permutation: 순열인지 확인
vector<int> vec2 = {3, 1, 2};
bool is_perm = is_permutation(vec.begin(), vec.end(), vec2.begin());

기타 유용한 연산

vector<int> vec = {1, 2, 3, 4, 5};

// reverse: 순서 뒤집기
reverse(vec.begin(), vec.end());

// rotate: 회전
rotate(vec.begin(), vec.begin() + 2, vec.end()); // 2칸 왼쪽 회전

// shuffle: 무작위 섞기 (C++11)
random_device rd;
mt19937 g(rd());
shuffle(vec.begin(), vec.end(), g);

// sample: 무작위 샘플링 (C++17)
vector<int> source = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> sample_vec(3);
sample(source.begin(), source.end(), sample_vec.begin(), 3, g);

실전 예제

1. 중복 제거

vector<int> remove_duplicates(vector<int> vec) {
    sort(vec.begin(), vec.end());
    auto it = unique(vec.begin(), vec.end());
    vec.erase(it, vec.end());
    return vec;
}

2. 조건 만족하는 요소만 필터링

vector<int> filter_even(const vector<int>& vec) {
    vector<int> result;
    copy_if(vec.begin(), vec.end(), back_inserter(result), 
            [](int x) { return x % 2 == 0; });
    return result;
}

3. Top K 찾기

vector<int> top_k(vector<int> vec, int k) {
    partial_sort(vec.begin(), vec.begin() + k, vec.end(), greater<int>());
    vec.resize(k);
    return vec;
}

4. 빈도수 계산

map<int, int> count_frequency(const vector<int>& vec) {
    map<int, int> freq;
    for (int x : vec) {
        freq[x]++;
    }
    return freq;
}

5. 배열 회전

void rotate_left(vector<int>& vec, int k) {
    k %= vec.size();
    rotate(vec.begin(), vec.begin() + k, vec.end());
}

성능 고려사항

시간 복잡도

  • 정렬: sort() - O(n log n), partial_sort() - O(n log k)
  • 검색: find() - O(n), binary_search() - O(log n)
  • 힙: make_heap() - O(n), push_heap()/pop_heap() - O(log n)
  • 집합 연산: O(n + m) (n, m은 각 집합의 크기)

메모리 효율성

  • stable_* 알고리즘들은 추가 메모리를 사용할 수 있음
  • inplace_* 알고리즘들은 추가 메모리 없이 제자리에서 동작
  • *_copy 알고리즘들은 원본을 변경하지 않고 결과를 다른 곳에 복사

최적화 팁

  1. 정렬된 데이터: binary_search, lower_bound, upper_bound 활용
  2. 부분 정렬: 전체가 아닌 일부만 필요하면 partial_sort, nth_element 사용
  3. 안정성 필요: stable_sort, stable_partition 사용
  4. 조건부 연산: *_if 버전들을 적극 활용
  5. 병렬 처리: C++17의 실행 정책 활용 가능

관련 헤더

  • <algorithm>: 대부분의 알고리즘
  • <numeric>: 수치 연산 알고리즘
  • <functional>: 함수 객체 (predicate 등)
  • <iterator>: 반복자 관련
  • <random>: 무작위 관련 (shuffle 등)

마지막 업데이트: 2025-06-24