1. 비수정(Non-modifying) 시퀀스 알고리즘
이 범주의 알고리즘은 대상 컨테이너의 요소 값을 변경하지 않으면서 정보를 검색합니다.
1.1 요소 찾기: find, find_if, find_end
find(begin, end, value): 주어진 범위에서 특정 값과 일치하는 첫 번째 요소를 찾아 해당 위치의 이터레이터를 반환합니다. 찾지 못하면end이터레이터를 반환합니다.find_if(begin, end, predicate): 특정 조건을 만족하는(즉,predicate가true를 반환하는) 첫 번째 요소를 찾습니다.find_end(begin, end, sub_begin, sub_end): 주어진 범위 내에서 특정 하위 시퀀스가 마지막으로 나타나는 위치를 찾습니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric> // for std::iota if needed
int main() {
std::vector<int> my_numbers = {10, 20, 30, 40, 50, 20, 60};
// 1. 특정 값(30) 찾기
auto iter_val = std::find(my_numbers.begin(), my_numbers.end(), 30);
if (iter_val != my_numbers.end()) {
std::cout << "값 30 발견: " << *iter_val << std::endl; // 출력: 값 30 발견: 30
}
// 2. 특정 조건(30보다 큰 값)을 만족하는 첫 번째 요소 찾기
auto iter_pred = std::find_if(my_numbers.begin(), my_numbers.end(), [](int n) {
return n > 30;
});
if (iter_pred != my_numbers.end()) {
std::cout << "30보다 큰 첫 번째 값: " << *iter_pred << std::endl; // 출력: 30보다 큰 첫 번째 값: 40
}
// 3. 하위 시퀀스 {20, 60}의 마지막 발생 위치 찾기
std::vector<int> sub_sequence = {20, 60};
auto iter_sub = std::find_end(my_numbers.begin(), my_numbers.end(),
sub_sequence.begin(), sub_sequence.end());
if (iter_sub != my_numbers.end()) {
std::cout << "하위 시퀀스 {20, 60}은 인덱스 " << std::distance(my_numbers.begin(), iter_sub)
<< "에서 시작합니다." << std::endl; // 출력: 하위 시퀀스 {20, 60}은 인덱스 5에서 시작합니다.
}
return 0;
}
1.2 요소 개수 세기: count, count_if
count(begin, end, value): 범위 내에서 특정 값과 일치하는 요소의 총 개수를 반환합니다.count_if(begin, end, predicate): 특정 조건(predicate)을 만족하는 요소의 개수를 반환합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> data_list = {1, 2, 2, 3, 4, 2, 5};
// 값 2의 개수 세기
int two_count = std::count(data_list.begin(), data_list.end(), 2);
std::cout << "값 2의 개수: " << two_count << std::endl; // 출력: 값 2의 개수: 3
// 짝수의 개수 세기
int even_count = std::count_if(data_list.begin(), data_list.end(), [](int x) {
return x % 2 == 0;
});
std::cout << "짝수의 개수: " << even_count << std::endl; // 출력: 짝수의 개수: 4
return 0;
}
1.3 각 요소에 함수 적용: for_each
지정된 범위의 각 요소에 대해 주어진 함수 객체(또는 람다)를 한 번씩 호출합니다. 이 함수는 원래 컨테이너의 요소를 변경할 수도 있습니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> value_set = {10, 20, 30, 40};
// 각 요소를 2배로 만듭니다.
std::for_each(value_set.begin(), value_set.end(), [](int& val) {
val *= 2;
});
std::cout << "2배로 변환된 값: ";
for (int v : value_set) {
std::cout << v << " "; // 출력: 20 40 60 80
}
std::cout << std::endl;
return 0;
}
1.4 범위 비교: equal, mismatch
equal(b1, e1, b2): 두 범위가 동일한지 여부를 확인합니다. 두 번째 범위는 첫 번째 범위의 길이만큼 비교됩니다.mismatch(b1, e1, b2): 두 범위에서 처음으로 서로 다른 요소의 이터레이터 쌍(std::pair)을 반환합니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip> // for std::boolalpha
int main() {
std::vector<int> seq1 = {1, 2, 3, 4};
std::vector<int> seq2 = {1, 2, 3, 5};
std::vector<int> seq3 = {1, 2, 3};
// seq1과 seq2가 동일한지 비교
bool are_equal = std::equal(seq1.begin(), seq1.end(), seq2.begin());
std::cout << "seq1과 seq2는 동일한가? " << std::boolalpha << are_equal << std::endl; // 출력: false
// seq1과 seq3의 불일치 지점 찾기 (seq3이 더 짧음)
auto diff_point = std::mismatch(seq1.begin(), seq1.end(), seq3.begin());
if (diff_point.first != seq1.end()) {
std::cout << "seq1과 seq3의 첫 불일치: " << *diff_point.first
<< " vs (seq3 끝)" << std::endl; // 출력: seq1과 seq3의 첫 불일치: 4 vs (seq3 끝)
}
// seq1과 seq2의 불일치 지점 찾기
auto diff_point_2 = std::mismatch(seq1.begin(), seq1.end(), seq2.begin());
if (diff_point_2.first != seq1.end()) {
std::cout << "seq1과 seq2의 첫 불일치: " << *diff_point_2.first
<< " vs " << *diff_point_2.second << std::endl; // 출력: seq1과 seq2의 첫 불일치: 4 vs 5
}
return 0;
}
1.5 조건 만족 여부 확인: all_of, any_of, none_of (C++11)
주어진 범위의 모든/일부/아무 요소도 특정 조건을 만족하는지 확인합니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
int main() {
std::vector<int> numbers_set = {2, 4, 6, 8};
// 모든 요소가 짝수인가?
bool are_all_even = std::all_of(numbers_set.begin(), numbers_set.end(), [](int x) {
return x % 2 == 0;
});
std::cout << "모든 요소가 짝수인가? " << std::boolalpha << are_all_even << std::endl; // 출력: true
// 홀수가 하나라도 있는가?
bool is_any_odd = std::any_of(numbers_set.begin(), numbers_set.end(), [](int x) {
return x % 2 != 0;
});
std::cout << "홀수가 하나라도 있는가? " << std::boolalpha << is_any_odd << std::endl; // 출력: false
// 음수가 하나도 없는가?
bool no_negatives = std::none_of(numbers_set.begin(), numbers_set.end(), [](int x) {
return x < 0;
});
std::cout << "음수가 하나도 없는가? " << std::boolalpha << no_negatives << std::endl; // 출력: true
return 0;
}
2. 수정(Modifying) 시퀀스 알고리즘
이 알고리즘들은 컨테이너 내의 요소를 직접 수정합니다.
2.1 요소 복사: copy, copy_if
copy(begin, end, dest): 한 범위의 요소를 다른 목적지 범위로 복사합니다.copy_if(begin, end, dest, predicate): 특정 조건을 만족하는 요소만 목적지로 복사합니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // For std::back_inserter
int main() {
std::vector<int> source_data = {10, 20, 30, 40, 50};
std::vector<int> destination_data(source_data.size()); // 충분한 공간을 미리 할당해야 함
// 모든 요소 복사
std::copy(source_data.begin(), source_data.end(), destination_data.begin());
std::cout << "모두 복사: ";
for (int val : destination_data) {
std::cout << val << " "; // 출력: 10 20 30 40 50
}
std::cout << std::endl;
// 짝수만 새 컨테이너로 복사
std::vector<int> even_numbers;
// std::back_inserter는 자동으로 push_back을 호출하므로, 목적지 컨테이너의 크기를 미리 지정할 필요가 없습니다.
std::copy_if(source_data.begin(), source_data.end(),
std::back_inserter(even_numbers), [](int x) {
return x % 2 == 0;
});
std::cout << "짝수만 복사: ";
for (int val : even_numbers) {
std::cout << val << " "; // 출력: 10 20 30 40 50
}
std::cout << std::endl;
return 0;
}
2.2 요소 변환: transform
주어진 범위의 각 요소에 함수를 적용하고 결과를 다른 범위에 저장합니다. 단항 또는 이항 연산을 수행할 수 있습니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional> // For std::plus, std::multiplies (not used in example, but good for context)
int main() {
std::vector<int> original_values = {1, 2, 3, 4};
std::vector<int> transformed_values(original_values.size());
// 각 요소를 제곱하여 저장 (단항 변환)
std::transform(original_values.begin(), original_values.end(),
transformed_values.begin(), [](int x) {
return x * x;
});
std::cout << "제곱 값: ";
for (int val : transformed_values) {
std::cout << val << " "; // 출력: 1 4 9 16
}
std::cout << std::endl;
// 두 벡터의 요소들을 더하여 저장 (이항 변환)
std::vector<int> vec_a = {10, 20, 30};
std::vector<int> vec_b = {1, 2, 3};
std::vector<int> sum_result(vec_a.size());
std::transform(vec_a.begin(), vec_a.end(), vec_b.begin(), sum_result.begin(),
[](int x, int y) {
return x + y;
});
std::cout << "두 벡터 합: ";
for (int val : sum_result) {
std::cout << val << " "; // 출력: 11 22 33
}
std::cout << std::endl;
return 0;
}
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): 특정 조건을 만족하는 요소를new_val로 교체합니다.replace_copy(begin, end, dest, old_val, new_val): 원본 컨테이너를 변경하지 않고 복사하면서 요소를 교체합니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // For std::back_inserter
int main() {
std::vector<int> my_elements = {1, 5, 2, 5, 3, 5, 4};
// 값 5를 99로 교체
std::replace(my_elements.begin(), my_elements.end(), 5, 99);
std::cout << "값 5를 99로 교체: ";
for (int val : my_elements) {
std::cout << val << " "; // 출력: 1 99 2 99 3 99 4
}
std::cout << std::endl;
// 90보다 큰 요소를 0으로 교체
std::replace_if(my_elements.begin(), my_elements.end(), [](int x) {
return x > 90;
}, 0);
std::cout << "90 초과를 0으로 교체: ";
for (int val : my_elements) {
std::cout << val << " "; // 출력: 1 0 2 0 3 0 4
}
std::cout << std::endl;
// 복사하면서 값 0을 100으로 교체 (원본은 변경 안됨)
std::vector<int> replaced_copy_vec;
std::replace_copy(my_elements.begin(), my_elements.end(),
std::back_inserter(replaced_copy_vec), 0, 100);
std::cout << "복사 후 0을 100으로 교체: ";
for (int val : replaced_copy_vec) {
std::cout << val << " "; // 출력: 1 100 2 100 3 100 4
}
std::cout << std::endl;
std::cout << "원본 벡터: ";
for (int val : my_elements) {
std::cout << val << " "; // 출력: 1 0 2 0 3 0 4 (원본은 그대로)
}
std::cout << std::endl;
return 0;
}
2.4 요소 제거: remove, remove_if, erase
remove와 remove_if는 컨테이너의 물리적 크기를 변경하지 않고, 삭제될 요소를 범위의 끝으로 "이동"시키고 새 논리적 끝 이터레이터를 반환합니다. 실제 요소 제거는 erase 멤버 함수와 결합하여 수행해야 합니다.
remove(begin, end, value): 특정 값과 일치하는 모든 요소를 논리적으로 제거합니다.remove_if(begin, end, predicate): 특정 조건을 만족하는 모든 요소를 논리적으로 제거합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> item_list = {10, 20, 30, 20, 40, 50, 20};
// 값 20을 논리적으로 제거
auto new_logical_end = std::remove(item_list.begin(), item_list.end(), 20);
// 현재 item_list는 {10, 30, 40, 50, 40, 50, 20} (정확한 내용은 구현마다 다를 수 있음), 실제 크기는 그대로
std::cout << "remove 후 (논리적 끝까지): ";
for (auto it = item_list.begin(); it != new_logical_end; ++it) {
std::cout << *it << " "; // 출력: 10 30 40 50
}
std::cout << std::endl;
// 실제 요소 제거 (erase-remove 이디엄)
item_list.erase(new_logical_end, item_list.end());
std::cout << "erase 후: ";
for (int val : item_list) {
std::cout << val << " "; // 출력: 10 30 40 50
}
std::cout << std::endl;
// 짝수를 제거하는 예시 (다시 초기화)
item_list = {1, 2, 3, 4, 5, 6};
item_list.erase(std::remove_if(item_list.begin(), item_list.end(), [](int x) {
return x % 2 == 0;
}), item_list.end());
std::cout << "짝수 제거 후: ";
for (int val : item_list) {
std::cout << val << " "; // 출력: 1 3 5
}
std::cout << std::endl;
return 0;
}
2.5 중복 요소 제거: unique
인접한 중복 요소를 제거합니다. `remove`와 마찬가지로 논리적으로만 제거하며, `erase`와 함께 사용해야 합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> dup_vec = {1, 1, 2, 2, 2, 3, 4, 4, 5};
// 인접한 중복 제거 (논리적)
auto new_end_unique = std::unique(dup_vec.begin(), dup_vec.end());
// dup_vec 내용은 {1, 2, 3, 4, 5, 4, 4, 4, 5} (정확한 내용은 구현마다 다를 수 있음)
// 실제 중복 요소 제거
dup_vec.erase(new_end_unique, dup_vec.end());
std::cout << "unique 후: ";
for (int val : dup_vec) {
std::cout << val << " "; // 출력: 1 2 3 4 5
}
std::cout << std::endl;
return 0;
}
2.6 순서 반전: reverse
지정된 범위의 요소 순서를 역순으로 변경합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> original_order = {10, 20, 30, 40, 50};
std::reverse(original_order.begin(), original_order.end());
std::cout << "역순으로 변경: ";
for (int val : original_order) {
std::cout << val << " "; // 출력: 50 40 30 20 10
}
std::cout << std::endl;
return 0;
}
2.7 요소 회전: rotate
범위의 요소를 회전시켜 특정 요소가 새로운 시작 위치가 되도록 합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> my_data = {1, 2, 3, 4, 5, 6};
// 3(인덱스 2)을 새로운 시작점으로 회전
std::rotate(my_data.begin(), my_data.begin() + 2, my_data.end());
std::cout << "회전 후: ";
for (int val : my_data) {
std::cout << val << " "; // 출력: 3 4 5 6 1 2
}
std::cout << std::endl;
return 0;
}
2.8 요소 무작위 재배치: shuffle (C++11)
지정된 범위의 요소들을 무작위로 섞습니다. 난수 생성 엔진이 필요합니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <random> // For std::random_device, std::mt19937
int main() {
std::vector<int> cards = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::random_device rd; // 하드웨어 기반 난수 생성기 (seed)
std::mt19937 g(rd()); // 메르센 트위스터 엔진 초기화
std::shuffle(cards.begin(), cards.end(), g); // 카드 섞기
std::cout << "섞인 카드: ";
for (int card : cards) {
std::cout << card << " "; // 매 실행마다 다른 순서로 출력
}
std::cout << std::endl;
return 0;
}
3. 정렬 및 관련 알고리즘
데이터의 순서를 정렬하거나 정렬된 데이터에서 효율적으로 정보를 찾습니다.
3.1 정렬: sort, stable_sort, partial_sort
sort(begin, end): 요소를 정렬합니다. 빠르지만 안정적이지 않을 수 있습니다 (동일한 요소의 상대적 순서가 변경될 수 있음). 일반적으로 인트로소트(Introsort)를 사용합니다.stable_sort(begin, end): 요소를 정렬합니다. 동일한 요소의 상대적 순서를 보존하는 안정적인 정렬입니다. 일반적으로 병합 정렬(Merge Sort)을 사용합니다.partial_sort(begin, middle, end): 범위의 시작 부분에 가장 작은(middle - begin)개의 요소를 정렬된 상태로 배치합니다. 나머지 요소는 정렬되지 않습니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional> // For std::greater
int main() {
std::vector<int> my_scores = {85, 30, 95, 40, 70, 50};
// 1. 기본 오름차순 정렬
std::sort(my_scores.begin(), my_scores.end());
std::cout << "오름차순 정렬: ";
for (int score : my_scores) {
std::cout << score << " "; // 출력: 30 40 50 70 85 95
}
std::cout << std::endl;
// 2. 내림차순 정렬 (std::greater 사용)
std::sort(my_scores.begin(), my_scores.end(), std::greater<int>());
std::cout << "내림차순 정렬: ";
for (int score : my_scores) {
std::cout << score << " "; // 출력: 95 85 70 50 40 30
}
std::cout << std::endl;
// 3. 사용자 정의 람다 비교자(comparator)로 오름차순 정렬
my_scores = {85, 30, 95, 40, 70, 50}; // 다시 초기화
std::sort(my_scores.begin(), my_scores.end(), [](int a, int b) {
return a < b; // a가 b보다 작으면 true (오름차순)
});
std::cout << "람다로 오름차순 정렬: ";
for (int score : my_scores) {
std::cout << score << " "; // 출력: 30 40 50 70 85 95
}
std::cout << std::endl;
// 4. stable_sort 예시 (std::pair를 사용하여 안정성 확인)
std::vector<std::pair<int, int>> student_data = {{5, 1}, {2, 2}, {5, 3}, {1, 4}, {2, 5}};
// first 값을 기준으로 정렬, first 값이 같으면 second 값의 원래 순서 유지
std::stable_sort(student_data.begin(), student_data.end(), [](const auto& a, const auto& b) {
return a.first < b.first;
});
std::cout << "Stable Sort (first 기준): ";
for (const auto& p : student_data) {
std::cout << "(" << p.first << "," << p.second << ") "; // 출력: (1,4) (2,2) (2,5) (5,1) (5,3)
}
std::cout << std::endl;
// 5. partial_sort 예시
std::vector<int> mixed_nums = {9, 1, 8, 2, 7, 3, 6, 4, 5};
// 가장 작은 4개의 요소를 정렬하여 앞에 배치
std::partial_sort(mixed_nums.begin(), mixed_nums.begin() + 4, mixed_nums.end());
std::cout << "Partial Sort (앞 4개 정렬): ";
for (int num : mixed_nums) {
std::cout << num << " "; // 출력: 1 2 3 4 7 9 8 6 5 (앞 4개는 정렬, 나머지는 그대로)
}
std::cout << std::endl;
return 0;
}
3.2 특정 위치 요소 정렬: nth_element
주어진 범위에서 `nth` 위치의 요소가 만약 전체가 정렬되었을 때 그 위치에 있어야 할 값과 동일하도록 재배열합니다. `nth` 위치의 왼쪽에 있는 요소들은 그 값보다 작거나 같고, 오른쪽에 있는 요소들은 그 값보다 크거나 같습니다. (완전히 정렬된 것은 아님)
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> unsorted_data = {50, 30, 10, 40, 20, 60};
// 세 번째로 작은 요소(인덱스 2)를 찾고 해당 위치에 배치
std::nth_element(unsorted_data.begin(), unsorted_data.begin() + 2, unsorted_data.end());
std::cout << "nth_element 후: ";
for (int val : unsorted_data) {
std::cout << val << " ";
}
std::cout << std::endl;
// 출력 예시: 20 10 30 50 40 60 (인덱스 2의 30이 정렬되면 3번째로 작은 값이고, 왼쪽은 30보다 작거나 같고, 오른쪽은 30보다 크거나 같음)
return 0;
}
3.3 이진 검색: binary_search, lower_bound, upper_bound
이 알고리즘들은 반드시 정렬된 범위에 적용해야 합니다.
binary_search(begin, end, value): 특정 값이 범위 내에 존재하는지 여부를 불리언 값으로 반환합니다.lower_bound(begin, end, value): 주어진 값보다 작지 않은(즉, 크거나 같은) 첫 번째 요소의 이터레이터를 반환합니다.upper_bound(begin, end, value): 주어진 값보다 큰 첫 번째 요소의 이터레이터를 반환합니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
int main() {
std::vector<int> sorted_list = {10, 20, 30, 30, 40, 50, 60}; // 정렬 필수!
// 1. 값 30이 존재하는지 확인
bool found_30 = std::binary_search(sorted_list.begin(), sorted_list.end(), 30);
std::cout << "값 30 존재 여부: " << std::boolalpha << found_30 << std::endl; // 출력: true
// 2. 값 35가 존재하는지 확인
bool found_35 = std::binary_search(sorted_list.begin(), sorted_list.end(), 35);
std::cout << "값 35 존재 여부: " << std::boolalpha << found_35 << std::endl; // 출력: false
// 3. 30보다 크거나 같은 첫 번째 요소 찾기
auto lb_iter = std::lower_bound(sorted_list.begin(), sorted_list.end(), 30);
std::cout << "lower_bound (30): " << *lb_iter
<< ", 인덱스: " << std::distance(sorted_list.begin(), lb_iter) << std::endl; // 출력: 30, 인덱스: 2
// 4. 30보다 큰 첫 번째 요소 찾기
auto ub_iter = std::upper_bound(sorted_list.begin(), sorted_list.end(), 30);
std::cout << "upper_bound (30): " << *ub_iter
<< ", 인덱스: " << std::distance(sorted_list.begin(), ub_iter) << std::endl; // 출력: 40, 인덱스: 4
// 5. 35보다 크거나 같은 첫 번째 요소 찾기
auto lb_iter_35 = std::lower_bound(sorted_list.begin(), sorted_list.end(), 35);
std::cout << "lower_bound (35): " << *lb_iter_35
<< ", 인덱스: " << std::distance(sorted_list.begin(), lb_iter_35) << std::endl; // 출력: 40, 인덱스: 4
return 0;
}
3.4 정렬된 범위 병합: merge
두 개의 정렬된 범위의 요소들을 하나의 새로운 정렬된 범위로 병합합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> list_a = {1, 3, 5, 7};
std::vector<int> list_b = {2, 4, 6, 8};
std::vector<int> merged_list(list_a.size() + list_b.size());
// 두 정렬된 리스트 병합
std::merge(list_a.begin(), list_a.end(),
list_b.begin(), list_b.end(),
merged_list.begin());
std::cout << "병합된 리스트: ";
for (int val : merged_list) {
std::cout << val << " "; // 출력: 1 2 3 4 5 6 7 8
}
std::cout << std::endl;
return 0;
}
4. 힙 알고리즘
STL은 컨테이너를 이진 힙 구조로 관리하는 알고리즘을 제공합니다. 힙은 우선순위 큐 구현에 주로 사용됩니다.
make_heap(begin, end): 지정된 범위의 요소를 최대 힙(max-heap)으로 구성합니다.push_heap(begin, end): 범위의 마지막 요소를 힙에 추가합니다 (push_back후 호출).pop_heap(begin, end): 힙에서 가장 큰 요소(루트)를 제거하고 범위의 끝으로 이동시킵니다 (실제 제거는pop_back으로).sort_heap(begin, end): 힙을 정렬된 순서로 변환합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> heap_data = {40, 10, 30, 20, 50};
// 1. 벡터를 최대 힙으로 변환
std::make_heap(heap_data.begin(), heap_data.end());
std::cout << "Make Heap 후 (루트가 가장 큼): ";
for (int val : heap_data) {
std::cout << val << " "; // 출력 예시: 50 40 30 20 10
}
std::cout << std::endl;
// 2. 새 요소(60)를 추가하고 힙 속성 유지
heap_data.push_back(60); // 먼저 요소를 벡터 끝에 추가
std::push_heap(heap_data.begin(), heap_data.end()); // 힙 속성 재정렬
std::cout << "Push Heap (60 추가) 후: ";
for (int val : heap_data) {
std::cout << val << " "; // 출력 예시: 60 40 50 20 10 30
}
std::cout << std::endl;
// 3. 가장 큰 요소(루트)를 추출 (논리적으로 제거)
std::pop_heap(heap_data.begin(), heap_data.end()); // 가장 큰 요소를 끝으로 이동하고 힙 재정렬
int max_value = heap_data.back(); // 끝으로 이동한 요소 접근
heap_data.pop_back(); // 실제 벡터에서 제거
std::cout << "Pop Heap (최대값 " << max_value << " 추출) 후: ";
for (int val : heap_data) {
std::cout << val << " "; // 출력 예시: 50 40 30 20 10
}
std::cout << std::endl;
// 4. 힙을 정렬된 순서로 변환
std::sort_heap(heap_data.begin(), heap_data.end());
std::cout << "Sort Heap 후: ";
for (int val : heap_data) {
std::cout << val << " "; // 출력: 10 20 30 40 50
}
std::cout << std::endl;
return 0;
}
5. 최소/최대값 알고리즘
단일 값 또는 범위에서 최소/최대 값을 찾습니다.
5.1 두 값 또는 초기화 리스트의 최소/최대: min, max
#include <algorithm>
#include <iostream>
#include <vector> // For initializer_list used with min/max
int main() {
int num1 = 15, num2 = 7;
int min_of_two = std::min(num1, num2);
int max_of_two = std::max(num1, num2);
std::cout << "두 값 중 최소: " << min_of_two << ", 최대: " << max_of_two << std::endl; // 출력: 7, 15
// 초기화 리스트에서 최소/최대 (C++11)
int min_in_list = std::min({5, 1, 9, 3, 7});
int max_in_list = std::max({5, 1, 9, 3, 7});
std::cout << "리스트 중 최소: " << min_in_list << ", 최대: " << max_in_list << std::endl; // 출력: 1, 9
return 0;
}
5.2 범위 내 최소/최대 요소의 이터레이터: min_element, max_element
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> data_values = {33, 11, 44, 22, 55};
auto min_it = std::min_element(data_values.begin(), data_values.end());
auto max_it = std::max_element(data_values.begin(), data_values.end());
std::cout << "최소 요소: " << *min_it << std::endl; // 출력: 11
std::cout << "최대 요소: " << *max_it << std::endl; // 출력: 55
return 0;
}
5.3 범위 내 최소/최대 요소 동시 찾기: minmax_element (C++11)
한 번의 순회로 범위 내의 최소 및 최대 요소 이터레이터를 std::pair로 반환합니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> number_set = {30, 10, 40, 20, 50};
auto minmax_pair = std::minmax_element(number_set.begin(), number_set.end());
std::cout << "최소 요소: " << *minmax_pair.first << std::endl; // 출력: 10
std::cout << "최대 요소: " << *minmax_pair.second << std::endl; // 출력: 50
return 0;
}
6. 수치(Numeric) 알고리즘 (<numeric> 헤더)
이 알고리즘들은 주로 수학적 연산을 수행합니다.
6.1 누적 합계 계산: accumulate
범위 내의 요소들을 지정된 초기값부터 누적하여 합계 또는 다른 연산을 수행합니다.
#include <vector>
#include <numeric> // For std::accumulate
#include <iostream>
#include <functional> // For std::multiplies
int main() {
std::vector<int> data_seq = {1, 2, 3, 4, 5};
// 초기값 0으로 합계 계산
int total_sum = std::accumulate(data_seq.begin(), data_seq.end(), 0);
std::cout << "총 합계: " << total_sum << std::endl; // 출력: 15
// 초기값 1로 곱셈 누적 (팩토리얼과 유사)
int total_product = std::accumulate(data_seq.begin(), data_seq.end(), 1, std::multiplies<int>());
std::cout << "총 곱셈: " << total_product << std::endl; // 출력: 120 (1*2*3*4*5)
return 0;
}
6.2 내적 계산: inner_product
두 범위의 내적(dot product)을 계산하거나 사용자 정의 이항 연산을 수행합니다.
#include <vector>
#include <numeric> // For std::inner_product
#include <iostream>
int main() {
std::vector<int> vec_x = {1, 2, 3};
std::vector<int> vec_y = {4, 5, 6};
// 내적 계산: (1*4) + (2*5) + (3*6) = 4 + 10 + 18 = 32
int dot_product = std::inner_product(vec_x.begin(), vec_x.end(), vec_y.begin(), 0);
std::cout << "내적 결과: " << dot_product << std::endl; // 출력: 32
return 0;
}
6.3 연속 값 채우기: iota (C++11)
지정된 범위에 시작 값부터 1씩 증가하는 연속적인 값을 채웁니다.
#include <vector>
#include <numeric> // For std::iota
#include <iostream>
int main() {
std::vector<int> sequence_vec(5); // 5개 요소의 벡터
// 10부터 시작하는 연속 값으로 채우기
std::iota(sequence_vec.begin(), sequence_vec.end(), 10);
std::cout << "iota 채우기 후: ";
for (int val : sequence_vec) {
std::cout << val << " "; // 출력: 10 11 12 13 14
}
std::cout << std::endl;
return 0;
}
6.4 부분 합 계산: partial_sum
주어진 범위의 부분 합(누적 합)을 계산하여 다른 범위에 저장합니다.
#include <vector>
#include <numeric> // For std::partial_sum
#include <iostream>
int main() {
std::vector<int> input_data = {1, 2, 3, 4, 5};
std::vector<int> output_sum(input_data.size());
// 부분 합 계산: {1, 1+2, 1+2+3, ...}
std::partial_sum(input_data.begin(), input_data.end(), output_sum.begin());
std::cout << "부분 합: ";
for (int val : output_sum) {
std::cout << val << " "; // 출력: 1 3 6 10 15
}
std::cout << std::endl;
return 0;
}
6.5 인접 요소 차이 계산: adjacent_difference
인접한 요소들 사이의 차이를 계산하여 다른 범위에 저장합니다. 첫 번째 요소는 그대로 복사됩니다.
#include <vector>
#include <numeric> // For std::adjacent_difference
#include <iostream>
int main() {
std::vector<int> original_seq = {10, 12, 15, 19, 24};
std::vector<int> diff_seq(original_seq.size());
// 인접한 요소 차이 계산: {10, 12-10, 15-12, ...}
std::adjacent_difference(original_seq.begin(), original_seq.end(), diff_seq.begin());
std::cout << "인접 차이: ";
for (int val : diff_seq) {
std::cout << val << " "; // 출력: 10 2 3 4 5
}
std::cout << std::endl;
return 0;
}
7. 기타 유용한 알고리즘
7.1 생성 함수로 범위 채우기: generate
지정된 생성 함수(제너레이터)를 사용하여 범위의 모든 요소를 채웁니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> fill_vec(5);
int current_num = 0;
// 0부터 시작하는 증가하는 값으로 채우기
std::generate(fill_vec.begin(), fill_vec.end(), [¤t_num]() {
return current_num++;
});
std::cout << "Generate로 채우기: ";
for (int val : fill_vec) {
std::cout << val << " "; // 출력: 0 1 2 3 4
}
std::cout << std::endl;
return 0;
}
7.2 생성 함수로 N개 요소 채우기: generate_n
범위의 시작부터 n개의 요소를 지정된 생성 함수로 채웁니다.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> initial_vec(5, -1); // -1로 초기화된 벡터
int seed_val = 100;
// 벡터의 첫 3개 요소를 100부터 시작하는 값으로 채우기
std::generate_n(initial_vec.begin(), 3, [&seed_val]() {
return seed_val++;
});
std::cout << "Generate_n으로 채우기: ";
for (int val : initial_vec) {
std::cout << val << " "; // 출력: 100 101 102 -1 -1
}
std::cout << std::endl;
return 0;
}
7.3 부분 집합 포함 여부 확인: includes
두 개의 정렬된 범위가 주어졌을 때, 첫 번째 범위가 두 번째 범위의 모든 요소를 포함하는지 확인합니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
int main() {
std::vector<int> main_set = {10, 20, 30, 40, 50}; // 정렬되어야 함
std::vector<int> sub_set_a = {20, 40}; // 정렬되어야 함
std::vector<int> sub_set_b = {10, 60};
// main_set이 sub_set_a를 포함하는가?
bool contains_a = std::includes(main_set.begin(), main_set.end(),
sub_set_a.begin(), sub_set_a.end());
std::cout << "main_set이 sub_set_a를 포함하는가? " << std::boolalpha << contains_a << std::endl; // 출력: true
// main_set이 sub_set_b를 포함하는가?
bool contains_b = std::includes(main_set.begin(), main_set.end(),
sub_set_b.begin(), sub_set_b.end());
std::cout << "main_set이 sub_set_b를 포함하는가? " << std::boolalpha << contains_b << std::endl; // 출력: false
return 0;
}
7.4 집합 연산: set_union, set_intersection, set_difference, set_symmetric_difference
모든 집합 알고리즘은 정렬된 범위에 대해 작동하며, 결과도 정렬된 상태로 생성됩니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // For std::back_inserter
// 결과를 출력하는 헬퍼 함수
void print_vector(const std::string& title, const std::vector<int>& vec) {
std::cout << title;
for (int x : vec) {
std::cout << x << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> set1 = {1, 2, 3, 4, 5};
std::vector<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> result_set;
// 1. 합집합 (Union)
result_set.clear();
std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result_set));
print_vector("합집합: ", result_set); // 출력: 1 2 3 4 5 6 7
// 2. 교집합 (Intersection)
result_set.clear();
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result_set));
print_vector("교집합: ", result_set); // 출력: 3 4 5
// 3. 차집합 (Difference: set1 - set2)
result_set.clear();
std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result_set));
print_vector("차집합 (set1 - set2): ", result_set); // 출력: 1 2
// 4. 대칭 차집합 (Symmetric Difference: (set1 ∪ set2) - (set1 ∩ set2))
result_set.clear();
std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result_set));
print_vector("대칭 차집합: ", result_set); // 출력: 1 2 6 7
return 0;
}
8. 자주 묻는 질문 (FAQ)
8.1 sort와 stable_sort의 차이점은 무엇인가요?
std::sort: 일반적으로 빠르지만(평균 O(N log N)), 값이 동일한 요소들의 상대적인 순서를 보장하지 않는 불안정 정렬입니다. 인트로소트(Introsort)를 사용합니다.std::stable_sort: 값이 동일한 요소들의 상대적인 순서를 유지하는 안정 정렬입니다(O(N log N)). 메모리 사용량이 더 많을 수 있습니다. 병합 정렬(Merge Sort)을 사용합니다.
8.2 remove 알고리즘은 왜 항상 erase와 함께 사용해야 하나요?
std::remove (및 std::remove_if)는 실제로는 컨테이너에서 요소를 삭제하지 않습니다. 대신, 삭제되지 않을 요소들을 범위의 시작 부분으로 "이동"시키고, 논리적으로 새로운 끝을 가리키는 이터레이터를 반환합니다. 컨테이너의 크기는 변하지 않으며, 이동된 요소들 뒤에는 "유효하지 않은" 요소들이 남아있을 수 있습니다. 따라서, 실제 메모리에서 이 요소들을 제거하고 컨테이너의 크기를 조정하려면 반환된 이터레이터와 container.end()를 사용하여 컨테이너의 erase() 멤버 함수를 호출해야 합니다. 이것을 "erase-remove 이디엄"이라고 합니다.
8.3 어떤 알고리즘들이 컨테이너가 정렬되어 있어야만 올바르게 작동하나요?
이진 검색을 기반으로 하는 알고리즘(예: binary_search, lower_bound, upper_bound, equal_range), 집합 연산 알고리즘(예: set_union, set_intersection, includes), 그리고 merge와 같은 알고리즘은 효율성을 위해 입력 범위가 정렬되어 있다고 가정합니다. 정렬되지 않은 범위에 이들을 적용하면 예측할 수 없는 결과가 발생하거나 잘못된 동작을 할 수 있습니다.