std::tuple이란?

• 기존에 다른 데이터 타입의 값 2개를 저장하기 위해 pair를 사용했지만, first와 second 두 개의 요소만 관리할 수 있었다.
• C++11부터 STL에서 tuple을 제공하여 다수의 요소를 관리할 수 있는 tuple을 제공한다.
• <tuple>에 정의되어 있다.

기본 사용법

#include <tuple>
#include <iostream>

int main() {
    // 다양한 타입의 요소들을 포함하는 튜플 생성
    std::tuple<int, double, std::string> myTuple(1, 3.14, "Hello");

    // 튜플의 요소에 접근
    std::cout << "Integer: " << std::get<0>(myTuple) << std::endl;
    std::cout << "Double: " << std::get<1>(myTuple) << std::endl;
    std::cout << "String: " << std::get<2>(myTuple) << std::endl;

    return 0;
}

별 특이한 점은 없지만, std::get을 사용할 수 있다.

std::get

std::get 템플릿 함수를 이용해서 튜플의 요소에 접근할 수 있다(인덱스를 통해 접근)

std::get<0>(myTuple);  // 첫 번째 요소
std::get<1>(myTuple);  // 두 번째 요소
std::get<2>(myTuple);  // 세 번째 요소

std::make_tuple

주어진 값들로 초기화된 튜플을 리턴

auto t3 = std::make_tuple(2, 2.71, "World");

std::tie

기존 변수들을 튜플의 요소에 바인딩해준다

int a;
double b;
std::string c;

std::tie(a, b, c) = t3;

std::tuple_cat()

두 개의 tuple을 합친다

auto t1{std::make_tuple(10, "Name", 'a')};
auto t2{std::make_tuple("Hello", 20, 'b')};

auto t3{std::tuple_cat(t1, t2)};   
EXPECT_TRUE(
    std::get<0>(t3) == 10 && 
    std::get<1>(t3) == "Name" && 
    std::get<2>(t3) == 'a' &&
    std::get<3>(t3) == "Hello" && 
    std::get<4>(t3) == 20 && 
    std::get<5>(t3) == 'b'
);

std::string이란?

• STL에서 제공하는 문자열 처리 클래스
• 동적 길이 문자열을 다루기 쉽게 만들어준다.
• <string>에 정의되어 있다.

내부 구현?

• 문자열의 크기에 따라 동적으로 할당하여 문자열 데이터를 저장한다
• 짧은 문자열은 내부 버퍼에 따로 저장하여 동적 할당을 하지 않는다
• 복사 및 연산 과정에서 기본적으로 깊은 복사를 사용한다. 포인터나 참조가 기반으로 관리되지 않는다

초기화

기본 생성자 : 빈 문자열 생성

std::string s;

C-스타일 문자열로부터 생성

std::string s1("Hello");
std::string s2 = "Hello";
std::string s3 = "";

반복자로부터 생성

std::string s(iter1, iter2);

특정 문자 n개로 초기화

std::string s(5, 's');// "sssss"

부분 문자열

std::string s1 = "abc";

std::string s2(s1, 1, 2); // s1[1]부터 2개 문자를 복사하여 생성합니다.
EXPECT_TRUE(s2 == "bc");

// std::string s3(s1, 100, 2); // (X) 예외 발생. s1[100]부터 2개 복사. out_of_range

std::string s4(s1, 0, std::string::npos); // s1[0] 부터 끝까지 복사하여 생성합니다.
EXPECT_TRUE(s4 == s1);

std::string s5(s1.begin(), s1.end()); // s1.begin()부터 s1.end() 직전 까지 복사하여 생성합니다. 즉, s1[0]부터 끝까지 복사하여 생성합니다.
EXPECT_TRUE(s5 == s1);

const char* ptr = "abc";
std::string s6("abc", 2); // ptr에서 2개 복사하여 생성합니다.
EXPECT_TRUE(s6 == "ab");

참조) https://tango1202.github.io/legacy-cpp-stl/legacy-cpp-stl-string/

문자열 수정

append: 문자열을 끝에 추가

s.append(" World");

insert : 문자열을 지정된 위치에 삽입

s.insert(5, " C++");

erase : 지정된 위치의 문자열 제거

s.erase(5, 3);  // 5번 인덱스부터 3글자 제거

replace : 지정된 범위의 문자들을 다른 문자열로 대체

s.replace(0, 5, "Hi");  // 처음 5글자를 "Hi"로 대체

문자열 연산자

• "="를 이용하여 문자열 할당
• "+", "+="를 이용하여 문자열 합성
• "=", "!=", "<", ">", "<=", ">="를 이용하여 대소 비교

std::string s = "abc";

EXPECT_TRUE(s == "abc");
EXPECT_TRUE(s != "def");
EXPECT_TRUE(s < "ccc");
EXPECT_TRUE(s.compare("ccc") < 0); // s < "ccc"
EXPECT_TRUE(s.compare("abc") == 0); // s == "abc"
EXPECT_TRUE(s.compare("aaa") > 0); // s > "aaa"

문자열 검색

find : 부분 문자열 검색. 주어진 부분 문자열의 위치를 리턴한다. 리턴받은 인덱스 이후부터 찾을 수 있다.

std::size_t pos = s.find("Hello");
if (pos != std::string::npos) { /* ... */ }

find_first_of(), find_last_of() : 전달한 문자들 중 일치하는 문자가 있는 첫 번째/마지막 위치를 리턴한다

std::size_t pos = s.find_first_of("aeiou");
std::size_t pos = s.find_last_of("aeiou");

rfind : 문자열을 역방향으로 검색

std::size_t pos = s.rfind("Hello");

부분 문자열 처리

substr : 부분 문자열을 복사하여 반환

replace : 부분 문자열로 대체

copy : 부분 문자열을 문자 배열에 복사

std::string s = "Hello. My name is Tango.";

std::string::size_type pos = s.find("Tango");
std::string::size_type count = std::string("Tango").size();

s.replace(pos, count, "Sam"); // Tango를 Sam으로 바꿉니다.
EXPECT_TRUE(s == "Hello. My name is Sam."); 

EXPECT_TRUE(s.substr(pos, 3) == "Sam"); // 부분 문자열을 복사하여 리턴합니다.

char arr[3]; // 문자 배열
s.copy(arr, 3, pos); // 크기가 3인 arr 배열에 pos 위치에서부터 배열 크기만큼 부분 문자열을 복사 합니다.
EXPECT_TRUE(arr[0] == 'S' && arr[1] == 'a' && arr[2] == 'm');

Program Example

#include <iostream>
#include <string>

int main() {
    std::string str = "Hello, World!";
    
    // 문자열 길이
    std::cout << "Length: " << str.size() << std::endl;
    
    // 부분 문자열
    std::string sub = str.substr(7, 5);  // "World"
    std::cout << "Substring: " << sub << std::endl;
    
    // 문자열 검색
    std::size_t pos = str.find("World");
    if (pos != std::string::npos) {
        std::cout << "'World' found at position: " << pos << std::endl;
    }
    
    // 문자열 대체
    str.replace(7, 5, "C++");
    std::cout << "Replaced: " << str << std::endl;
    
    // 문자열 연결
    std::string str2 = " How are you?";
    str += str2;
    std::cout << "Concatenated: " << str << std::endl;
    
    return 0;
}

std::pair란?

• 두 개의 이질적인 데이터 타입의 값을 하나로 묶어서 저장하는데 사용되는 템플릿 클래스
• 두 개의 값을 리턴해야 해야 하거나, 두 개의 값을 key와 value로 사용하는데 유용하다
• <utility>에 정의되어 있다.

std::pair의 구현 방식

• 실제 구현 코드는 아니지만, 이러한 방식으로 구현되어 있다

template <typename T1, typename T2>
struct pair {
    T1 first;
    T2 second;

    // 기본 생성자
    pair() : first(T1()), second(T2()) {}

    // 사용자 정의 생성자
    pair(const T1& a, const T2& b) : first(a), second(b) {}

    // 복사 생성자
    template <typename U1, typename U2>
    pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}

    // 이동 생성자
    template <typename U1, typename U2>
    pair(pair<U1, U2>&& p) : first(std::move(p.first)), second(std::move(p.second)) {}

    // 복사 대입 연산자
    pair& operator=(const pair& p) {
        if (this != &p) {
            first = p.first;
            second = p.second;
        }
        return *this;
    }

    // 이동 대입 연산자
    pair& operator=(pair&& p) noexcept {
        if (this != &p) {
            first = std::move(p.first);
            second = std::move(p.second);
        }
        return *this;
    }

    // 비교 연산자
    bool operator==(const pair& p) const {
        return first == p.first && second == p.second;
    }

    bool operator!=(const pair& p) const {
        return !(*this == p);
    }

    bool operator<(const pair& p) const {
        return first < p.first || (!(p.first < first) && second < p.second);
    }

    bool operator<=(const pair& p) const {
        return !(p < *this);
    }

    bool operator>(const pair& p) const {
        return p < *this;
    }

    bool operator>=(const pair& p) const {
        return !(*this < p);
    }
};

이거 말고 다른 기능은 없나요?

• std::pair는 map, queue, stack과 같은 컨테이너가 아니다
  • std::map과 std::unordered_map과 같은 연관 컨테이너에서 key-value쌍을 나타내기 위해 많이 사용된다
• 두 개의 값을 묶는 단순한 구조체로, 삽입, 삭제, 검색 등의 메서드를 제공하지 않는다.
  • 삽입, 삭제, 검색 등은 std::pair를 사용하는 컨테이너에 제공된다

선언 및 초기화

#include <utility>

std::pair<int, std::string> p1;  // 정수와 문자열을 쌍으로 가지는 pair
std::pair<int, std::string> p2(42, "Hello");  // 생성자 초기화
auto p3 = std::make_pair(42, "Hello");  // make_pair 함수 사용

멤버 변수

first와 second 멤버 변수가 존재한다

std::cout << p2.first << " " << p2.second << std::endl;  // 42 Hello

생성자

기본 생성자, 복사 생성자, 이동 생성자, 사용자 정의 생성자를 사용할 수 있다.

std::pair<int, std::string> p4(p2);  // 복사 생성자
std::pair<int, std::string> p5(std::move(p2));  // 이동 생성자

비교 연산자

위 구현 코드에서 알 수 있듯이 비교 연산 또한 지원한다

std::pair<int, std::string> p6(42, "Hello");
std::pair<int, std::string> p7(42, "World");

if (p6 == p2) { /* ... */ }  // true
if (p6 < p7) { /* ... */ }   // true

활용 예시

함수에서 여러 개의 값을 반환해야 하는 경우

std::pair<int, std::string> getAgeAndName() {
    return std::make_pair(30, "Alice");
}

auto result = getAgeAndName();
std::cout << "Age: " << result.first << ", Name: " << result.second << std::endl;

map과 같은 STL에서 key-value 쌍을 저장하는 경우

#include <map>

std::map<int, std::string> myMap;
myMap.insert(std::make_pair(1, "one"));
myMap.insert(std::make_pair(2, "two"));

for (const auto& pair : myMap) {
    std::cout << pair.first << " => " << pair.second << std::endl;
}

C++ 해시 테이블

• 해시 구현에서 항상 양의 정수만 취급할 수는 없다.
• 오히려 문자열 데이터를 다루게 되는 경우가 더 많다
  • 영어 사전을 구현하려면 영어 단어를 키로 사용하고, 뜻을 값으로 사용해야 한다
• 모듈로 함수는 문자열에는 적용할 수 없다
  • 간단한 해결책은 문자열의 모든 문자에 대한 ASCII 코드 값을 모두 더한 후에 모듈로 연산을 하는 것이다.
  • 위 방법은 충돌이 빈번하게 발생할 수 있다
• C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash<std::string>(std::string) 함수 객체를 제공한다
  • 이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다.
• C++은 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다
• "체이닝을 사용하는 해시 테이블"에서 구현했던 해시 테이블 코드를 템플릿 형태로 바꾸면 모든 데이터 타입에 대해 사용할 수 있는 형태로 만들 수 있다.
• STL은 이러한 기능을 std::unordered_set와 std::unordered_set<Key, Value> 형태로 미리 구현하여 제공한다
  • std::unordered_set은 키만 저장할 수 있고, std::unordered_map은 키와 value를 함께 저장할 수 있다
  • 두 컨테이너 모두 체이닝을 사용하는 해시 테이블 형태로 구현되어 있다.
    • 해시 테이블의 각 행은 키 또는 키와 값의 쌍을 저장하는 벡터이다. 여기서 각 행을 버킷(bucket)이라고 부른다
    • 즉, key로부터 해시 값을 구하면 이에 해당하는 버킷에 접근할 수 있다
  • 기본적으로 이들 컨테이너는 최대 1의 부하율을 가진다
    • 해시 테이블 크기보다 원소 개수가 많아지게 되면 곧바로 해시 테이블을 키우고, 해시 함수를 변경하는 재해싱이 일어난다
    • 사용자가 강제로 rehash()함수를 호출하여 재해싱을 할 수도 있다
    • max_load_factor(float) 함수를 사용하여 기본값이 1로 되어 있는 부하율 최대 한계치를 변경할 수도 있다
• std::unordered_set와 std::unordered_map 컨테이너는 검색, 삽입, 삭제 등의 보편적인 기능을 제공한다
• 모든 원소에 차례대로 접근할 수 있도록 반복자 기능도 제공하고, 벡터나 배열 같은 다른 컨테이너로부터 바로 std::unordered_set 또는 std::unordered_map을 구성할 수 있는 생성자도 제공한다.
• std::unordered_map은 []연산자를 이용하여 주어진 키에 해당하는 값을 받을 수도 있다.
  • 파이썬의 dictionary 처럼 작동한다

Example) STL에서 제공하는 해시 테이블

#include <iostream>
#include <unordered_map>
#include <unordered_set>

void print(const std::unordered_set<int>& container)
{
    for(const auto& element : container)
        std::cout << element << " ";

    std::cout << std::endl;
}

void print(const std::unordered_map<int, int>& container)
{
    for(const auto& element : container)
        std::cout << element.first << " -> " << element.second << ", ";

    std::cout << std::endl;
}

void find(const std::unordered_set<int>& container, const int element)
{
    if(container.find(element) == container.end())   
        std::cout << element << " 검색 실패" << std::endl;
    else
        std::cout << element << " 검색 성공" << std::endl;
}

void find(const std::unordered_map<int, int>& container, const int element)
{
    auto it = container.find(element);

    if(it == container.end())
        std::cout << element << " 검색 실패" << std::endl;
    else
        std::cout << element << "검색 성공 값 = " << it->second << std::endl;
}

int main()
{
    std::cout << "*** std::unordered_set 예제 ***" << std::endl;

    std::unordered_set<int> set1 = { 1, 2, 3, 4, 5 };

    std::cout << "set1 초깃값 : ";
    print(set1);

    set1.insert(2);
    std::cout << "2 삽입 : ";
    print(set1);

    set1.insert(10);
    set1.insert(300);
    std::cout << "10, 300 삽입 : ";
    print(set1);

    find(set1, 4);
    find(set1, 100);

    set1.erase(2);
    std::cout << "2 삭제 : ";
    print(set1);

    find(set1, 2);

    std::cout << "*** std::unordered_map 예제 ***" << std::endl;
    std::unordered_map<int, int> squareMap;

    squareMap.insert({2, 4});
    squareMap[3] = 9;
    std::cout << "2, 3의 제곱 삽입 : ";
    print(squareMap);

    squareMap[20] = 400;
    squareMap[3] = 900;
    std::cout << "20, 30의 제곱 삽입 : ";
    print(squareMap);

    find(squareMap, 10);
    find(squareMap, 20);

    std::cout << "squareMap[3] = " << squareMap[3] << std::endl;
    std::cout << "squareMap[100] = " << squareMap[100] << std::endl;
    print(squareMap);

    return 0;
}

• 이들 컨테이너에서 저장된 원소 순서는 정해져 있지 않으며, 이 때문에 컨테이너 이름에 'unordered'가 들어간다
• [] 연산자는 key에 해당하는 실제 값이 없을 때는 기본 값 0을 추가한 후 반환해준다
• 현재 버킷의 개수를 알고 싶으면 bucket_count() 함수를 사용할 수 있다
• 이 외에도 load_factor(), max_bucket_count() 등의 함수를 이용하여 컨테이너 내부에서 사용되는 설정 값을 알 수 있다
• 또한 rehash()함수를 이용하여 수동으로 재해싱을 수행할 수 있다
• 이들 컨테이너는 체이닝 기법을 사용하여 구현되었으므로, 버킷에서 특정 키를 찾을 때 키가 같은지를 비교해야 한다
  • 그러므로 키 타입에 대해 등호 연산이 정의되어 있어야 한다. 또는 템플릿 매개변수로 비교자를 지정할 수 있다
• std::unordered_set와 std::unordered_map은 중복된 키를 허용하지 않는다
  • 만약 중복된 값을 저장하고 싶다면 std::unordered_multiset 또는 std::unordered_multimap을 사용해야 한다
  • 이 두 컨테이너의 삽입 함수는 주어진 키가 이미 존재하는지를 검사하지 않는다.
  • 또한 이들 컨테이너는 특정 키에 해당하는 모든 값을 얻을 수 있는 기능도 지원한다
• STL은 C++에서 지원하는 모든 기본 데이터 타입에 대한 해시 함수를 제공한다
  • 따라서 앞서 언급했던 컨테이너에서 사용자 정의 클래스 또는 구조체를 키 타입으로 사용하려면 std 네임스페이스 안에서 해시 함수를 구현해야 한다
  • 또는 컨테이너 템플릿 매개변수로 해서 해시 함수 객체를 지정할 수도 있다
    • 해시 함수를 직접 만드는 것은 성능에 큰 영향을 주기 때문에 그다지 좋은 생각은 아니다
• 해시 함수로 MD5, SHA-1, SHA-256 같은 복잡한 암호화 함수도 사용할 수 있다
  • 암호화 함수를 사용하면, 해시 값으로 부터 원본 데이터를 알아내는 역해싱이 매우 어렵기 때문에 보안 시스템에서 사용되기도 한다

그래프(graph)

• 트리는 원형 또는 순환적인 종속성을 표현할 수 없다.
  • 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에
    • 도로망을 생각해보자. 특정 노드에서 다른 노드로 이동하기 위한 다양한 경로가 존재할 수 있다.
• 이러한 경우에는 그래프(graph) 구조를 사용해야 한다

그래프 구분 - weight

• 그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 한다.
  • 도로망을 예로 들면 각각의 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 한다.
    • 이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있다.
      • 이러한 그래프를 비가중 그래프(unweighted graph)라고 한다.
• 에지에 가중치 또는 더 많은 정보를 부여할 수 있다.
  • 도로망에서 에지에 노드와 노드 사이의 거리를 저장할 수 있다.
    • 이러한 형태의 그래프를 가중 그래프(weighted graph) 라고 한다
  • 최단 거리 경로 탐색 같은 문제에서 이 그래프를 활용할 수 있다.

그래프 구분 - 방향성

• 그래프는 방향성이 있는 그래프와 방향성이 없는 그래프로 구분할 수 있다.
• 무방향 그래프(undirected graph)는 에지가 양방향임을 의미한다.
  • 양방향이라 함은 대칭적인, 또는 상호 교환적인 속성을 나타낸다
• 이와 반대되는 개념으로는 방향 그래프(directed graph)가 있다.
  • 어떤 도로가 일방통행으로 제한되어 있는 경우를 생각해보자
  • 방향 그래프에서 양방향 에지를 표현하려면, A->B, B->A 두 개의 에지를 사용해야 한다
• 무방향 그래프의 구조와 순회방법은 방향 그래프에도 적용할 수 있다.
  • 다만 그래프에 에지를 추가하는 방법만 달라짐

그래프 표현

• 그래프는 순환적 에지를 가질 수 있고, 특정 노드에서 다른 노드로 이동하는 방법이 여러 개 있을 수 있다.
  • 따라서 각 노드를 고유하게 식별해야 한다.
  • 이를 위해 각 노드에 고유한 ID를 부여할 수 있다.
• 그래프의 데이터를 표현하기 위해 반드시 트리의 노드 같은 구조를 사용해야 하는 것은 아니다.
  • 실제로 STL 컨테이너를 이용하여 그래프를 표현할 수 있다.

인접 행렬로 그래프 표현하기

• 노드가 N개 있을 경우, 이 그래프는 N X N 크기의 2차원 배열로 표현할 수 있다.
• 이 배열에서 특정 원소는 해당 원소 인덱스에 해당하는 노드 사이의 거리를 표현한다.
  • data[1][2]는 1번 노드와 2번 노드를 잇는 에지의 가중치를 나타낸다
• 이러한 방식으로 그래프를 표현하는 방법을 인접 행렬(adjacency matrix)라고 한다
• 두 노드 사이에 에지가 존재하지 않으면 해당 원소에 -1을 설정한다

Example) 인접 행렬로 도시 네트워크 그래프 구성하기

#include <iostream>
#include <vector>

enum class city : int
{
    MOSCOW,
    LONDON,
    SEOUL,
    SEATTLE,
    DUBAI,
    SYDNEY
};

std::ostream& operator<<(std::ostream& os, const city c)
{
    switch(c)
    {
        case city::LONDON:
            os << "런던";
            return os;
        case city::MOSCOW:
            os << "모스크바";
            return os;
        case city::SEOUL:
            os << "서울";
            return os;
        case city::SEATTLE:
            os << "시애틀";
            return os;
        case city::DUBAI:
            os << "두바이";
            return os;
        case city::SYDNEY:
            os << "시드니";
            return os;
        default:
            return os;
    }
}

struct graph
{
    std::vector<std::vector<int>> data;

    graph(int n)
    {
        data.reserve(n);
        std::vector<int> row(n);
        std::fill(row.begin(), row.end(), -1);

        for(int i = 0; i < n; i++)
        {
            data.push_back(row);
        }
    }

    // 에지 추가 함수로 두 개의 도시와 소이 사이의 거리(가중치)를 인자로 받음
    void addEdge(const city c1, const city c2, int dis)
    {
        std::cout << "에지 추가 : " << c1 << "-" << c2 << "-" << dis << std::endl;

        auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);

        data[n1][n2] = dis;
        data[n2][n1] = dis;
    }

    // 에지 제거 함수
    void removeEdge(const city c1, const city c2)
    {
        std::cout << "에지 삭제 : " << c1 << "-" << c2 << std::endl;

        auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);

        data[n1][n2] = -1;
        data[n2][n1] = -1;
    }
};

using namespace std;

int main()
{
    graph g(6);

    g.addEdge(city::LONDON, city::MOSCOW, 2500);
    g.addEdge(city::LONDON, city::SEOUL, 9000);
    g.addEdge(city::LONDON, city::DUBAI, 5500);
    g.addEdge(city::SEOUL, city::MOSCOW, 6600);
    g.addEdge(city::SEOUL, city::SEATTLE, 8000);
    g.addEdge(city::SEOUL, city::DUBAI, 7000);
    g.addEdge(city::SEOUL, city::SYDNEY, 8000);
    g.addEdge(city::SEATTLE, city::MOSCOW, 8400);
    g.addEdge(city::SEATTLE, city::SYDNEY, 12000);
    g.addEdge(city::DUBAI, city::SYDNEY, 1200);

    g.addEdge(city::SEATTLE, city::LONDON, 8000);
    g.removeEdge(city::SEATTLE, city::LONDON);

    return 0;
}

• 벡터의 벡터를 이용하여 데이터를 저장했다.
• 노드 개수가 V라면, 전체 V X V 크기의 메모리 공간을 사용하게 된다

인접 리스트로 그래프 표현하기

• 행렬을 이용하여 그래프를 표현할 때 가장 큰 문제는, 노드 개수의 제곱에 비례하는 메모리를 사용한다는 점이다
  • 행렬을 사용할 경우 두 노드가 서로 연결되어 있지 않더라도 모든 노드 사이의 에지 정보를 저장해야 한다
• 대신 각 노드에 직접 연결되어 있는 노드의 ID만 저장하는 방식으로 그래프를 표현할 수 있다.
  • 이러한 방식을 인접 리스트(adjacency list)라고 한다

Example) 인접 리스트로 도시 네트워크 그래프 구성하기

#include <iostream>
#include <vector>
#include <algorithm>

enum class city : int
{
    MOSCOW,
    LONDON,
    SEOUL,
    SEATTLE,
    DUBAI,
    SYDNEY
};

std::ostream& operator<<(std::ostream& os, const city c)
{
    switch(c)
    {
        case city::LONDON:
            os << "런던";
            return os;
        case city::MOSCOW:
            os << "모스크바";
            return os;
        case city::SEOUL:
            os << "서울";
            return os;
        case city::SEATTLE:
            os << "시애틀";
            return os;
        case city::DUBAI:
            os << "두바이";
            return os;
        case city::SYDNEY:
            os << "시드니";
            return os;
        default:
            return os;
    }
}

struct graph
{
    std::vector<std::vector<std::pair<int, int>>> data;

    graph(int n)
    {
        data = std::vector<std::vector<std::pair<int, int>>>(n, std::vector<std::pair<int, int>>());
    }

    // 에지 추가 함수로 두 개의 도시와 소이 사이의 거리(가중치)를 인자로 받음
    void addEdge(const city c1, const city c2, int dis)
    {
        std::cout << "에지 추가 : " << c1 << "-" << c2 << "=" << dis << std::endl;

        auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);

        data[n1].push_back({n2, dis});
        data[n2].push_back({n1, dis});
    }

    // 에지 제거 함수
    void removeEdge(const city c1, const city c2)
    {
        std::cout << "에지 삭제 : " << c1 << "-" << c2 << std::endl;

        auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);

        std::remove_if(data[n1].begin(), data[n1].end(), [n2](const auto& pair) {
            return pair.first == n2;
        });
        std::remove_if(data[n2].begin(), data[n2].end(), [n1](const auto& pair) {
            return pair.first == n1;
        });
    }
};

using namespace std;

int main()
{
    graph g(6);

    g.addEdge(city::LONDON, city::MOSCOW, 2500);
    g.addEdge(city::LONDON, city::SEOUL, 9000);
    g.addEdge(city::LONDON, city::DUBAI, 5500);
    g.addEdge(city::SEOUL, city::MOSCOW, 6600);
    g.addEdge(city::SEOUL, city::SEATTLE, 8000);
    g.addEdge(city::SEOUL, city::DUBAI, 7000);
    g.addEdge(city::SEOUL, city::SYDNEY, 8000);
    g.addEdge(city::SEATTLE, city::MOSCOW, 8400);
    g.addEdge(city::SEATTLE, city::SYDNEY, 12000);
    g.addEdge(city::DUBAI, city::SYDNEY, 1200);

    g.addEdge(city::SEATTLE, city::LONDON, 8000);
    g.removeEdge(city::SEATTLE, city::LONDON);

    return 0;
}

• 각 노드에 인접한 노드를 리스트에 저장하기 때문에 인접 리스트라고 한다
• 데이터 저장을 위해 벡터의 벡터를 사용한다.
• 다만 안쪽 벡터의 크기가 전체 노드 개수가 아니라 해당 노드에 연결된 노드 개수와 같다.
  • 인접 리스트에 의한 그래프 표현은 전체 에지 개수 E에 비례한 크기의 메모리를 사용한다.
• 그래프를 탐색해야 하는 경우에는 BFS(너비 우선 탐색)과 DFS(깊이 우선 탐색)과 같은 방법을 사용할 수 있다.
  • 알고리즘 파트에서 따로 다룰 예정

힙(heap)

• std::priority_queue에서 다룬 heap에 대해 더 깊이 있게 알아보자
• 힙은 앞서 말했던 것처럼 다음과 같은 시간 복잡도를 만족해야 한다

1. O(1) : 최대 원소에 즉각적으로 접근할 수 있어야 한다.
2. O(log N) : 원소 삽입에 대한 시간 복잡도
3. O(log N) : 최대 원소 삭제에 대한 시간 복잡도

• 원소 삽입 또는 삭제에 대해 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 한다.
  • 특히 이 경우 완전 이진 트리를 사용해야 한다.
• 완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있다.
  • 루트 노드를 배열 또는 벡터의 맨 처음에 저장하고, 그다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장한다
  • 포인터를 사용하지 않아서 메모리 사용 측면에서 효율적이다.
• 부모 노드로부터 자식노드로 이동하는 것은 단순히 배열의 인덱스 계산으로 가능하다.
  • 부모 노드가 i번째 배열 원소로 저장되어있다면, 자식 노드는 2i + 1 또는 2i +2번째 인덱스로 접근하면 된다
  • 자식 노드가 i번째 인덱스라면, 부모 노드는 (i - 1)/2 번째 인덱스이다.

힙의 불변성

• 원소를 삽입하거나 삭제할 때 유지해야 할 조건
  • 최대 원소에 즉각적으로 접근 가능해야 한다.
    • 이를 위해 최대 원소가 항상 고정된 위치에 있어야 한다
    •  힙을 구현할 때는 최대 원소가 트리의 루트에 있도록 설정한다
      • 이를 위해 부모 노드가 두 자식 노드보다 항상 커야 한다는 불변성을 유지하도록 설정해야 한다.
    • 이렇게 구성한 힙을 최대 힙(max heap) 이라고 한다.
    • 반대로 최소 원소에 빠르게 접근할 수 있도록 힙을 구성할 수 있다
      • 모든 비교 연산을 반대로 설정하면 된다
    • 이렇게 만들어진 힙을 최소 힙(min heap) 이라고 한다.

힙 연산

원소 삽입

힙의 불변성을 고려하면서 살펴보자

먼저, 완전 이진 트리를 유지해야 한다.

• 새 원소를 삽입하려면 단순히 배열의 맨 마지막 위치에 원소를 추가하면 된다
  • 마지막 레벨이 꽉 차있다면 새로운 레벨을 추가하여 노드를 추가한다

그리고, 모든 노드는 자식 노드보다 더 큰 값을 가지고 있어야 한다

• 새로운 원소를 트리의 맨 마지막 위치에 추가한 후에는 이 조건이 성립되지 않을 가능성이 생긴다
  • 이를 해결하기 위해 새로 삽입한 원소의 부모 노드와 값을 비교하고, 만약 부모 노드가 더 작으면 서로 교환한다.
  • 여전히 새 원소가 새 부모 노드보다 큰 값을 가질 수 있으므로, 교환 작업을 반복해야 한다.

• 완전 이진 트리의 높이는 최대 log N이므로, 시간 복잡도는 O(log N)으로 표현할 수 있다.

원소 삭제

• 힙에서는 가장 큰 원소만 삭제할 수 있다.(최대 힙 기준)
  • 다른 원소에는 직접 접근할 수 없기 때문
• 최대 원소는 항상 루트에 존재하므로, 루트 노드를 삭제해야 한다.
• 루트를 삭제할 경우, 어느 노드를 이용하여 루트를 대체할 것인지 결정해야 한다.

이를 위해

1. 루트 노드와 트리의 맨 마지막 노드를 서로 교환한다.
2. 마지막 노드를 삭제한다

• 다만 최대 원소는 삭제했지만, 루트 위치에서 부모 노드가 자식 노드보다 커야 한다는 불변성을 만족하지 못하게 된다

이를 위해

1. 루트 노드와 두 자식 노드를 서로 비교하여 그 중 더 큰 노드와 교환한다.
2. 서브 트리에 대해서도 노드 교환 작업을 재귀적으로 반복한다

• 교환 작업의 최대 횟수는 트리의 높이와 같으므로, 원소 삭제의 시간 복잡도는 O(lon N)으로 표현할 수 있다

힙 초기화

• 벡터, 리스트, 덱과는 달리 힙은 불변성을 유지해야 하기 때문에 초기화가 간단하지 않다.
  • 힙에 하나씩 원소를 삽입하는 방법이 가장 간단하나, O(Nlog N)의 시간 복잡도를 가지며 효율적이지 않다.
• 힙 생성 알고리즘(heapification algorithm)을 사용하면 O(N) 시간에 힙을 초기화할 수 있다.
  • 전체 트리의 아래쪽 서브 트리부터 힙 불변 속성을 만족하도록 힙을 업데이트 하는 방식이다
  • 맨 마지막 레벨부터, 한 레벨씩 트리 위로 올라가면서 힙 속성을 만족하도록 트리를 업데이트한다.
  • 이 작업은 O(N)의 시간 복잡도를 갖는다
• 다행히 C++ 표준은 배열 또는 벡터의 반복자를 인자로 받아 힙을 구성하는 std::make_heap() 함수를 제공한다

Example) 중앙값 구하기

• 가장 간단한 방법은 매번 데이터를 받을 때 마다 모든 데이터를 정렬하고, 가운데 원소를 반환하는 것이다.
  • 이러한 작업은 정렬 연산 때문에 O(Nlog N)의 시간복잡도를 갖는다
• 힙을 이용하여 최적화하는 방법을 알아보자
  • 최대 힙, 최소 힙 2개를 이용하여 새로 들어온 데이터가 기존 데이터의 중앙값보다 작으면 최대 힙에 저장하고, 크면 최소 힙에 저장한다
  • 두 힙의 최상단 원소를 이용하여 중앙값을 계산할 수 있게 된다

#include <iostream>
#include <queue>
#include <vector>

struct median
{
    std::priority_queue<int> maxHeap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    void insert(int data)
    {
        if(maxHeap.size() == 0)
        {
            maxHeap.push(data);
            return;
        }

        if(maxHeap.size() == minHeap.size())
        {
            if(data <= get())
                maxHeap.push(data);
            else
                minHeap.push(data);

            return;
        }

        if(maxHeap.size() < minHeap.size())
        {
            if(data > get())
            {
                maxHeap.push(minHeap.top());
                minHeap.pop();
                minHeap.push(data);
            }
            else
                maxHeap.push(data);
            return;
        }

        if(data < get())
        {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(data);
        }
        else
            minHeap.push(data);
    }

    double get()
    {
        if(maxHeap.size() == minHeap.size())
            return (maxHeap.top() + minHeap.top()) / 2.0;
        if(maxHeap.size() < minHeap.size())
            return minHeap.top();

        return maxHeap.top();
    }
};

int main()
{
    median med;

    med.insert(1);
    std::cout << "1 삽입 후 중앙 값 : " << med.get() << std::endl;

    med.insert(5);
    std::cout << "5 삽입 후 중앙 값 : " << med.get() << std::endl;

    med.insert(2);
    std::cout << "2 삽입 후 중앙 값 : " << med.get() << std::endl;

    med.insert(10);
    std::cout << "10 삽입 후 중앙 값 : " << med.get() << std::endl;

    med.insert(40);
    std::cout << "40 삽입 후 중앙 값 : " << med.get() << std::endl;

    return 0;
}