알고리즘
STL 알고리즘 개요
STL 알고리즘은 컨테이너의 요소들을 처리하는 일반화된 함수들의 집합입니다.
이들은 <algorithm> 헤더에 정의되어 있으며, 반복자를 통해 컨테이너와 상호작용합니다.
주요 특징
- 컨테이너 독립적 : 특정 컨테이너에 종속되지 않음
- 효율성 : 최적화된 구현 제공
- 재사용성 : 다양한 상황에서 활용 가능
- 일관성 : 유사한 인터페이스로 다양한 작업 수행
주요 알고리즘 카테고리
STL 알고리즘은 다음과 같은 주요 카테고리로 나눌 수 있습니다.
- 비수정 시퀀스 연산 (예 : find, count)
- 수정 시퀀스 연산 (예 : copy, remove)
- 정렬 관련 연산 (예 : sort, binary_search)
- 수치 연산 (예 : accumulate)
- 집합 연산 (예 : set_union, set_intersection)
각 카테고리별로 주요 알고리즘들을 살펴보겠습니다.
비수정 시퀀스 연산
std::find
std::find는 지정된 값을 가진 첫 번째 요소를 찾는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = std::find(vec.begin(), vec.end(), 3);
if (it != vec.end()) {
std::cout << "Found: " << *it << " at position " << std::distance(vec.begin(), it) << std::endl;
} else {
std::cout << "Not found" << std::endl;
}
return 0;
}std::count
std::count는 특정 값의 출현 횟수를 세는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
int count = std::count(vec.begin(), vec.end(), 2);
std::cout << "Number of 2s: " << count << std::endl;
return 0;
}std::find_if
std::find_if는 주어진 조건을 만족하는 첫 번째 요소를 찾는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <algorithm>
bool is_even(int n) {
return n % 2 == 0;
}
int main() {
std::vector<int> vec = {1, 3, 5, 2, 4, 6};
auto it = std::find_if(vec.begin(), vec.end(), is_even);
if (it != vec.end()) {
std::cout << "First even number: " << *it << std::endl;
} else {
std::cout << "No even numbers found" << std::endl;
}
return 0;
}수정 시퀀스 연산
std::copy
std::copy는 요소를 다른 위치로 복사하는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);
std::copy(source.begin(), source.end(), destination.begin());
for (int num : destination) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}std::remove
std::remove는 특정 값을 제거하는 알고리즘입니다. (실제로는 요소를 이동시킴)
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
auto new_end = std::remove(vec.begin(), vec.end(), 2);
vec.erase(new_end, vec.end()); // 실제로 컨테이너에서 제거
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}std::transform
std::transform은 각 요소에 함수를 적용하여 결과를 다른 컨테이너에 저장하는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int square(int n) {
return n * n;
}
int main() {
std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> output(5);
std::transform(input.begin(), input.end(), output.begin(), square);
for (int num : output) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}정렬 관련 연산
std::sort
std::sort는 요소를 정렬하는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9};
std::sort(vec.begin(), vec.end());
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}std::binary_search
std::binary_search는 정렬된 범위에서 이진 검색을 수행하는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
bool found = std::binary_search(vec.begin(), vec.end(), 5);
std::cout << "5 is " << (found ? "found" : "not found") << std::endl;
return 0;
}수치 연산
std::accumulate
std::accumulate는 요소들의 합을 계산하는 알고리즘입니다.
#include <iostream>
#include <vector>
#include <numeric> // std::accumulate를 위해 필요
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = std::accumulate(vec.begin(), vec.end(), 0);
std::cout << "Sum: " << sum << std::endl;
return 0;
}람다 함수와 알고리즘
C++ 11부터 도입된 람다 함수를 STL 알고리즘과 함께 사용하면 더욱 유연한 동작을 구현할 수 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::for_each(vec.begin(), vec.end(), [](int& n) { n *= 2; });
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}실습 : 학생 성적 관리 시스템
다음 요구사항을 만족하는 간단한 학생 성적 관리 시스템을 구현해보세요.
Student구조체 정의 (이름, 점수)- 여러 학생의 정보를 벡터에 저장
- 학생들의 평균 점수 계산 (std::accumulate 사용)
- 점수에 따라 학생들을 정렬 (std::sort 사용)
- 특정 점수 이상의 학생 수 계산 (std::count_if 사용)
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
struct Student {
std::string name;
int score;
Student(const std::string& n, int s) : name(n), score(s) {}
};
int main() {
std::vector<Student> students = {
{"Alice", 85}, {"Bob", 72}, {"Charlie", 90}, {"David", 68}, {"Eve", 95}
};
// 평균 점수 계산
double average = std::accumulate(students.begin(), students.end(), 0.0,
[](double acc, const Student& s) { return acc + s.score; }) / students.size();
std::cout << "Average score: " << average << std::endl;
// 점수에 따라 정렬
std::sort(students.begin(), students.end(),
[](const Student& a, const Student& b) { return a.score > b.score; });
std::cout << "Sorted students:" << std::endl;
for (const auto& student : students) {
std::cout << student.name << ": " << student.score << std::endl;
}
// 80점 이상인 학생 수 계산
int high_scorers = std::count_if(students.begin(), students.end(),
[](const Student& s) { return s.score >= 80; });
std::cout << "Number of students scoring 80 or above: " << high_scorers << std::endl;
return 0;
}연습 문제
std::transform을 사용하여 섭씨 온도 벡터를 화씨 온도 벡터로 변환하는 프로그램을 작성하세요.std::partition을 사용하여 벡터의 요소를 짝수와 홀수로 분리하는 프로그램을 작성하세요.std::unique를 사용하여 정렬된 벡터에서 중복된 요소를 제거하는 프로그램을 작성하세요.
참고자료
- "Effective STL" by Scott Meyers (항목 31-37 : 알고리즘에 대한 내용)
- "The C++ Standard Library" by Nicolai M. Josuttis (Chapter 11 : STL Algorithms)
- C++ Reference : Algorithms library
- "C++ Concurrency in Action" by Anthony Williams (Chapter 10 : Parallel STL Algorithms)