1. 비수정 시퀀스 알고리즘
이 알고리즘들은 작업하는 컨테이너의 요소를 변경하지 않습니다.
1.1 find와 find_if
find(begin, end, value):value와 같은 첫 번째 요소를 찾아 반복자를 반환합니다. (찾지 못하면end반환)find_if(begin, end, predicate): 조건자(predicate)를 만족하는 첫 번째 요소를 찾습니다.find_end(begin, end, sub_begin, sub_end): 부분 시퀀스가 마지막으로 나타나는 위치를 찾습니다.
std::vector<int> data = {10, 20, 30, 40, 50};
// 값 30을 찾기
auto it = std::find(data.begin(), data.end(), 30);
if (it != data.end()) {
std::cout << "found: " << *it << std::endl; // 출력: 30
}
// 첫 번째 35보다 큰 요소 찾기
auto it2 = std::find_if(data.begin(), data.end(), [](int x) {
return x > 35;
});
std::cout << "first >35: " << *it2 << std::endl; // 출력: 40
// 부분 시퀀스 찾기
std::vector<int> pattern = {20, 30};
auto it3 = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (it3 != data.end()) {
std::cout << "subsequence starts at index: " << it3 - data.begin() << std::endl; // 출력: 1
}1.2 count와 count_if
count(begin, end, value):value와 같은 요소의 개수를 셉니다.count_if(begin, end, predicate): 조건자를 만족하는 요소의 개수를 셉니다.
std::vector<int> container = {5, 10, 15, 10, 20, 10};
int cnt = std::count(container.begin(), container.end(), 10); // 10의 개수, 결과는 3
int multiple_of_5_cnt = std::count_if(container.begin(), container.end(), [](int x) {
return x % 5 == 0;
}); // 5의 배수 개수, 결과는 61.3 for_each
범위 내의 각 요소에 함수를 적용합니다.
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::for_each(numbers.begin(), numbers.end(), [](int& x) {
x += 10; // 각 요소에 10을 더함
});
// 이제 numbers는 {11, 12, 13, 14, 15}1.4 equal과 mismatch
equal(b1, e1, b2): 두 범위[b1,e1)와[b2, b2+(e1-b1))가 같은지 판단합니다.mismatch(b1, e1, b2): 두 범위에서 첫 번째로 다른 요소의 반복자 쌍(pair)을 반환합니다.
std::vector<int> list1 = {1, 2, 3};
std::vector<int> list2 = {1, 2, 4};
std::vector<int> list3 = {1, 2, 3, 4};
// list1과 list2의 처음 3개 요소 비교
bool is_equal = std::equal(list1.begin(), list1.end(), list2.begin());
std::cout << "list1 == list2? " << std::boolalpha << is_equal << std::endl; // 출력: false
// list1과 list3의 첫 번째 불일치 요소 찾기
auto mis = std::mismatch(list1.begin(), list1.end(), list3.begin());
if (mis.first != list1.end()) {
std::cout << "mismatch: " << *mis.first << " vs " << *mis.second << std::endl; // 출력 없음 (list1과 list3의 앞 3개 요소는 같음)
}1.5 all_of, any_of, none_of
범위 내 요소가 모두, 일부, 또는 하나도 조건을 만족하는지 확인합니다.
std::vector<int> values = {2, 4, 6, 8};
bool all_even = std::all_of(values.begin(), values.end(), [](int x) {
return x % 2 == 0;
}); // true
bool any_odd = std::any_of(values.begin(), values.end(), [](int x) {
return x % 2 != 0;
}); // false
bool none_negative = std::none_of(values.begin(), values.end(), [](int x) {
return x < 0;
}); // true2. 수정 시퀀스 알고리즘
이 알고리즘들은 작업하는 컨테이너의 요소를 수정합니다.
2.1 copy와 copy_if
copy(begin, end, dest):[begin, end)의 요소를dest가 시작하는 위치로 복사합니다.copy_if(begin, end, dest, predicate): 조건자를 만족하는 요소를dest로 복사합니다.
std::vector<int> sourceData = {1, 2, 3, 4, 5};
std::vector<int> targetContainer(5); // 충분한 공간을 미리 할당해야 함
// 모든 요소 복사
std::copy(sourceData.begin(), sourceData.end(), targetContainer.begin()); // targetContainer: [1,2,3,4,5]
// 짝수 요소를 새 컨테이너로 복사
std::vector<int> evenNumbers;
std::copy_if(sourceData.begin(), sourceData.end(), std::back_inserter(evenNumbers), [](int x) {
return x % 2 == 0;
}); // evenNumbers: [2,4]참고: back_inserter(dest)는 push_back을 자동으로 호출하므로, 미리 공간을 할당할 필요가 없습니다.
2.2 transform
범위 내의 각 요소에 함수를 적용하고, 결과를 다른 범위에 저장합니다.
std::vector<int> inputData = {1, 2, 3};
std::vector<int> squaredData(3);
// 제곱 계산 (단일 인자 변환)
std::transform(inputData.begin(), inputData.end(), squaredData.begin(), [](int x) {
return x * x;
}); // squaredData: [1,4,9]
// 두 컨테이너 요소 더하기 (이중 인자 변환)
std::vector<int> listA = {10, 20, 30};
std::vector<int> listB = {1, 2, 3};
std::vector<int> resultList(3);
std::transform(listA.begin(), listA.end(), listB.begin(), resultList.begin(), [](int x, int y) {
return x + y;
}); // resultList: [11,22,33]2.3 replace, replace_if, replace_copy
replace(begin, end, old_val, new_val): 모든old_val을new_val로 교체합니다.replace_if(begin, end, predicate, new_val): 조건자를 만족하는 요소를 교체합니다.replace_copy(begin, end, dest, old_val, new_val): 복사하는 동안 요소를 교체합니다 (원본 컨테이너를 수정하지 않음).
std::vector<int> myData = {5, 10, 15, 10, 25};
// 모든 10을 100으로 교체
std::replace(myData.begin(), myData.end(), 10, 100); // myData: [5,100,15,100,25]
// 50보다 큰 요소를 0으로 교체
std::replace_if(myData.begin(), myData.end(), [](int x) {
return x > 50;
}, 0); // myData: [5,0,15,0,25]
// 복사하는 동안 15를 150으로 교체 (원본 컨테이너는 변경되지 않음)
std::vector<int> outputData;
std::replace_copy(myData.begin(), myData.end(), std::back_inserter(outputData), 15, 150); // outputData: [5,0,150,0,25]2.4 remove, remove_if, erase
remove(begin, end, value):value와 같은 요소를 "이동"하여 컨테이너의 끝으로 보냅니다. 새로운 논리적 끝 반복자를 반환합니다. (실제로 요소를 삭제하지 않으므로erase와 함께 사용해야 함)remove_if(begin, end, predicate): 조건자를 만족하는 요소를 끝으로 이동시킵니다.
std::vector<int> myVector = {5, 10, 15, 10, 20};
// 모든 10을 논리적으로 삭제 (끝으로 이동)
auto new_end = std::remove(myVector.begin(), myVector.end(), 10); // myVector: [5,15,20,10,10]
// 물리적 삭제 (실제로 요소 제거)
myVector.erase(new_end, myVector.end()); // myVector: [5,15,20]
// 람다와 결합하여 짝수 삭제
myVector = {5, 10, 15, 20, 25};
myVector.erase(std::remove_if(myVector.begin(), myVector.end(), [](int x) {
return x % 2 == 0;
}), myVector.end()); // myVector: [5,15,25]2.5 unique
범위 내에서 연속된 중복 요소를 제거하고, 새로운 논리적 끝 반복자를 반환합니다. 보통 erase와 함께 사용됩니다.
std::vector<int> myVector = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last = std::unique(myVector.begin(), myVector.end());
myVector.erase(last, myVector.end()); // myVector은 {1, 2, 3, 4, 5}이 됨2.6 reverse
범위 내의 요소 순서를 반전시킵니다.
std::vector<int> myVector = {1, 2, 3, 4, 5};
std::reverse(myVector.begin(), myVector.end()); // myVector은 {5, 4, 3, 2, 1}이 됨2.7 rotate
범위 내의 요소를 회전하여, 중간 요소가 새로운 첫 번째 요소가 되도록 합니다.
std::vector<int> myVector = {1, 2, 3, 4, 5};
std::rotate(myVector.begin(), myVector.begin() + 2, myVector.end()); // 3을 시작점으로 회전, myVector은 {3, 4, 5, 1, 2}이 됨2.8 shuffle
범위 내의 요소를 무작위로 재배열합니다 (C++11 이상 필요).
#include <random>
#include <algorithm>
std::vector<int> myVector = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 rng(rd());
std::shuffle(myVector.begin(), myVector.end(), rng); // myVector의 요소를 무작위로 섞음3. 정렬 및 관련 알고리즘
3.1 sort, stable_sort, partial_sort
sort(begin, end): 요소를 퀵 정렬합니다 (불안정, 평균 시간 복잡도 O(n log n)).stable_sort(begin, end): 안정 정렬 (같은 요소의 상대적 위치가 변하지 않음).partial_sort(begin, mid, end): 부분 정렬,[begin, mid)범위를 전체 범위에서 가장 작은 요소로 만들고 정렬합니다.
std::vector<int> myVector = {50, 30, 10, 40, 20};
std::sort(myVector.begin(), myVector.end()); // 기본 오름차순, myVector은 {10, 20, 30, 40, 50}
std::sort(myVector.begin(), myVector.end(), std::greater<int>()); // 내림차순, myVector은 {50, 40, 30, 20, 10}
std::sort(myVector.begin(), myVector.end(), [](int a, int b) {
return a < b;
}); // 오름차순, 사용자 정의 비교
std::vector> pairVector = {{2, 1}, {1, 2}, {2, 2}, {1, 1}};
std::stable_sort(pairVector.begin(), pairVector.end(), [](const auto& a, const auto& b) {
return a.first < b.first; // first 기준 정렬, 같은 요소의 상대적 순서 유지
});
std::vector<int> myVector2 = {50, 30, 10, 40, 20, 60};
// 가장 작은 3개의 요소를 앞에 놓고 정렬
std::partial_sort(myVector2.begin(), myVector2.begin() + 3, myVector2.end());
// 이제 myVector2의 앞 3개 요소는 10, 20, 30이고, 뒤는 정렬되지 않은 40, 50, 60 3.2 nth_element
범위를 재배열하여, 지정된 위치의 요소가 정렬된 요소와 같게 하고, 왼쪽 요소는 모두 그보다 작거나 같고, 오른쪽 요소는 모두 그보다 크거나 같게 합니다.
std::vector<int> myVector = {50, 30, 10, 40, 20, 60};
// 세 번째로 작은 요소(인덱스 2) 찾기
std::nth_element(myVector.begin(), myVector.begin() + 2, myVector.end());
// 이제 myVector[2]는 30이고, 왼쪽 요소는 <=30, 오른쪽은 >=303.3 binary_search, lower_bound, upper_bound
정렬된 컨테이너에서 사용해야 합니다.
binary_search(begin, end, value):value가 존재하는지 판단합니다 (bool 반환).lower_bound(begin, end, value):value보다 작지 않은 첫 번째 요소의 반복자를 반환합니다.upper_bound(begin, end, value):value보다 큰 첫 번째 요소의 반복자를 반환합니다.
std::vector<int> sortedData = {10, 30, 30, 50, 70}; // 먼저 정렬해야 함
// 30이 존재하는지 확인
bool exists = std::binary_search(sortedData.begin(), sortedData.end(), 30); // true
// 첫 번째 >=30인 요소 찾기
auto lb = std::lower_bound(sortedData.begin(), sortedData.end(), 30);
std::cout << "lower_bound index: " << lb - sortedData.begin() << std::endl; // 출력: 1
// 첫 번째 >30인 요소 찾기
auto ub = std::upper_bound(sortedData.begin(), sortedData.end(), 30);
std::cout << "upper_bound index: " << ub - sortedData.begin() << std::endl; // 출력: 33.4 merge
두 개의 정렬된 범위를 새 컨테이너로 합병합니다 (정렬을 유지).
std::vector<int> firstList = {10, 30, 50};
std::vector<int> secondList = {20, 40, 60};
std::vector<int> combinedList(firstList.size() + secondList.size());
// firstList와 secondList를 합병 (둘 다 정렬되어 있어야 함)
std::merge(firstList.begin(), firstList.end(), secondList.begin(), secondList.end(), combinedList.begin()); // combinedList: [10,20,30,40,50,60]4. 힙 알고리즘
STL은 범위를 힙으로 처리하는 알고리즘을 제공하며, make_heap, push_heap, pop_heap, sort_heap 등이 포함됩니다.
std::vector<int> myHeap = {40, 10, 30, 20, 50};
std::make_heap(myHeap.begin(), myHeap.end()); // 최대 힙 구성, myHeap은 {50, 40, 30, 20, 10}
myHeap.push_back(60);
std::push_heap(myHeap.begin(), myHeap.end()); // 새 요소를 힙에 추가, myHeap은 {60, 40, 30, 20, 10, 50}
std::pop_heap(myHeap.begin(), myHeap.end()); // 최대 요소를 끝으로 이동, myHeap은 {50, 40, 30, 20, 10, 60}
int max_val = myHeap.back(); // 최대 요소 60 가져오기
myHeap.pop_back(); // 최대 요소 제거
std::sort_heap(myHeap.begin(), myHeap.end()); // 힙을 오름차순 시퀀스로 정렬, myHeap은 {10, 20, 30, 40, 50}5. 최소/최대값 알고리즘
5.1 min과 max
두 값 또는 초기화 리스트에서의 최소/최대값을 반환합니다.
int x = 50, y = 30;
int min_val = std::min(x, y); // 30
int max_val = std::max(x, y); // 50
auto min_of_list = std::min({40, 20, 80, 50, 10}); // 10
auto max_of_list = std::max({40, 20, 80, 50, 10}); // 805.2 min_element와 max_element
범위 내의 최소/최대 요소의 반복자를 반환합니다.
std::vector<int> myContainer = {30, 10, 40, 20, 50};
auto min_it = std::min_element(myContainer.begin(), myContainer.end()); // 10을 가리킴
auto max_it = std::max_element(myContainer.begin(), myContainer.end()); // 50을 가리킴5.3 minmax_element (C++11)
범위 내의 최소와 최대 요소의 반복자를 동시에 반환합니다.
std::vector<int> myContainer = {30, 10, 40, 20, 50};
auto minmax = std::minmax_element(myContainer.begin(), myContainer.end());
// minmax.first는 10을, minmax.second는 50을 가리킴6. 수치 알고리즘 (<numeric>에서)
6.1 accumulate
범위 내 요소의 누적 합계를 계산합니다 (또는 사용자 정의 연산).
#include <numeric>
std::vector<int> myNumbers = {1, 2, 3, 4, 5};
int sum = std::accumulate(myNumbers.begin(), myNumbers.end(), 0); // 합계, 초기값 0, 결과 15
int product = std::accumulate(myNumbers.begin(), myNumbers.end(), 1, std::multiplies<int>()); // 곱셈, 초기값 1, 결과 1206.2 inner_product
두 범위의 내적을 계산합니다 (또는 사용자 정의 연산).
std::vector<int> vectorA = {1, 2, 3};
std::vector<int> vectorB = {4, 5, 6};
int dot = std::inner_product(vectorA.begin(), vectorA.end(), vectorB.begin(), 0); // 1*4 + 2*5 + 3*6 = 326.3 iota
연속적으로 증가하는 값으로 범위를 채웁니다.
std::vector<int> mySequence(5);
std::iota(mySequence.begin(), mySequence.end(), 100); // 100, 101, 102, 103, 104로 채움6.4 partial_sum
부분 합계를 계산하고 결과를 대상 범위에 저장합니다.
std::vector<int> sourceData = {1, 2, 3, 4, 5};
std::vector<int> partialSums(sourceData.size());
std::partial_sum(sourceData.begin(), sourceData.end(), partialSums.begin()); // partialSums는 {1, 3, 6, 10, 15}6.5 adjacent_difference
인접 요소의 차이를 계산하고 결과를 대상 범위에 저장합니다.
std::vector<int> sourceData = {1, 2, 3, 4, 5};
std::vector<int> differences(sourceData.size());
std::adjacent_difference(sourceData.begin(), sourceData.end(), differences.begin()); // differences는 {1, 1, 1, 1, 1}7. 기타 알고리즘
7.1 generate
생성 함수로 범위를 채웁니다.
std::vector<int> myVector(5);
int counter = 0;
std::generate(myVector.begin(), myVector.end(), [&counter]() {
return counter++;
}); // 0, 1, 2, 3, 4로 채움7.2 generate_n
생성 함수로 범위의 시작 n개 요소를 채웁니다.
std::vector<int> myVector(5);
int start = 100;
std::generate_n(myVector.begin(), 3, [&start]() {
return start++;
}); // 앞 3개 요소는 100, 101, 102, 뒤 2개는 변경되지 않음7.3 includes
정렬된 범위가 다른 정렬된 범위의 모든 요소를 포함하는지 확인합니다.
std::vector<int> mainSet = {1, 2, 3, 4, 5};
std::vector<int> subset = {2, 4};
bool includes = std::includes(mainSet.begin(), mainSet.end(), subset.begin(), subset.end()); // true7.4 set_union, set_intersection, set_difference, set_symmetric_difference
집합 연산을 수행합니다: 합집합, 교집합, 차집합, 대칭 차집합.
std::vector<int> setA = {1, 2, 3, 4, 5};
std::vector<int> setB = {3, 4, 5, 6, 7};
std::vector<int> outputSet;
// 합집합
std::set_union(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(outputSet));
// outputSet는 {1, 2, 3, 4, 5, 6, 7}
// 교집합
outputSet.clear();
std::set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(outputSet));
// outputSet는 {3, 4, 5}
// 차집합 (setA - setB)
outputSet.clear();
std::set_difference(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(outputSet));
// outputSet는 {1, 2}
// 대칭 차집합 (setA ∪ setB - setA ∩ setB)
outputSet.clear();
std::set_symmetric_difference(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(outputSet));
// outputSet는 {1, 2, 6, 7}8. 자주 묻는 질문
- sort와 stable_sort의 차이점은 무엇인가요?
-sort는 퀵 정렬(실제로는 introsort 알고리즘)을 사용하며, 불안정합니다 (같은 요소의 상대적 위치가 변경될 수 있음). 평균 시간 복잡도는 O(n log n)입니다.
-stable_sort는 병합 정렬을 사용하며, 안정적입니다 (같은 요소의 상대적 위치가 유지됨). 시간 복잡도는 O(n log n)이지만, 공간 오버헤드가 약간 더 큽니다. - 왜 remove 알고리즘은 erase와 함께 사용해야 하나요?
remove알고리즘의 원리는 삭제할 요소를 "덮어쓰는" 방식으로, 보존할 요소를 앞으로 이동시키고 새로운 논리적 끝 반복자를 반환하지만, 컨테이너의 실제 크기를 수정하지 않습니다.erase는 반복자 범위를 통해 실제로 요소를 삭제하고 컨테이너 크기를 수정합니다. 따라서container.erase(remove(...), container.end())와 같이 결합하여 사용해야 합니다. - 어떤 알고리즘은 컨테이너가 정렬되어 있어야 하나요?
이진 탐색 계열(binary_search,lower_bound,upper_bound), 집합 알고리즘(set_intersection,set_union등),merge등이 있습니다. 이 알고리즘들은 정렬된 상태를 이용하여 효율적인 작업(예: 이진 탐색 O(log n))을 수행합니다.