24.12.09 언리얼(STL의 자료구조과 알고리즘)

어제 배웠던 STL과 알고리즘에 대해 자세히 알아보자

Vector

벡터는 동적배열로, 사용자가 원하는 만큼 크기를 조절합니다. 인덱스를 통해 빠른 접근이 가능합니다.

단점: 연속된 메모리 구조로 인해 중간요소를 삽입하거나 삭제할때 시간이 걸립니다.

 

ex)

std::vector<int> numbers;
numbers.push_back(5);
numbers.push_back(10);
numbers.push_back(15);

for (size_t i = 0; i < numbers.size(); i++) {
    std::cout << numbers[i] << " ";
} // 출력: 5 ,10,15
numbers.pop_back();//출력 : 5, 10

 

list

리스트는 이중연결리스트(연결된 기차라고 생각하면 편함 )로 ,중간 삽입과 삭제가 빠릅니다. 연속된 메모리가 없기에 메모리 할당도 자유롭습니다.

단점: 인덱스로 접근 할수 없습니다.

 

std::list<int> numbers;
numbers.push_back(5);
numbers.push_front(10);
numbers.insert(++numbers.begin(), 20);  // 두 번째 위치에 삽입

for (int num : numbers) {
    std::cout << num << " ";
}

 

set

셋은 중복되지않게 요소를 저장하며 자동으로 정렬됩니다.

검색,삽입,삭제가 **O(log n)**의 시간 복잡도로 수행되며, 인덱스로 접근은 불가능합니다.

ex)

std::set<int> numbers = {5, 10, 15};
numbers.insert(5);  // 중복된 값은 무시됨

for (int num : numbers) {
    std::cout << num << " ";
}
numbers.erase(10);

 

Map

맵은 키 - 값으로 짝을 이뤄서 데이터를 저장합니다. 키는 유일해야하며 자동으로 정렬됩니다.(오름차순)

검색,삽입,삭제가 O(log n)의 시간 복잡도로 수행됩니다.

ex)

std::map<std::string, int> ages;
ages["Alice"] = 30;
ages.insert({"Bob", 25});

if (ages.find("Bob") != ages.end()) {
    std::cout << "Bob의 나이: " << ages["Bob"] << std::endl;
}
ages.erase("Alice");

 

알고리즘

프로그래밍을 공부해본 경험이 있다면 다양한 알고리즘이 있다는 것을 알게 될겁니다.

그 중 가장 대표적인 Sort(정렬),Find(검색), Transform(변환), Accumulate(합계)을 지원합니다.

 

Sort

주어진 범위의 데이터를 오름차순 또는 내림차순으로 정렬합니다. 정렬조건을 추가할 수 있습니다.

 

std::vector<int> numbers = {5, 3, 8, 1, 2};
std::sort(numbers.begin(), numbers.end(), std::greater<int>());

for (int num : numbers) {
    std::cout << num << " ";  // 8 5 3 2 1
}

 

Find

std::find는 주어진 범위에서 특정 값을 찾는 선형 검색 알고리즘입니다. 요소가 많을 경우 **이진 탐색(binary search)**이 더 효율적입니다.

STL에서는 다양한 이진탐색 관련 함수를 제공합니다.(ex. std::binary_search,std::lower_bound,std::upper_bound 등)

 

ex)

std::vector<int> numbers = {1, 2, 3, 4, 5};
auto it = std::find(numbers.begin(), numbers.end(), 3);

if (it != numbers.end()) {
    std::cout << "값 3을 찾았습니다.";
}

Transform

각 요소에 변환(ex. 산술연산)을 적용하여 새로운 범위(새로운 벡터나 리스트나 새로운 박스)에 저장합니다.

ex)

std::vector<int> numbers = {1, 2, 3, 4, 5};
std::vector<int> squares(numbers.size());

std::transform(numbers.begin(), numbers.end(), squares.begin(), [](int x) {
    return x * x;
});

for (int square : squares) {
    std::cout << square << " ";  // 1 4 9 16 25
}

Accumulate

합계는 주어진 범위(박스)의 요소를 누적(합하거나 곱 등등)하여 하나의 결과를 생성합니다.

ex)

std::vector<int> numbers = {1, 2, 3, 4, 5};
int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
std::cout << "합계: " << sum << std::endl;  // 15

int product = std::accumulate(numbers.begin(), numbers.end(), 1, std::multiplies<int>());
std::cout << "곱: " << product << std::endl;  // 120