반응형
알고리즘
1. C++ 표준 라이브러리의 알고리즘은 코드의 복잡도를 줄이고 효율성을 높일 수 있으며 다양한 작업을 단순화하고 최적화할 수 있다.
2. 일반 함수로 제공되며 컨테이너의 구조와 상관없이 독립적으로 동작한다.
알고리즘 종류
1. 정렬
1) 데이터를 정렬하는 이유는 처리 속도를 올리기 위해서이다. 데이터를 저장하고 저장된 데이터를 빠르게 찾으려고 데이터를 정렬한다.
1.1 퀵 정렬(std::sort)
1) n개의 데이터를 정렬한다고 가정했을 때 최악의 경우에는 이차 시간[O(n^2)] 번의 비교를 수행하지만, 평균적으로 지수 로그 시간[O(n log n)] 번의 비교를 수행한다.
2) std::array나 std::vector 처럼 임의 접근 반복자(index를 통한 접근으로 이해하면 쉽다)를 지원하는 컨테이너를 대상으로만 사용할 수 있기 때문에 std::list처럼 원소에 차례로 접근해야하는 컨테이너는 사용할 수 없다.
- (기본) 오름차순 정렬
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 벡터의 원소를 순서대로 출력
template <typename T>
void print_vector_all(vector<T>& vec) {
for (typename vector<T>::iterator it = vec.begin(); it != vec.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
int main() {
vector<int> vec = { 7, 6, 3, 5, 4, 1, 2, 0, 8 };
// 벡터의 원소를 오름차순으로 정렬
sort(vec.begin(), vec.end());
print_vector_all(vec);
return 0;
}
/*
출력 결과
0 1 2 3 4 5 6 7 8
*/- 내림차순 정렬
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template <typename T>
void print_vector_all(vector<T>& vec) {
for (typename vector<T>::iterator it = vec.begin(); it != vec.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
int main() {
vector<int> vec = { 7, 6, 3, 5, 4, 1, 2, 0, 8 };
// 벡터의 원소를 내림차순으로 정렬
sort(vec.begin(), vec.end(), greater<int>());
print_vector_all(vec);
return 0;
}
/*
출력 결과
8 7 6 5 4 3 2 1 0
*/- 사용자 정의 기준으로 정렬(나이를 기준으로 오름차순 정렬)
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
struct Person {
string name; // 이름
int age; // 나이
float height; // 키
float weight; // 몸무게
};
void print_preson_all(vector<Person>& vec) {
for (vector<Person>::iterator it = vec.begin(); it != vec.end(); it++) {
cout << "이름: " << it->name << "\t > " << "나이: " << it->age << ", " << "키: " << it->height << ", " << "몸무게: " << it->weight << endl;
}
}
// Person 구조체의 나이 비교(첫 번째 인자의 나이가 작으면 true)
bool compare(const Person& lhs, const Person& rhs) {
return lhs.age < rhs.age;
}
int main() {
Person p[5] = {
{"Brain", 24, 180, 70},
{"Jessica", 22, 165, 55},
{"James", 30, 170, 65},
{"Tom", 12, 155, 46},
{"Mary", 18, 172, 62}
};
vector<Person> vec;
vec.push_back(p[0]);
vec.push_back(p[1]);
vec.push_back(p[2]);
vec.push_back(p[3]);
vec.push_back(p[4]);
cout << "-----정렬 전-----" << endl;
print_preson_all(vec);
cout << endl;
// 사용자 정의 기준으로 정렬
sort(vec.begin(), vec.end(), compare);
cout << "-----정렬 후-----" << endl;
print_preson_all(vec);
return 0;
}1.2 안정 정렬(std::stable_sort)
1) 순서의 안정성이 필요할 때 사용하며, 같은 원소가 정렬 후에도 원본의 순서와 일치한다.
2) 사용 방법은 sort 함수(불안정 정렬 함수)와 같다.
3) 시간 복잡도 측면에서 sort 함수보다 느리다.
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
bool compare_pairs(const pair<int, string>& a, const pair<int, string>& b) {
return a.first < b.first;
}
int main() {
vector<pair<int, string>> pairs = {
{5, "apple"},
{2, "orange"},
{5, "banana"},
{3, "grape"}
};
// std::stable_sort를 사용하여 pair를 첫 번째 요소에 따라 안정 정렬
stable_sort(pairs.begin(), pairs.end(), compare_pairs);
// 정렬된 결과 출력
for (vector<pair<int, string>>::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
const pair<int, string>& pair = *it;
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
/*
출력 결과
2: orange
3: grape
5: apple
5: banana
*/1.3 부분 정렬(std::partial_sort)
1) 컨테이너의 모든 원소가 아닌 일정 구간만 정렬할 때 사용한다.
2) 매개변수가 first, middle, last 로 구성되어 있다.
- first : 정렬을 시작할 범위의 시작을 가리키는 반복자
- middle : 정렬을 원하는 범위의 끝을 가리키는 반복자. 정렬 후에 이 반복자가 가리키는 위치 이전의 원소들은 정렬되지만, 이후의 원소들은 순서가 보장되지 않음
- last : 정렬을 종료할 범위의 끝을 가리키는 반복자
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = { 7, 2, 5, 1, 8, 9, 3, 6, 4 };
// numbers 벡터에서 가장 작은 3개의 요소만 정렬
partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());
// 정렬된 결과 출력
for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
/*
출력 결과
1 2 3 7 8 9 5 6 4
*/2. 찾기(std::find)
1) 순차 컨테이너에서 원하는 값을 찾는 함수이다.
2) 선형 검색을 기반으로 동작한다. 따라서 선형 시간[O(n)]이 걸린다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = { 1, 2, 3, 4, 5 };
cout << "찾고 싶은 숫자를 입력하세요: ";
int target;
cin >> target;
// 입력받은 숫자를 찾아서 해당 위치를 반환
vector<int>::iterator it = find(numbers.begin(), numbers.end(), target);
if (it != numbers.end()) {
cout << "찾은 위치: " << distance(numbers.begin(), it) << endl;
}
else {
cout << "찾을 수 없음" << endl;
}
return 0;
}
/*
출력 결과
찾고 싶은 숫자를 입력하세요: 3
찾은 위치: 2
*/- 사용자 정의 클래스에 == 연산자 오버로딩 예시
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
class my_class {
public:
int value;
string name;
// == 연산자 오버로딩
bool operator==(const my_class& other) const {
return value == other.value && name == other.name;
}
};
int main() {
vector<my_class> objects = { {1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"} };
// my_class 클래스의 모든 멤버 변수까지 같은 객체를 찾음
vector<my_class>::iterator it = find(objects.begin(), objects.end(), my_class{ 3, "three" });
if (it != objects.end()) {
cout << "찾은 위치: " << distance(objects.begin(), it) << endl;
}
else {
cout << "찾을 수 없음" << endl;
}
return 0;
}
/*
출력 결과
찾은 위치: 2
*/3. 이진 탐색(std::binary_search)
1) 정렬된 범위에서 특정 값을 이진 탐색으로 찾는 함수이다. 탐색 볌위를 반으로 나눠 범위를 좁혀가는 방식으로 동작하는 알고리즘이다.
2) 정렬되지 않은 상태에서 binary_search 함수를 사용하면, 검색 결과가 불확실하거나 검색을 아예 실패 할 수 있다.
3) 이진 탐색 알고리즘을 사용하므로 시간 복잡도는 로그 시간[O(log n)] 이다
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
// 정렬되지 않은 벡터
vector<int> numbers = { 8, 3, 1, 7, 4, 5, 9, 2, 6 };
// 정렬 수행
sort(numbers.begin(), numbers.end());
// 사용자에게 숫자 입력 받기
int target;
cout << "컨테이너에서 검색하고 싶은 숫자를 입력해보세요: ";
cin >> target;
// 이진 탐색
bool found = binary_search(numbers.begin(), numbers.end(), target);
if (found) {
cout << "찾았습니다." << endl;
}
else {
cout << "저장되어 있지 않습니다." << endl;
}
return 0;
}
/*
출력 결과
컨테이너에서 검색하고 싶은 숫자를 입력해보세요: 6
찾았습니다.
*/알고리즘 비교
| 알고리즘 | 사용 가능한 컨테이너 | 요구 반복자 종류 | 시간 복잡도 | 정렬/탐색 안정성 | 특징 |
| std::sort | array, vector, deque (연속적 메모리) | Random Access Iterator | 평균 O(N log N) 최악 O(N log² N) |
❌ 불안정 (unstable sort) | 빠른 정렬, 내부적으로 introsort(quick + heap + insertion) |
| std::stable_sort | array, vector, deque | Random Access Iterator | 평균/최악 O (N log² N) |
✅ 안정적 (stable sort) | 동일 값의 상대적 순서 유지 |
| std::partial_sort | array, vector, deque | Random Access Iterator | O(N log M) (M = 정렬할 원소 개수) |
❌ 불안정 | 전체 정렬이 필요 없을 때 효율적 (예: 상위 10개만 정렬) |
| std::find | 모든 순차 컨테이너 및 연관 컨테이너 array, vector, deque, list, forward_list, set, map, unordered_* 등 |
Input Iterator 이상 | O(N) | — | 순차 탐색, 처음 일치하는 원소 반환 |
| std::binary_search | array, vector, deque(정렬된 컨테이너만 가능) | Random Access Iterator | O(log N) | — | 정렬된 구간에서 이진 탐색 수행 |
반응형