소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 같은 의미로 1과 자기 자신 외에는 약수가 존재하지 않는 수를 말한다.

코딩 테스트에는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제 된다.

소수 구하기 이론

소수를 구하는 대표적인 판별법은 에라토스테네스의 체이다.

에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 배열을 생성한다.
2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 2를 반복한 후에 남은 모든 수를 출력한다.

이러면 배열 범위 내의 수들 중에서 소수들만 구할 수 있다.

에라토스테네스의 체를 사용할 때 시간 복잡도

에라토스테네스의 체를 사용할 때 일반적으로 이중 for문을 사용하며로 시간 복잡도가 O(N^2)이라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))이다. 왜냐하면 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하기 때문이다.

백준 1929 소수 구하기

https://www.acmicpc.net/problem/1929

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int M, N;
    cin >> M >> N;

    vector<int> v(N + 1);

    for(int i = 2; i <= N; i++)
    {
        v[i] = i;
    }
    //제곱근까지만 탐색한다.
    for(int i = 2; i <= sqrt(N); i++)
    {
        if(v[i] == 0)
            continue;
        for(int j = i + i; j <= N; j = j + i)
        {
            v[j] = 0;
        }
    }

    for(int i = M; i <= N; i++)
    {
        if(v[i] == 0)
            continue;
        cout << v[i] << '\n';
    }
}

소수를 구할 때는 바깥 for문의 종료 조건에서 N의 제곱근까지만 탐색한다. 왜냐하면 N의 제곱근이 n일 때 N = a * b를 만족하는 a와 b가 모두 n보다 클 수는 없다. a가 n보다 크다면 b는 n보다 작아야 한다. 즉, N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가진다. 따라서 에라토스테네스의 체로 n 이하의 수의 배수를 모두 제거하면 1부터 N사이의 소수를 구할 수 있다.

백준 1456 거의 소수 구하기

https://www.acmicpc.net/problem/1456

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<bool> arr(10000001, true);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long A, B;
    cin >> A >> B;

    long long answer = 0;

    arr[0] = false;
    arr[1] = false;
    for (long long i = 2; i <= sqrt(10000001); i++)
    {
        if (arr[i] == false)
            continue;
        for (long long j = i + i; j <= 10000001; j += i)
        {
            arr[j] = false;
        }
    }

    for (long long i = 2; i <= 10000001; i++)
    {
        if (arr[i] == true)
        {
            //소수라면 제곱수를 카운트한다.
            long long temp = i;

            //비교 중에 long long의 범위를 넘으면 잘못 카운트가 되기 때문에 이렇게 B에서 나눠서 수를 비교한다.
            while ((double)i <= (double)B / (double)temp)
            {
                if ((double)i >= (double)A / (double)temp)
                {
                    answer++;
                }
                temp *= i;
            }
        }
    }

    cout << answer;

    return 0;
}

이 문제는 몇 번 틀렸다. 틀린 이유는 저 거의 소수를 구하는 부분에서 제곱한 수를 직접 B와 비교를 하게 되면 long long 타입의 표현 범위를 벗어나는 수가 나오면 제대로 카운트를 할 수 없게 된다. 그래서 수의 범위를 벗어나지 않도록 이항 정리를 해주었다. 그러면 범위 안에서 제대로 카운팅이 진행된다.

문제 풀이의 아이디어 자체는 간단했다. 소수를 구하고 소수를 차례로 제곱하면서 A, B의 범위에 그 수가 있는지를 판단하기만 하면 되는 문제였다. 어려웠던 점은 수의 범위를 고려해서 구현을 해야 했다는 점이다.

백준 1747 소수&팰린드롬

https://www.acmicpc.net/problem/1747

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
using namespace std;

int N;

bool isPrime(int data);
bool isParindrom(int data);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    int k = N;
    while (true)
    {
        if (isPrime(k) && isParindrom(k))
        {
            break;
        }

        k++;
    }

    cout << k;

    return 0;
}

bool isPrime(int data)
{
    if (data == 1)
        return false;
    for (int i = 2; i <= sqrt(data); i++)
    {
        if (data % i == 0)
            return false;
    }
    return true;
}

bool isParindrom(int data)
{
    string str = to_string(data);
    int start = 0;
    int end = str.size() - 1;

    while (start < end)
    {
        if (str[start] == str[end])
        {
            start++;
            end--;
        }
        else
            return false;
    }
    return true;
}

이번에는 에라토스테네스의 체를 쓰지 않아보았다. 한 번 틀렸는데, 소수에서 1을 예외처리 하지 않았기 때문이었다.

문제 해결의 과정은 간단히 소수인지 판단 후 펠린드롬 수인지 투포인터로 확인해서 답을 도출해내었다.

Do it! 알고리즘 코딩테스트 C++편 (김종관, 이지스퍼블리싱)

그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다는 단점이 있다.

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

그리디 알고리즘의 핵심 이론

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가서 같은 과정을 반복한다.

그리디 알고리즘을 적용하는 문제는 지역적으로 최적이면 전역적으로도 최적인 문제이다.

백준 11047 동전 개수의 최솟값 구하기

https://www.acmicpc.net/problem/11047

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, K;
int cnt;

int price[10];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;

    for (int i = 0; i < N; i++)
    {
        cin >> price[i];
    }

    //동전 개수의 최소를 구하려면 가장 큰 값의 동전부터 골라서 목표 값을 채우면 된다.
    for (int i = N - 1; i >= 0; i--)
    {
        while ((K - price[i]) >= 0)
        {
            K -= price[i];
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}

매번 빼는 방식으로 구현을 했는데, 모듈러 연산을 활용하면 좀 더 효율적일 것이다.

백준 1715 카드 정렬하기

https://www.acmicpc.net/problem/1715

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    priority_queue<int, vector<int>, greater<int>> pq;

    int data;

    for (int i = 0; i < N; i++)
    {
        cin >> data;
        pq.push(data);
    }

    int data1 = 0;
    int data2 = 0;
    int sum = 0;

    while (pq.size() != 1)
    {
        data1 = pq.top();
        pq.pop();
        data2 = pq.top();
        pq.pop();
        sum += data1 + data2;
        pq.push(data1 + data2);
    }

    cout << sum;

    return 0;
}

이 문제는 핵심 아이디어만 뽑아 낸다면 쉽게 구현해서 풀 수 있는 문제다.

카드 더미들 중에서 가장 작은 크기의 더미 두 개를 먼저 더하면 최소 비교 수를 구할 수 있다. 그걸 해내기 위해서는 우선순위 큐를 사용하면 된다.

백준 1744 수 묶기

https://www.acmicpc.net/problem/1744

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    priority_queue<int, vector<int>, greater<int>> minus;
    priority_queue<int, vector<int>, less<int>> plus;

    int sum = 0;
    bool zeroFlag = false;

    for (int i = 0; i < N; i++)
    {
        int data;
        cin >> data;

        if (data == 0)
            zeroFlag = true;
        else if (data == 1)
            sum += data;
        else if (data > 1)
            plus.push(data);
        else if (data < 0)
            minus.push(data);
    }

    int data1 = 0;
    int data2 = 0;
    while (plus.size() > 1)
    {
        data1 = plus.top();
        plus.pop();
        data2 = plus.top();
        plus.pop();

        sum += data1 * data2;
    }

    if (plus.size() == 1)
        sum += plus.top();

    while (minus.size() > 1)
    {
        data1 = minus.top();
        minus.pop();
        data2 = minus.top();
        minus.pop();

        sum += data1 * data2;
    }

    if (minus.size() == 1)
    {
        if(!zeroFlag)
            sum += minus.top();
    }

    cout << sum;

    return 0;
}

이 문제는 입력 값을 1보다 큰 수/1/0/음수 이 네 종류의 카테고리로 분류해서 처리해야 한다. 1보다 큰 수는 큰 순서대로 2개씩 짝 지어서 수를 묶으면 최대 수가 된다. 홀수개라면 마지막 하나 남는 건 그냥 더하면 된다. 1은 절대 수를 묶으면 안 된다. 최대가 될 수 없기 때문이다. 그냥 1은 바로 더해준다. 0은 그냥 무시할 수 있지만, 0이 적어도 하나가 있는지를 체크해야 한다. 왜냐하면 음수가 홀수개가 들어와서 하나가 남는 경우 그 하나의 음수와 0을 묶어서 음수 덧셈을 막아야 최대값이 나오기 때문이다. 음수는 음수끼리 곱하면 양수이기 때문에 가장 작은 음수 순서대로 2개씩 묶어서 곱해주면 된다. 마지막 남은 음수는 0이 있다면 날리고, 없다면 그냥 더해준다.

백준 1931 회의실 배정

https://www.acmicpc.net/problem/1931

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    //종료 시간을 기준으로 정렬하고, 종료 시간이 같다면 시작 시간 순으로 정렬한다.
    vector<pair<int, int>> times;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int start, end;
        cin >> start >> end;

        times.push_back({ end, start });
    }

    sort(times.begin(), times.end());

    int count = 0;

    int prevEndTime = 0;
    for (int i = 0; i < N; i++)
    {
        if (prevEndTime <= times[i].second)
        {
            count++;
            prevEndTime = times[i].first;
        }
    }

    cout << count;
    return 0;
}

이 문제는 그리디 알고리즘으로 종료 시간이 가장 빠른 회의들을 우선적으로 배치하면 해결할 수 있는 문제이다. 종료 시간을 기준으로 정렬을 수행하고 만일 종료 시간이 같다면 시작 시간 기준으로 정렬을 수행한다. 이전 회의의 종료 시간을 변수로 따로 저장해서 정렬된 벡터를 순회하면서 가능한 회의들을 카운팅해주면 된다.

백준 1541 잃어버린 괄호

https://www.acmicpc.net/problem/1541

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

vector<string> split(string input, char delimiter);
int mySum(string a);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int answer = 0;
    string example;
    cin >> example;
    vector<string> str = split(example, '-');

    for (int i = 0; i < str.size(); i++)
    {
        int temp = mySum(str[i]);
        if (i == 0)
        {
            answer = answer + temp;
        }
        else
        {
            answer = answer - temp;
        }
    }

    cout << answer << "\n";
    return 0;
}

vector<string> split(string input, char delimiter)
{
    vector<string> result;
    stringstream mystream(input);
    string splitdata;

    while (getline(mystream, splitdata, delimiter))
    {
        result.push_back(splitdata);
    }
    return result;
}

int mySum(string a)
{
    int sum = 0;
    vector<string> temp = split(a, '+');

    for (int i = 0; i < temp.size(); i++)
    {
        sum += stoi(temp[i]);
    }
    return sum;
}

문제를 푸는 아이디어는 간단하지만 문자열 처리가 좀 더 귀찮았던 문제이다. 문자열을 split하는 방법을 잘 숙지해두자.

그리디는 생각보다 어려운 알고리즘은 아닌 것 같다. 문제를 딱 봤을 때 그리디로 풀 수 있겠는데? 하는 직관이 잘 와야하는 것 같다.

공부 자료 : Do it! 알고리즘 코딩테스트 C++편 (김종관, 이지스퍼블리싱)

너비 우선 탐색(BFS, breadth-first search)은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준을 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

너비 우선 탐색은 선입선출 방식으로 탐색하기 때문에 큐를 이용해서 구현한다. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 떄문에 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

너비 우선 탐색의 특징

FIFO 탐색이다. Queue 자료구조를 이용한다.

너비 우선 탐색의 시간 복잡도

O(V + E)

BFS의 핵심 이론

1. BFS를 시작할 때 노드를 정한 후 사용할 자료구조 초기화하기

BFS도 DFS처럼 방문한 노드는 다시 방문하지 않기 때문에 방문 배열이 필요하다. 인접 리스트로 그래프를 표현하는 것도 동일하다. 다른 점은 탐색을 할 때 스택이 아닌 큐를 활용해서 탐색한다.

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다. 이때 방문 배열을 체크해서 이미 방문한 노드는 큐에 삽입하지 않는다. 또, 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

3. 큐 자료구조에 값이 없을 때까지 반복

1, 2를 큐가 빌 때까지 반복한다.

백준 1260번 DFS와 BFS

https://www.acmicpc.net/problem/1260

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

static int N;
static int M;
static int V;
static vector<vector<int>> graph;
static vector<bool> visited;
queue<int> bfsQueue;

void DFS(int v);
void BFS(int v);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> V;
    graph.resize(N + 1);

    visited = vector<bool>(N + 1, false);

    //인접 리스트 셋팅
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    //모든 인접 노드들을 순서에 맞게 정렬한다.
    for (int i = 0; i < N + 1; i++)
        sort(graph[i].begin(), graph[i].end());

    DFS(V);

    for (int i = 0; i < N + 1; i++)
        visited[i] = false;

    cout << endl;
    BFS(V);
    return 0;
}

void DFS(int v)
{
    if (visited[v])
        return;

    visited[v] = true;
    cout << v << " ";

    for (int i : graph[v])
    {
        if (!visited[i])
        {
            DFS(i);
        }
    }
}

void BFS(int v)
{
    if (visited[v])
        return;

    bfsQueue.push(v);
    visited[v] = true;
    cout << v << " ";

    while (!bfsQueue.empty())
    {
        int front = bfsQueue.front();
        bfsQueue.pop();

        for (int element : graph[front])
        {
            if (visited[element]) continue;
            bfsQueue.push(element);
            visited[element] = true;

            cout << element << " ";
        }
    }
}

이 문제는 단순히 DFS와 BFS를 구현할 수 있으면 풀 수 있는 문제였다! 약간 신경 쓸 것은 내림차순 순서대로 다음 노드를 선택해야 한다는 것이다.

백준 2178번 미로 탐색하기

https://www.acmicpc.net/problem/2178

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, M;
vector<vector<int>> visited;
vector<string> board;
queue<pair<int, int>> bfsQueue;

int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

void BFS(int x, int y);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    visited.resize(N);
    for (int i = 0; i < N; i++)
    {
        visited[i].resize(M);
        fill(visited[i].begin(), visited[i].end(), 1);
    }

    board.resize(N);

    for (int i = 0; i < N; i++)
    {
        cin >> board[i];
    }


    BFS(0, 0);

    cout << visited[N - 1][M - 1];
    return 0;
}

void BFS(int x, int y)
{
    if (visited[y][x] != 1) 
        return;

    bfsQueue.push({ x, y });

    while (!bfsQueue.empty())
    {
        auto pair = bfsQueue.front();
        bfsQueue.pop();

        //갈 수 있는 곳 탐색
        for (int i = 0; i < 4; i++)
        {
            int nextX = pair.first + dx[i];
            int nextY = pair.second + dy[i];

            //범위 체크
            if (nextX < 0 || nextX > M - 1 || nextY < 0 || nextY > N - 1)
                continue;
            //방문한 적이 있다면 스킵
            if (visited[nextY][nextX] != 1)
                continue;
            if (board[nextY][nextX] == '0')
                continue;

            visited[nextY][nextX] = visited[pair.second][pair.first] + 1;
            bfsQueue.push({ nextX, nextY });
        }
    }
}

이제 미로가 나오고 최단 거리를 구하는 문제이기 때문에 BFS가 먼저 떠올랐다. DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 가능한 모든 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문이다.

무난하게 BFS 알고리즘을 써서 방문 조건과 인덱스 조건을 잘 걸러내서 답을 구할 수 있었다. 과거에 풀었던 내용을 보니까. 지금 풀이처럼 동적으로 자료구조의 크기를 입력 값에 따라서 넣는 것이 아니라. 그냥 전역에 가능한 최대의 수치로 자료구조 크기를 확보하는 방법도 있었다. 메모리가 부족하지 않다면 활용하는 것이 좋아보였다.

백준 1167번 트리의 지름 구하기

https://www.acmicpc.net/problem/1167

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int V;

vector<vector<pair<int, int>>> graph;
void bfs(int start);
vector<int> dist;
queue<int> bfsQueue;
vector<bool> visited;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> V;
    graph.resize(V + 1);
    dist.resize(V + 1, 0);
    visited.resize(V + 1, false);

    for (int i = 0; i < V; i++)
    {
        int v;
        cin >> v;
        while (true)
        {
            int node;
            cin >> node;
            if (node == -1)
                break;

            int weight;
            cin >> weight;
            graph[v].push_back({ node, weight });
        }
    }

    // 임의의 노드 하나를 잡고 bfs를 수행한 후 최장 거리의 노드를 구한다.
    bfs(1);

    pair<int, int> maxNode = { 0, 0 };
    for (int i = 0; i < dist.size(); i++)
    {
        if (maxNode.second < dist[i])
        {
            maxNode.second = dist[i];
            maxNode.first = i;
        }
    }

    fill(dist.begin(), dist.end(), 0);
    fill(visited.begin(), visited.end(), false);

    // 그 노드에서 다시 최장 거리를 구하면 그게 트리의 지름이다.
    bfs(maxNode.first);
    pair<int, int> answerNode = { 0, 0 };
    for (int i = 0; i < dist.size(); i++)
    {
        if (answerNode.second < dist[i])
        {
            answerNode.second = dist[i];
            answerNode.first = i;
        }
    }
    cout << answerNode.second;

    return 0;
}

void bfs(int start)
{
    bfsQueue.push(start);

    while (!bfsQueue.empty())
    {
        int node = bfsQueue.front();
        bfsQueue.pop();

        visited[node] = true;

        for (int i = 0; i < graph[node].size(); i++)
        {
            if (visited[graph[node][i].first] == true)
                continue;
            //거리 업데이트
            dist[graph[node][i].first] = dist[node] + graph[node][i].second;
            bfsQueue.push(graph[node][i].first);
        }
    }
}

이 문제를 풀기 위해서는 트리에 대한 이해가 있어야 한다. 트리는 모든 노드가 서로 유일한 경로로 연결이 되어 있고, 싸이클이 존재하지 않는 그래프이다. 트리의 지름을 구하기 위해서는 이 아이디어가 있어야 한다. 아이디어가 가장 중요했던 문제이다.

임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.

임의의 A 노드에서 가장 멀리 있는 B노드는 트리의 지름의 양 끝 노드 중 하나라는 의미이다.

그 아이디어만 잘 염두해두면 로직은 간단하다.

공부 자료 : Do it! 알고리즘 코딩 테스트 C++ (김종관, 이지스퍼블리싱)

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

깊이 우선 탐색의 특징

스택이나 재귀 함수로 구현한다.

시간 복잡도

O(V + E)

V : 노드 수 E : 간선 수

DFS 문제를 풀어보기 전에 우선 그래프를 표현하는 방법부터 알아본다.

그래프 표현의 3가지 방법

그래프를 코드 상에 표현하는 방법은 크게 3가지가 있다.

에지 리스트(edge list)

에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.

에지 리스트로 가중치 없는 그래프 표현

가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하기 때문에 배열의 열은 2개면 충분하다. 노드를 배열에 저장하여 에지를 표현하므로 에지 리스트라고 한다.

1에서 2로 가는 에지는 [1,2]로 표현한다. 0번째 열에 출발 노드, 1번째 열에는 도착 노드를 저장하면 그래프를 표현할 수 있다. 무방향 그래프의 경우에는 [1,2]와 [2,1]은 같은 에지일 것이다. 가중치가 필요하다면 열을 3개로 해서 마지막 열에 해당 에지의 가중치 정보를 저장하면 된다.

에지 리스트는 구현하기 쉽지만, 특정 노드와 관련된 에지를 탐색하기는 쉽지 않다. 에지 리스트는 노드 사이의 최단 거리를 구하는 벨만-포드나 최소 신장 트리를 찾는 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.

인접 행렬(adjacency matrix)

인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 에지 리스트와는 다르게 노드 중심으로 그래프를 표현한다.

인접 행렬에서 각 배열의 값은 가중치를 의미한다. 가중치가 없는 그래프라면 1로 표현한다. 1에서 2로 가는 에지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다.

인접 행렬을 이용한 그래프 구현은 쉽다. 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있다는 장점이 있다. 하지만 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 시간 복잡도가 인접 리스트에 비해 느리고 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.

인접 리스트(adjacency list)

C++의 인접 리스트는 이차원 벡터로 그래프를 표현한다. 자료형은 문제의 조건에 맞게 설정한다.

다른 방법에 비해 인접 리스트로 그래프를 표현하는 것은 복잡하다. 하지만 노드와 연결된 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율성이 좋아서 메모리 초과 에러도 발생하지 않는다. 이러한 장점으로 인해 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.

DFS로 돌아와서 DFS는 재귀함수를 이용하므로 스택 오버 플로에 유의해야 한다. DFS를 응용해서 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

DFS의 핵심 이론

DFS는 한 번 방문한 노드는 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기

DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기가 있다. 시작 노드를 스택에 삽입함과 동시에 방문 배열에 방문 표시를 해준다.

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입한다.

3. 스택 자료구조에 값이 없을 때까지 반복한다.

앞의 1,2 작업을 스택 자료구조에 값이 없을 때까지 반복한다. 이 때, 한 번 방문한 노드는 방문 배열을 참고해서 스택에 다시 삽입하지 않는 것이 핵심이다.

백준 11724번 문제

https://www.acmicpc.net/problem/11724

#include <iostream>
#include <vector>
using namespace std;

static vector<vector<int>> graph;
static vector<bool> visited;
void DFS(int v);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int v, e;

    cin >> v >> e;
    graph.resize(v + 1);
    visited = vector<bool>(v + 1, false);

    //간선 개수만큼 인접 리스트에 간선 정보 추가
    for (int i = 0; i < e; i++)
    {
        int start, end;
        cin >> start >> end;

        graph[start].push_back(end);
        graph[end].push_back(start);
    }

    int answer = 0;

    //시작 노드 넣기
    for (int i = 1; i < v + 1; i++)
    {
        //방문하지 않은 노드라면 시작 노드로 넣고 DFS를 시작한다.
        if (!visited[i])
        {
            answer++;
            DFS(i);
        }
    }


    cout << answer;
    return 0;
}

void DFS(int v)
{
    //방문 했으니 그냥 리턴
    if (visited[v])
    {
        return;
    }
    //방문 표시
    visited[v] = true;

    //인접 리스트의 노드들 방문
    for (int i : graph[v])
    {
        //방문하지 않은 것만 방문
        if (visited[i] == false)
        {
            DFS(i);
        }
    }
}

방문하지 않는 노드를 시작 노드로 해서 여러 번 DFS를 해서 연결된 노드의 개수를 구하면 되는 문제였다. 그래프를 표현하고 그래프 탐색 알고리즘을 짤 수 있다면 풀 수 있는 문제이다.

백준 2023번 문제

https://www.acmicpc.net/problem/2023

#include <iostream>
#include <vector>
using namespace std;

void DFS(int num, int j);
bool isPrime(int num);
static int N;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    // 2, 3, 5, 7로 시작
    // 그 뒤는 무조건 홀수만 소수의 가능성이 있다.
    DFS(2, 1);
    DFS(3, 1);
    DFS(5, 1);
    DFS(7, 1);

    return 0;
}


void DFS(int num, int j)
{
    if (j == N)
    {
        if (isPrime(num))
        {
            cout << num << '\n';
            return;
        }
    }

    for (int i = 0; i < 10; i++)
    {
        //짝수 가지치기
        if (i % 2 == 0)
            continue;
        if (isPrime(num * 10 + i))
            DFS(num * 10 + i, j + 1);
    }
}

bool isPrime(int num)
{
    if (num < 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;

    for (int i = 3; i <= num / 2; i++)
    {
        if (num % i == 0) 
            return false;
    }
    return true;
}

이 문제는 혼자 못 풀었는데 그 이유는 DFS 문제인데 그래프를 표현할 필요가 없어서 DFS는 그래프랑 같이 쓰는 느낌이라고 생각해서 DFS를 어떻게 적용해야할지 감이 안 왔기 때문이다. 이 문제에서 DFS를 써야하는 당위는 오름차순으로 신기한 소수를 출력해야 하기 때문인 것 같다. 0부터 탐색을 시작해서 DFS를 돌면 제일 작은 수 부터 출력하게 되고 모든 경우를 탐색할 수 있다. 중간에 문제에 알맞게 가지치기를 해서 필요없는 연산을 줄였다.

백준 13023번 문제

https://www.acmicpc.net/problem/13023

#include <iostream>
#include <vector>
using namespace std;

static int N;
static int M;
static vector<vector<int>> graph;
static vector<bool> visited;

void DFS(int v, int depth);
bool answer = false;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    graph.resize(N);

    visited = vector<bool>(N, false);

    //인접 리스트 셋팅
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 0; i < N; i++)
    {
        DFS(i, 1);
        if (answer == true) 
            break;
    }

    cout << (int)answer;
    return 0;
}

void DFS(int v, int depth)
{
    if (visited[v])
    {
        return;
    }

    //방문 체크
    visited[v] = true;

    if (depth >= 5)
    {
        answer = true;
        return;
    }

    for (int i : graph[v])
    {
        if (!visited[i])
        {
            DFS(i, depth + 1);
        }
    }
    //다른 노드를 시작으로 다시 반복해야 하니까 false로 바꿔준다.
    visited[v] = false;
}

이 문제는 맨 밑에 visited[v] = false;를 깜박해서 틀렸다. 우선 이 문제의 핵심은 DFS의 깊이가 5인 탐색이 존재하는지이다. 이를 탐색하려면 모든 노드를 시작으로 해서 각각 DFS를 해야하는데 한 번 돌고나서 방문 배열을 초기화하지 않아서 틀렸다. 여러 번 돌아야 할 때는 방문 배열을 잊지말고 되돌려주자.

공부 자료 : Do it! 알고리즘 코딩 테스트 (김종관, 이지스퍼블리싱)

그런 상황을 어떻게 구현하는지에 대해 알아본다.

std::condition_variable

표준 C++ 라이브러리는 두 개의 condition_variable의 구현을 제공한다.

std::condition_variable과 std::condition_variable_any이다.

전자는 무조건 std::unique_lock<std::mutex>와 함께 사용해야 한다. 후자는 어떤 락 타입과도 함께 동작할 수 있다. std::mutex뿐만 아니라 사용자 정의 뮤텍스나 다른 락 타입(std::shared_lock, std::scoped_lock 등)을 사용할 수 있다. 더 유연하지만, 속도가 약간 느릴 수 있다.

대부분 추가적인 유연성이 필요하지 않기 때문에 std::condition_variable을 사용한다.

예제 코드

#include <iostream>
#include <mutex>
#include <vector>
#include <thread>
#include <condition_variable>

std::mutex mut;
std::queue<data_chunk> data_queue; //두 스레드 사이에 데이터를 전달하기 위한 큐
std::condition_variable data_cond;

//데이터 준비 스레드의 엔트리 함수
void data_preparation_thread()
{
    while(more_data_to_prepare())
    {
        data_chunk const data = prepare_data();
        //데이터가 준비 되면 데이터 준비 스레드는 lock_gurad를 사용해서
        //플래그를 보호하는 뮤텍스를 잠그고 데이터를 큐에 push한다.
        std::lock_gurad<std::mutex> lk(mut);
        data_queue.push(data);
        //푸시 후 이 조건 변수에 대해 대기하고 있는 다른 스레드에게 이벤트를 알린다.
        data_cond.notify_one();
    }
}

//데이터 처리 스레드의 엔트리 함수
void data_processing_thread()
{
    while(true)
    {
        //std::unique_lock을 써야 하는 이유는 
        //중간에 임의로 unlock을 해야 하기 때문이다.

        //일단 뮤텍스를 잠그고 wait함수에서 람다로 전달된 조건을 검사한다.
        std::unique_lock<std::mutex> lk(mut);
        //조건을 검사해서 true가 반환되면 곧바로 리턴한다.
        //false라면 unlock을 하고 다시 알림이 올 때까지 스레드는 대기한다.
        //여기서 unlock을 하는 이유는 그래야 다른 스레드가 
        //다시 그 공유 자원에 대한 lock을 취득할 수 있기 때문이다.

        //조건 부분은 람다가 아니어도 호출 가능한 객체면 다 가능하다.
        //조건 확인은 wait 함수 내부에서 여러 번 동작할 수 있고,
        //항상 뮤텍스를 잠근 상태에서 확인한다.
        data_cond.wait(lk, []{return !data_queue.empty();});
        data_chunk data = data_queue.front();
        data_queue.pop();
        lk.unlock();
        process(data);
        if(is_last_chunk(data))
            break;
    }
}

std::condition_varialbe에서 다른 스레드를 깨우는 방법은 두 가지가 있다. 대기 중인 스레드 하나를 깨우는 방법은 위의 예제에서처럼 notify_one()함수를 호출하는 것이다. 대기 중인 모든 스레드에게 알림을 주는 것은 notify_all()함수를 호출하면 된다.

대기 스레드가 단 한 번만 대기할 경우, 즉 조건이 참일 때 이 조건 변수를 다시는 기다리지 않을 경우, 조건 변수는 동기화 메커니즘의 최상의 선택이 아닐 수 있다. 이런 시나리오에서는 future가 더 적합할 수 있다.

future를 사용하면 이제 task 기반의 비동기 프로그래밍을 추상화해서 쉽게 처리할 수 있게 된다. 여기서 중요한 것은 task에서 나온 데이터가 caller로 안전하게 전달되고 시그널을 잘 보내는지이다. 이는 future와 promise라는 도구를 활용해 C++에서 구현할 수 있다.

Future를 사용한 일회성 이벤트 대기

C++ 라이브러리는 일회성 이벤트를 future라는 매커니즘으로 모델링한다. 스레드가 특정 일회성 이벤트를 기다려야 하는 경우, 어떻게든 이 이벤트를 나타내는 future를 얻는다. 그런 다음 future를 폴링하여 이벤트가 발생했는지 확인할 수 있다. 다른 작업을 수행하는 도중에서 future를 확인할 수 있다. future에는 연관된 데이터가 있을 수도 있고 없을 수도 있다. 이벤트가 발생하고 future가 준비되면 future를 재설정할 수 없다.

future는 비동기 작업에 대한 결과를 받을 수 있는 객체라고 할 수 있다.

항공에서 비행기를 타기위해 기다리는 승객 스레드가 여러 명 있다고 해보자. 비행기가 출발 준비가 될 때까지 승객들은 기다린다. 어떤 승객은 계속 기다리고 있을 수 있고, 다른 승객은 준비 알림이 올 때까지 카페에서 뭘 먹고 있을 수도 있고, 면세점에서 물건을 사고 있을 수도 있을 것이다. 이를 코드로 나타내면 다음과 같다.

void wait_for_flight1(flight_number flight)
{
    //future를 사용해서 flight에 알림이 올 때까지 기다린다.
    std::shared_future<boarding_information> boarding_info =
    get_boarding_info(flight);
    //get()함수는 future가 아직 알림을 받지 못 했으면 스레드를 대기 시킨다.
    board_flight(boarding_info.get());
}
void wait_for_flight2(flight_number flight)
{
    std::shared_future<boarding_information> boarding_info =
    get_boarding_info(flight);
    //바로 get()호출하지 않고 다른 일을 하면서 주기적으로 준비가 되었는지 
    //체크하다가 준비가 되면 get()을 한다.
    while(!boarding_info.is_ready())
    {
        eat_in_cafe();
        buy_duty_free_goods();
    }
    board_flight(boarding_info.get());
}

이 예제에서는 여러 승객 스레드가 하나의 이벤트를 기다리고 모든 스레드는 동시에 알림을 받아야 하고 모두 동일한 탑승 정보기 필요하기 때문에std::shared_future를 사용했다.

여러 스레드가 아니라 하나의 스레드만 대기를 한다면std::unique_future를 사용하는 것이 적합하다. std::shared_future에 비해 오버헤드가 낮을 가능성이 있기 때문이다. 또한 std::shared_future은 future와 관련된 데이터를 복사만 할 수 있는 반면에 std::unique_future는 데이터를 이동하여 future에서 대기 코드로 소유권을 이전할 수 있다. 이는 이동이 복사보다 비용이 싼 경우 유용하다.

지금까지 대기 스레드 관점에서 본 future들이었다.

이벤트를 트리거 하는 스레드는 어떻게 모델링해야 할까? future를 준비하려면 어떻게 해야 할까? 연관 데이터는 어떻게 전달할까?

C++ 표준은 이런 질문에 대한 답을 두 가지 함수 템플릿인 std::packaged_task<>와 std::promise<>의 형태로 제공한다.

std::packaged_task<>

이 함수 템플릿은 future를 이 함수 호출 결과에 연결한다. 함수가 완료되면 future는 준비가 되고, 연관된 데이터는 함수의 반환값이 된다.

이는 자체 포함 작업 집합으로 세분화할 수 있는 전체 작업에 이상적이다. 이러한 작업은 함수로 작성되고, std::packaged_task를 사용하여 각 작업이 future와 연관되도록 패키징된 다음 별도의 스레드에서 실행될 수 있다. 그런 다음 구동 함수는 이러한 하위 작업의 결과를 처리하기 전에 future를 기다릴 수 있다.

쉽게 말해 하나의 큰 작업을 쪼개서 여러 작업으로 만들고 그 여러 작업이 끝나면 그걸 취합하는 시나리오에서 유용하다는 것이다.

말이 다소 어려워서 GPT에게 설명을 요청했다.

std::packaged_task는 특정 작업(함수)을 포장(package) 해서, 나중에 실행하거나 다른 스레드로 전달한 뒤 결과를 가져올 수 있도록 만드는 도구입니다. 쉽게 말해, 작업을 "포장 상자" 안에 넣어두고 필요할 때 실행할 수 있게 해주는 역할을 합니다.

예제 코드

#include <iostream>
#include <thread>
#include <future>

int calculateSum(int a, int b) {
    return a + b;
}

int main() {
    // 1. 작업을 포장 (packaged_task)
    std::packaged_task<int(int, int)> task(calculateSum);

    // 2. 미래 결과를 가져올 수 있는 열쇠 (future)
    std::future<int> result = task.get_future();

    // 3. 포장된 작업을 다른 스레드에서 실행
    std::thread t(std::move(task), 10, 20); // calculateSum(10, 20) 실행

    // 4. 결과 가져오기
    std::cout << "Result: " << result.get() << '\n';

    t.join();
    return 0;
}

std::promise

std::promise는 C++에서 값을 약속(promise) 하고, 나중에 그 값을 전달(deliver) 할 수 있도록 만들어주는 도구이다. 쉽게 말해, "나중에 결과를 줄게!" 라고 약속하고, 결과가 준비되면 전달하는 역할을 한다.

비유로 설명

📩 편지와 우체통 비유

1. 우체통 설치: std::promise는 값을 전달할 수 있는 우체통을 설치한다. 이 우체통에는 편지를 꺼내 볼 수 있는 열쇠(std::future)가 함께 제공된다.
2. 값을 약속: 편지를 우체통에 넣기로 약속(set_value)한다. 즉, 값을 나중에 줄 것을 약속한다.
3. 결과 전달: 우체통에 편지를 넣는다.
4. 결과 확인: 다른 곳에서 열쇠(std::future)를 사용해 우체통에서 편지를 꺼내 내용을 확인한다.

#include <iostream>
#include <thread>
#include <future>

void deliverResult(std::promise<int> promise) {
    // 3초 후 값을 약속
    std::this_thread::sleep_for(std::chrono::seconds(3));
    promise.set_value(42); // 값을 전달
}

int main() {
    // 1. 우체통 설치 (promise)
    std::promise<int> promise;

    // 2. 열쇠(future) 받기
    std::future<int> result = promise.get_future();

    // 3. 값을 약속 (다른 스레드에서)
    std::thread t(deliverResult, std::move(promise));

    // 4. 결과 확인
    std::cout << "Waiting for result...\n";
    std::cout << "Result: " << result.get() << '\n';

    t.join();
    return 0;
}

이런 추상화된 task 기반의 비동기 함수 호출 메커니즘은 내부적으로 결국 조건 변수와 뮤텍스, 힙 할당, 해제가 이뤄지기 때문에 성능이 중요한 코드에서는 잘 사용되지 않는다고 한다.

std::lock_guard

간단한 RAII 클래스이다. 락을 즉시 획득하고, 임의로 락 해제는 불가능하다.

항상 락이 유지되어야 하는 간단한 임계 구역에 적합하다.

성능

세 락 객체 중 가장 가볍다. 오버헤드가 거의 없다.

언제 사용?

간단하게 락만 필요할 때 사용한다. 락 해제/재획득 같은 유연성이 필요 없을 때 사용한다.

std::unique_lock

std::lock_guard보다 유연한 락 관리 도구이다.

락을 바로 거는 것이 아닌 지연된 락 획득이 가능하다. (defer_lock) 락을 명시적으로 해제/재획득 가능하다. 타이밍 제한(예: try_lock_for) 지원한다. 조건 변수와 함께 사용 가능.

성능

std::lock_guard보다 무겁지만, 유연성 때문에 필수 상황에 적합하다.

언제 사용?

락 해제/재획득이 필요하거나 조건 변수(std::condition_variable)를 사용할 때. 타임아웃 기능이 필요할 때.

std::mutex mtx;
void critical_section() {
    std::unique_lock<std::mutex> lock(mtx, std::defer_lock); // 바로 락을 걸지 않음
    lock.lock();  // 필요할 때 락을 획득
    // 락이 걸린 상태에서 실행
    lock.unlock(); // 락 해제
    lock.lock();  // 다시 락 획득 가능
}

std::shared_lock

윈도우 API의 SRWLock과 같은 기능이다.

다중 읽기 락을 제공하는 도구이다.

읽기 전용 락으로, 여러 스레드가 동시에 읽을 수 있다.

쓰기 락(std::unique_lock)과 함께 사용할 때, 쓰기 락이 우선권을 가진다. 예를 들어 A 스레드가 읽기 락을 얻어서 작업 중에 있고 B 스레드는 읽기 락을 대기하고 있고 C 스레드는 쓰기 락으로 대기를 하고 있다면, A가 읽기 락을 반환하면 C 스레드가 먼저 락을 선점한다는 의미이다.

락 해제/재획득 가능하다.

성능

읽기 락은 상대적으로 가볍다. 하지만 쓰기 락이 필요한 경우 성능이 낮아질 수 있음.

언제 사용?

데이터를 여러 스레드가 읽기만 하고, 쓰기는 드물게 발생하는 경우. 읽기와 쓰기가 명확히 구분되는 시나리오에서 쓴다.

std::shared_mutex smtx;
void read_data() {
    std::shared_lock<std::shared_mutex> lock(smtx); // 읽기 락
    // 데이터를 읽는 동안 다른 읽기 작업은 허용됨
}

void write_data() {
    std::unique_lock<std::shared_mutex> lock(smtx); // 쓰기 락
    // 쓰기 중에는 읽기/쓰기 모두 차단됨
}

뮤텍스를 통한 공유 자원 보호

mutex는 mutual exclusive(상호 배제)에서 따온 말이다. std::mutex는 멀티 스레드 프로그래밍에서 공유 자원에 대한 여러 스레드의 접근을 제한하는 데 사용된다. 오직 한 스레드만이 std::mutex의 lock을 취득해서 공유 자원을 적절히 처리하고 작업이 끝나면 unlock을 해서 다른 스레드도 공유 자원을 사용할 수 있도록 한다.

사용법은 여전히 간단하다. std::mutex 객체를 생성해서 공유 자원에 대한 처리의 시작과 끝에 lock()과 unlock() 함수를 호출해주면 된다.

#include <iostream>
#include <mutex>
#include <vector>
#include <thread>

std::mutex g_lock;
int g_data = 0;
void func()
{
    for(int i = 0; i < 100000; i++)
    {
        g_lock.lock();
        g_data++;
        g_lock.unlock();
    }
}

int main()
{
    std::vector<std::thread> threads;

    for(int i = 0; i < 3; i++)
    {
        threads.push_back(std::thread(func));
    }

    for(int i = 0; i < 3; i++)
        threads[i].join();

    std::cout << g_data << std::endl;
    return 0;
}

이렇게 lock()과 unlock()함수를 명시적으로 사용해줄 수 있다. 하지만 이 방법은 프로그래머가 lock()을 했다면 반드시 unlock()을 해줘야 하는 것을 까먹지 않아야만 한다는 단점이 있다.

명시적인 lock, unlock의 실수 가능성

처음 락을 배우는 사람이면 어떤 바보가 lock하고 unlock을 안 하겠어?(내가 그랬다) 하겠지만 코드가 복잡해지거나 lock()과 unlock()사이에 return이 되는 코드가 있거나 예외같은 문제가 있는 경우 unlock()을 수행하지 못 할 수도 있다. 이런 모든 경우에 맞게 꼼꼼히 unlock()하는 것은 생각보다 쉽지 않은 일이다. (데드락에 걸려서 디버깅을 몇 번 해보고 나면 느끼게 된다.)

std::lock_guard

이에 대한 해결책으로 std::lock_guard를 활용할 수 있다. std::lock_guard는 mutex 객체를 생성자에서 받아서 생성자에서 해당 mutex의 lock()을 호출한다. 그리고 소멸자에서 mutex의 unlock()을 호출한다.

객체의 생성자, 소멸자에서 자동으로 lock을 관리해주니 스코프를 벗어나게 되도 unlock()을 하지 않았다는 실수를 걱정을 할 필요가 없어진다.

#include <iostream>
#include <mutex>
#include <vector>
#include <thread>

std::mutex g_lock;
int g_data = 0;

void func()
{
    for(int i = 0; i < 100000; i++)
    {
        std::lock_guard guard(g_lock);
        g_data++;
    }
}

int main()
{
    std::vector<std::thread> threads;

    for(int i = 0; i < 3; i++)
    {
        threads.push_back(std::thread(func));
    }

    for(int i = 0; i < 3; i++)
        threads[i].join();

    std::cout << g_data << std::endl;
    return 0;
}

스레드 시작과 대기

스레드는 해당 스레드에서 실행할 작업을 지정하는 std::thread 객체를 초기화 하며 시작한다. 스레드 엔트리 함수를 단순한 함수로 전달할 수도 있고, 함수 호출 연산자가 있는 인스턴스(함수 객체)를 전달할 수도 있고, 람다를 전달할 수도 있다. 엔트리 함수를 전달하지 않고 std::thread를 생성하면 그냥 인스턴스만 생성할 뿐 스레드가 생성되지 않는다.

#include <thread>

void threadFunc()
{
    std::cout << "Hello" << std::endl;
}

int main()
{
    //스레드 시작
    std::thread myThread(threadFunc);
    //스레드 대기
    myThread.join();

    return 1;
}

간단하게 위 코드처럼 스레드를 생성하고 생성된 스레드가 종료될 때까지 대기 시킬 수 있다. join()을 하지 않으면 main의 return을 만나 스레드가 진행 중인데도 프로그램이 종료될 수 있다. 그리고 join()을 호출하게 되면 해당 std::thread에서 생성한 스레드와 연관이 끊기게 된다. (std::thread 인스턴스와 생성된 스레드는 다른 것이다.) 이런 사실은 당연하다. join에서 리턴된다는 것이 해당 스레드가 종료되었다는 것이기 때문이다.

한 std::thread 인스턴스에 대해 두 번 join()을 수행하면 에러가 발생한다. 그래서 join()을 호출할 수 있는 인스턴스인지 확인하려면 joinable()함수를 호출해서 체크를 하면 된다.

std::thread는 복사는 불가능 하고 이동 연산은 가능하다. 이는 하나의 스레드 관리를 여러 스레드가 복사해서 가지고 있다면 말이 안 되기 때문에 unique_ptr처럼 단일 소유만 가능하게 구현한 것이다.

detach

스레드를 백그라운드에서 돌게 하기 위해서 std::thread 객체와 의도적으로 연관을 끊는 detach()함수도 있다. detach는 std::thread오브젝트에서 스레드를 분리하는 개념이다. 이렇게 분리를 하게 되면 std::thread 오브젝트가 정리되어도 스레드의 실행은 유지된다.

detach를 사용하는 상황:

1. 백그라운드 작업으로 실행되는 스레드가 완전히 독립적이고, 결과를 확인하거나 제어할 필요가 없는 경우.
2. 메인 스레드가 스레드 종료를 기다리지 않고 다른 작업을 계속해야 할 때.

하지만 거의 대부분의 경우에는 detach를 하지 않는다. 스레드를 스레드 오브젝트에서 분리하게 되면 그 스레드를 더 이상 제어하거나 관련 정보를 얻을 수 없기 때문이다. 그래서 일반적으로 detach를 하지 않고 전역 스코프에 std::thread 객체를 둬서 로컬 범위 바깥으로 가도 std::thread가 소멸되지 않도록 한다.

스레드 ID

각각의 스레드는 ID를 가진다.

std::this_thread::get_id();

이렇게 현재 스레드의 id를 얻을 수도 있다.

스레드에 매개변수 전달하기

매우 간단하다. 그냥 std::thread 생성자에 추가적으로 인자를 전달하면 된다.

void func(int a)
{
    std::cout << a << std::endl;
}

int main()
{
    int num = 29;
    std::thread t1(func, num);
    t1.join();
}

매개변수가 한 개 이상이어도 그냥 뒤에 쭉 이어서 넣어주면 된다.

만약 엔트리 함수의 매개변수가 참조라면 std::ref를 써서 인자를 전달해야 한다.

void func(int a, std::string& str)
{
    std::cout << a << ' ' << str <<std::endl;
}

int main()
{
    int num = 29;
    std::string str = "hello";
    std::thread t1(func, num, std::ref(str));
    t1.join();
}

참조를 인자로 전달할 때 신경 써야하는 점이 있다. 그것은 해당 변수의 생명 주기이다.

void func(int i, std::string const& s);

void foo(int some_param)
{
    char buffer[1024];
    sprintf(buffer, "%d", some_param);
    std::thread(func, 3, buffer);
}

이렇게 지역 변수인 buffer를 전달하면 배열은 첫 번째 원소의 포인터이기 때문에 전달된 인자들은 복사가 된다. 새로 생성된 스레드의 실행이 func 함수를 실행시키기 전에 buffer가 가리키는 내용이 소멸했을 수도 있다. 그러면 넘겨진 buffer는 char* 타입이기 때문에 새로운 스레드가 func를 호출할 때 매개변수 s의 타입인 std::string으로 타입 변환이 이뤄지는데 그 전에 foo함수가 끝나버리면 buffer가 가리키는 값이 쓰레기 값이 되어버려서 정의되지 않는 동작이 발생한다.

이런 문제를 피하기 위해서는 buffer를 미리 std::string객체로 초기화 시켜서 인자로 전달하면 된다. std::thread(func, 3, std::stirng(buffer));

구조는 "변경"과 관련이 깊습니다. 구조가 없는 코드는 여러 시스템들이 얽히고 섥혀있는 스파게티의 형태로 코드가 흐릅니다. 그렇게 되면 나중에 코드를 수정해야 할 때, 하나의 변수를 바꾸려고 하면 다른 모든 부분이 틀어지게 될 수가 있게 됩니다. 정말 최악입니다. 저런 상황에서 유지보수를 하기는 너무 어렵습니다. 복잡도가 너무 높죠

그래서 좋은 소프트웨어 구조가 필요합니다. 변경이 쉽도록 하기 위해서죠. 구조가 잡혀있는 코드는 고칠 때 전체 프로그램을 이해해야 하는 것이 아니라 각 시스템들이 잘 분리되어 있기 때문에 고치려는 부분과 연관된 작은 부분만 이해하고 코드를 고칠 수 있습니다. 고친 후 테스트를 진행한 후 코드를 보기 좋게 정리까지 해주면 됩니다!

좋은 소프트웨어의 구조의 비용

득이 있으면 실이 있는 법이죠 좋은 구조는 거저 생기지 않습니다. 지속적으로 유지보수를 하면서 구조를 유지하려는 노력이 필요합니다. 그리고 구조를 유지하는 이유는 결국 변경에 대비하는 것입니다. 하지만 변경될 가능성이 거의 없는 프로젝트라면 구조를 유지하려고 노력한 의미가 많이 떨어지는 것이죠. 예를 들어 미래에 변경 될 것이라 예측해서 확장성 있게 추상화도하고 복잡성을 늘리다보면 디버깅도 어려워지고 유지보수에 시간이 더 걸리게 됩니다. 이런 확장성에 취하게 되면 코드에 인터페이스, 가상함수, 추상화 등등 온갖 구조가 붙으면서 오히려 이해하기 어려운 코드가 될 수도 있습니다. 아이러니하죠?

또 성능 이슈도 있습니다. 코드를 유연하게 만드는 많은 패턴이 포인터, 메시지, 가상함수같은 메커니즘에 의존하게 되는데 이러한 메커니즘은 런타임에 비용이 요구됩니다. 예를 들면 가상 함수의 경우 virtual table을 한 번 참조해야 하는 비용이 있습니다.

성능을 위한 최적화는 가정을 제한할 수록 선호합니다. 예를 들어 적이 256보다 적게 나온다고 확신한다면 적의 ID를 1byte로 압축할 수 있습니다.

결론

소프트웨어 구조의 장단점을 간단히 알아보았는데요, 결국 중요한 것은 밸런스를 잘 잡는 것입니다. 프로그램을 유연하게 만들려고 하면 성능이 낮아질 수 있고, 성능을 높히려 최적화하면 유연하지 못하게 됩니다. 역시나 결국은 트레이드 오프!

제가 읽고 있는 책의 저자는 이렇게 말합니다.

경험상으로는 재미있는 게임을 최적화하는 것이 최적화된 게임을 재미있게 만드는 것보다 훨씬 쉽다. 처음에는 코드를 유연하게 유지하다가 기획이 확실해진 다음에 추상 계층을 제거해서 성능을 높이는 타협안도 있다.

제가 느끼기에는 딱 이렇게 하라는 지침은 없으며, 지금 작성하고 있는 코드가 유연성이 필요한지를 먼저 판단하고 그 판단에 맞는 코드를 작성하면 좋을 것같다고 생각합니다.

참고

게임 프로그래밍 패턴 (로버트 나이스트롬, 한빛 미디어)

링크가 너무 길어서 여기에 올립니다.

가변 길이 템플릿은 템플릿 인자의 수를 가변적으로 받아야 할 때 사용할 수 있는 템플릿이다.

간단하게 여러 인자를 받아서 출력하는 프로그램을 가변 길이 템플릿을 활용해서 구현해본다.

바로 코드를 보자

#include <iostream>
#include <string>

//재귀적인 함수의 베이스 케이스를 나타내는 함수
template <typename T>
void print(T arg)
{
    std::cout << arg << std::endl;
}

//템플릿 인자에 ...이 들어가면 템플릿 파라미터 팩이라고 함.
template <typename T, typename... Types>
void print(T arg, Types... args)    //이렇게 함수 인자에 ...을 함수 파라미터 팩이라고 함.
{
    std::cout << arg << ", ";
    print(args...);
}

int main()
{
    print(23, 1.4, "hello");
    return 0;
}

위의 두 템플릿 함수 print로 가변인자 템플릿을 만들 수 있다. print(23, 1.4, "hello")를 호출할 때 무슨 일이 일어나는지 알아보자.

우선 두 번째 print 함수에서는 템플릿 인자로 typename... Types를 받고 있다. 이는 템플릿 파라미터 팩이라고 하며 이것은 0개 이상의 템플릿 인자를 나타낸다. 그리고 함수 파라미터에도 Types...이라는 타입의 args 매개변수가 존재하는데 이것은 함수 파라미터 팩이라고 하며 템플릿 파라미터 팩과 마찬가지고 0개 이상의 매개변수를 나타낸다.

즉 print(23, 1.4, "hello")를 호출하면 컴파일러는 매개 변수를 보고 두 번째 함수를 선택한다. 그렇게 되면 두 번째 함수에서의 print에서 맨 앞에 인자 23은 arg에 들어가고 나머지 1.4과 "hello"는 args에 들어간다. 그러므로 arg를 출력하고 재귀적으로 나머지 args를 다시 print()함수로 호출한다.

그렇게 쭉 가다가 마지막으로 "abc"하나만 두 번째 print에서 재귀적으로 호출되면 그 때는 컴파일러가 첫 번째 print함수를 선택해서 "abc"를 출력하고 끝낸다. C++에서는 파라미터 팩이 없는 함수를 우선적으로 선택한다는 규칙 때문이다.

이렇게 하면 원하는 만큼 인자를 넣어서 출력을 할 수 있게 된다.

1. 도메인 -> IP

도메인을 IP 구조체로 바꿀 때 옛날 책을 보면 gethostbyname이라는 함수를 사용하라고 합니다. 하지만 이 함수는 유니코드를 지원하지 않고 너무 옛날 방식이기 때문에 MSDN에서도 해당 함수를 보면 이렇게 써있습니다.

참고 : gethostbyname 함수는 getaddrinfo 함수를 도입하여 더 이상 사용되지 않습니다. Windows Sockets 2 애플리케이션을 만드는 개발자는 gethostbyname 대신 getaddrinfo 함수를 사용해야 합니다.

그러므로 getaddrinfo 함수를 쓰면 되는 것이죠. 우선 GetAddrInfo 함수를 쓰려면 일단 ws2tcpip.h 헤더를 인클루드 해줘야 합니다.

이 함수는 유니코드도 지원하고 ANSI 문자열도 지원합니다. GetAddrInfo 함수를 쓰면 알아서 환경에 따라 변환해 줍니다. 우선 유니코드 기반으로 쓰는 것을 설명하겠습니다.

함수 형태는 다음과 같습니다.

INT WSAAPI GetAddrInfoW(
  [in, optional] PCWSTR          pNodeName,
  [in, optional] PCWSTR          pServiceName,
  [in, optional] const ADDRINFOW *pHints,
  [out]          PADDRINFOW      *ppResult
);

1) pNodeName : 여기에 도메인 이름을 넣습니다. 2) pServiceName : 문자열로 표시되는 서비스 이름 또는 포트 번호를 포함하는 NULL로 종료된 유니코드 문자열에 대한 포인터입니다. 3) pHints : 호출자가 지원하는 소켓 유형에 대한 힌트를 제공하는 addrinfoW 구조체에 대한 포인터입니다. 4) ppResult : 호스트에 대한 응답 정보를 포함하는 하나 이상의 addrinfoW 구조체의 연결된 목록에 대한 포인터입니다. 5) 반환값 : 성공 시 0을 반환한다.

매개 변수만 보면 뭔가 복잡해 보이는데요. 2번 매개변수와, 3번 매개변수는 저도 솔직히 잘 이해가 되지 않습니다.

그래도 제 목적은 도메인 이름으로 IP주소를 얻는 것이므로 그 방법만 알아보려합니다.

#include <ws2tcpip.h>

int main()
{
    //GetAddrInfo 함수를 쓰기 위한 ADDRINFOW구조체 이 함수를 쓰는 이유는 매개변수로 버퍼를 받고, 유니코드를 지원하기 때문이다.
    //이 구조체는 링크드 리스트 형태로 한 도메인에 설정된 여러 아이피 정보를 물고있다.
    ADDRINFOW* addrInfo;
    //소켓 주소 구조체 선언
    SOCKADDR_IN* sockAddr;

    GetAddrInfo(L"www.naver.com", L"0", NULL, &addrInfo)
    //소켓 주소 구조체로 형변환 해서 원하는 도메인에 해당하는 ip를 가지는 소켓 주소 구조체를 얻을 수 있다.
    sockAddr = (SOCKADDR_IN*)(addrInfo->ai_addr);

    //GetAddrInfo 함수는 FreeAddrInfo 함수를 호출해서 리소스를 반환해줘야 한다.
    FreeAddrInfo(addrInfo);
}

이런 식으로 쓸 수 있습니다.

참고로 하나의 도메인에는 여러 IP 주소가 할당될 수 있습니다. 그래서 addrInfo 구조체는 리스트의 형태로 여러 addrInfo 구조체가 이어져 있습니다. addrInfo의 멤버에는 ai_next라는 멤버가 있는데 이 멤버로 다음 addrInfo 구조체로 가서 여러 IP에 접근할 수 있습니다.

그리고 잊어서는 안되는 FreeAddrInfo 함수! 반드시 호출해서 메모리 낭비를 막아야 합니다!

2. IP 문자열 -> IN_ADDR 형태

이번에는 IP를 문자열로 바꾸는 방법을 알아봅시다.

흔히 서버 주소를 세팅할 때 IN_ADDR으로 변환해야 하는 경우가 있습니다. 코드를 보시죠

SOCKADDR_IN serverAddr;
memset(&serverAddr, 0, sizeof(serverAddr));
serverAddr.sin_family = AF_INET;
InetPton(AF_INET, L"192. 168.0.3", &serverAddr.sin_addr);
serverAddr.sin_port = htons(SERVERPORT);

이렇게 InetPton 함수로 IP 문자열을 IN_ADDR 형태로 변환해줄 수 있습니다. 이 때 네트워크 바이트 배열로도 바뀌므로 htonl을 할 필요도 없습니다.

3. IN_ADDR 형태 -> IP 문자열

InetNtop() 함수로 쉽게 할 수 있습니다.

WCHAR serverIPStr[16] = { 0 };
InetNtop(AF_INET, &serverAddr.sin_addr, serverIPStr, 16);

버퍼 하나 준비해주시고 인자로 넘기면 그 버퍼에 IP 문자열이 들어가게 됩니다.

소켓 프로그래밍 지식이 어느정도 있어야 이해하실 수 있습니다.

백로그 큐(backlog queue)

backlog queue는 listen 상태의 서버 소켓에 연결하고자 하는 클라이언트의 요청들이 저장되는 곳입니다.

조금 더 구체적으로 보면 클라이언트 애플리케이션에서 connect() 함수를 호출하면 여러 계층의 활약으로 무사히 서버 호스트로 접속 요청이 도착하게 되고 TCP 계층에서 이 요청을 받아서 backlog queue에 넣어주게 됩니다.

이제 서버 측 애플리케이션에서 accept() 함수가 호출 되면 이 backlog queue에서 접속 요청을 하나씩 꺼내와서 새로운 소켓에 그 요청 내용을 참조하여 소켓 내부에 필요한 내용을 저장하게 되고 그 소켓을 반환해서 반환된 소켓으로 클라이언트와 통신할 수 있게 되는 것입니다.

TCP 연결은 언제 이루어지는 것일까

TCP 연결은 언제 이루어지는지 궁금해지더라구요. connect() 함수를 호출하면 TCP 연결이 일단은 이루어지는 것일까? 아니면 accept() 함수가 호출이 되고 새로운 소켓이 반환이 되어야 연결이 이루어지는 것일까? 하는 의문이 생겼습니다.

그 의문을 해소하려면 3 way handshaking이 언제 발생하는지를 알아야 합니다. 3 way handshaking은 TCP의 최초 연결 동작을 말합니다. 이에 대한 자세한 내용은 구글에 검색하면 많이 나오니 모르시는 분은 이해하고 넘어와 주세요.

아무튼 3 way handshaking은 3번의 패킷 교환이 이루어지므로 이 패킷을 캡처하면 언제 발생하는지 알 수 있습니다.

그래서 패킷 캡처 툴인 와이어 샤크를 이용해 보았습니다.

우선 클라이언트 측에서 connect()를 호출하고 서버 측에서는 accept()를 호출하지 않고 패킷을 캡처해보았습니다.

그랬을 때 3 way handshaking 패킷을 확인 할 수 있었습니다.

그러므로 accept() 함수의 호출과 TCP 연결은 무관하다는 사실을 알 수 있습니다. accept() 함수는 그저 backlog queue에 있는 연결되어 있는 클라이언트 요청 데이터를 꺼내서 연결된 소켓을 반환해주는 역할을 하는 것입니다.

backlog queue의 크기

listen() 함수를 호출할 때 매개변수로 개발자가 직접 backlog queue의 크기를 설정할 수 있습니다.

listen(listenSocket, SOMAXCONN);

listen() 함수의 두 번째 매개변수가 바로 backlog queue의 크기입니다. SOMAXCONN은 무슨 값일까요? MSDN의 listen() 함수 설명을 보면 다음과 같이 설명합니다.

SOMAXCONN으로 설정하면 소켓을 담당하는 기본 서비스 공급자가 백로그를 적절한 최대 값으로 설정합니다. https://learn.microsoft.com/ko-kr/windows/win32/api/winsock2/nf-winsock2-listen

적절한 최대 값이라... 한 번 알아봐야겠습니다.

알아보는 과정은 다음과 같습니다.

1. 서버 프로그램에서는 listen() 과정까지만 해서 특정 포트를 LISTENING 상태로 만들어 놓고 accept()는 하지 않습니다. 이 때 backlog 매개 변수로 SOMAXCONN을 전달합니다.
2. 클라이언트 프로그램에서는 많은 수의 connect() 함수를 호출하면 계속해서 backlog queue에 연결 요청이 쌓이게 되고 가득 차게 되면 SOCKET_ERROR가 발생할 것입니다.
3. 언제 SOCKET_ERROR가 발생하는지 보면 기본 서비스 공급자가 설정한 적절한 최대 값을 알 수 있을 것입니다.

클라이언트 측 소켓을 1024개 만들어서 connect()를 호출해 보았더니 200에서 에러가 터졌습니다. 그러므로 적절한 backlog queue의 크기는 200이었던 것입니다.

더 많은 연결 요청이 짧은 시간에 들어온다고 하면 이 backlog queue의 크기를 더 늘리는 법도 알아야 할 것 같습니다.

backlog queue 크기 늘리기

MSDN 문서를 보면 이 크기를 늘리는 방법이 나와있습니다.

SOMAXCONN_HINT(N)(여기서 N은 숫자)로 설정하면 백로그 값은 N이 되고 범위 내에서 조정됩니다(200, 65535). SOMAXCONN_HINT 사용하여 SOMAXCONN에서 백로그를 가능한 것보다 큰 값으로 설정할 수 있습니다.

문서를 보면 65535개가 최대치인 것 같습니다. (포트의 한계 때문인 것 같습니다.) 65535개의 연결요청이 잘 들어가는지 확인해 보도록 하겠습니다.

65540개 정도의 클라이언트 소켓을 만들어서 connect를 해본 결과 16333에서 오류가 발생했습니다. 그런데 에러코드를 보니 기존에 backlog queue가 가득 차서 발생한 오류와는 다른 WSAENOBUF 에러가 발생했습니다. 처음에는 아마 내부 송 수신 버퍼 공간이 없어서 그런 것 같다고 생각했습니다. 그런데 x64의 메모리는 부족하지 않을 것 같다는 생각이 들었습니다.

계속되는 고민...

계속 어떻게 하면 65535개의 연결 요청을 backlog queue에 넣을까 고민을 하다가... 65535개... 최대 포트 수... 혹시 동적 포트를 다 써서 그런 것일까?라는 실마리를 찾게 되었습니다. 그래서 구글에 동적 포트의 범위를 검색했더니 49152 - 65535였습니다. 두 수의 차는 16383... 어딘가 16333과 굉장히 유사한 숫자...!! (50개는 다른 프로세스에서 쓰고 있는 듯 합니다.)

결론을 내리자면 내부 송,수신버퍼의 공간이 부족한 것이 아닌 65535개의 클라이언트 소켓에 할당할 포트가 부족했던 것이었습니다.

제 목표는 backlog queue에 65535개의 연결 요청을 넣어보는 것입니다. 어떻게 부족한 포트 문제를 해결할까 고민했습니다.

고민을 계속 하다가 모르겠어서 그냥 침대에 누워서 자려고 하는데... 정말 스치듯이 connect()한 클라이언트 소켓을 바로 closesocket()해버리면 동적 포트를 재사용할 수 있지 않을까? 하는 아이디어가 떠올랐습니다.

저는 바로 책상 앞에 앉아 노트북을 켜고 실험을 해보았습니다.

우선 클라 소켓을 closesocket()을 했을 때 서버 측의 backlog queue에 들어가 있던 연결 요청이 사라지지는 않을까? 하는 의문을 해결해야 했습니다. (사실 연결 요청이 사라지지 않을 것이라고 예측을 했습니다. 연결 요청을 그냥 큐에 넣은 건데 close 했다고 실시간으로 큐의 내용을 지우진 않을 것 같았거든요.)

실험으로 2개의 클라이언트 소켓으로 connect() 후 바로 closesocket()을 했습니다. 서버측에서는 Sleep(5000)으로 5초 정도 지연시켜주고 accept()를 호출해서 요청을 2번 받는지 확인 했더니. 두 요청을 다 잘 받았습니다.

그러므로 closesocket()으로 포트를 재활용할 수 있겠습니다.

또다른 문제 Time_Wait 상태

희망을 얻은 것도 잠시 TCP 연결을 해제 할 때는 closesocket()을 하면 소켓은 바로 사라지지 않고 Time_wait 상태가 됩니다. 즉 바로 사라지지 않고 60초 정도 기다렸다가 사라집니다. 그 기다리는 동안에는 해당 포트를 사용할 수 없는 것이죠.

하지만 구글링한 결과 소켓에 Linger 옵션을 설정하면 time_wait을 상태를 없앨 수 있다는 사실을 알게 되었습니다. https://sunyzero.tistory.com/198

목표 달성

그렇게 time_wait을 없애고 포트를 재사용하니

드디어 backlog queue에 65535개의 연결 요청을 넣을 수 있었습니다!!

마치며

backlog queue에 최대로 넣을 수 있는 요청을 알아보고 실제로 넣어보는 과정이 끝났습니다.

네트워크 이론을 배우고 그 이론을 토대로 실험하고 검증하는 과정이 괴로우면서도 즐거웠습니다.

앞으로 게임 서버 공부를 하면서 backlog queue에 대해서는 잊지 않을 것 같습니다.

감사합니다.

TCP(Transmission Control Protocol)는 신뢰성 있는 데이터 전송을 위한 프로토콜로, 데이터를 패킷 단위로 나누어 전송하고, 수신 측에서 패킷의 손실이나 손상 여부를 확인하고 복구하는 기능을 제공합니다. 이를 위해 TCP는 ACK(Acknowledgment)와 SEQ(Sequence Number)라는 개념을 사용합니다.

ACK(Acknowledgment)

ACK는 수신 측이 데이터를 정상적으로 받았음을 송신 측에 알려주는 역할을 합니다. 송신 측에서 데이터를 전송하면 수신 측은 ACK를 생성하여 송신 측으로 전송합니다. ACK 번호는 송신 측으로부터 받은 데이터의 바로 다음에 기대되는 데이터의 순서 번호입니다. ACK 번호는 수신 측이 받은 마지막 바이트의 순서 번호에 1을 더한 값입니다. ACK를 받은 송신 측은 해당 ACK 번호 이전의 데이터는 정상적으로 수신되었다고 간주하고, 다음 데이터를 전송할 준비를 합니다.

SEQ(Sequence Number)

SEQ는 TCP 세그먼트에 포함되는 데이터의 순서 번호입니다. 데이터는 일련의 세그먼트로 나뉘어 전송되기 때문에, 수신 측은 이 순서 번호를 통해 패킷의 순서를 파악하고 조립합니다. SEQ 번호는 송신 측에서 데이터를 세그먼트로 나눌 때 각 세그먼트의 시작 위치를 식별하기 위해 사용됩니다. SEQ 번호는 수신 측으로부터 받은 마지막 바이트의 순서 번호에 1을 더한 값입니다.

결론

ACK와 SEQ는 TCP 헤더에 포함되어 전송되며, 송신 측과 수신 측 간에 신뢰성 있는 데이터 전송을 위한 정확한 순서 제어와 오류 복구를 가능하게 합니다. 이를 통해 데이터의 손실, 중복, 순서 오류 등을 신속하게 감지하고 처리하여 신뢰성 있는 데이터 전송을 보장합니다.

삽입 정렬은 특수한 경우에 매우 빠르게 동작하는 정렬 알고리즘 입니다.

우선 핵심 논리는 다음과 같습니다.

정렬이 된 영역과 정렬이 되지 않은 영역을 나눠서 정렬이 되지 않은 영역에서 정렬이 된 영역으로 하나씩 이동 시킨다.

삽입 정렬의 구현

void InserSort(int arr[], int n)
{
    int i, j;
    int insData;

    for(i = 1; i < n; i++)
    {
        insData = arr[i];

        for(j = i-1; j >= 0; j--)
        {
            if(arr[j] > insData)
                arr[j+1] = arr[j];
            else
                break;
        }
        arr[j+1] = insData;
    }
}

바깥쪽 for문

i가 1에서 시작하는데 이는 맨 앞의 인덱스 0을 무시하기 위함이다. 맨 앞의 요소는 혼자이니까 정렬이 되었다고 간주할 수 있기 때문이다.

안쪽 for문

j = i - 1인 이유는 정렬된 영역의 오른쪽 끝에서부터 시작하기 때문이다. 즉 i는 정렬시킬 요소의 인덱스고 i -1인 j 는 정렬된 영역의 가장 오른쪽에 있는 인덱스이다. 루프를 돌며 정렬 영역의 왼쪽으로 이동하면서 정렬 시킬 요소의 위치를 찾아준다. 찾았다면 안쪽 for문을 빠져나와서 arr[j+1] = insData; 로 적절한 위치에 값을 넣어준다.

삽입 정렬의 성능 평가

삽입 정렬의 빅-오는 O(N^2)이다. 완전 구린 알고리즘이라고 생각할 수 있지만 삽입 정렬은 거의 정렬된 배열에서는 누구보다 빠른 알고리즘이다. 왜냐하면 이미 정렬이 되었다면 반복문에서 break;를 타고 어떠한 연산도 하지 않고 바로 정렬되지 않은 부분만 처리해주기 때문이다.

선택 정렬은 버블 정렬보다 쉬운 알고리즘이다. 하지만 역시 쉬운 만큼 성능이 별로다.

선택 정렬은 정렬 순서에 맞게 하나씩 선택해서 맨 앞으로 보내는 방식의 정렬이다.

선택 정렬의 구현

void SelSort(int arr[], int n)
{
    int i, j;
    int maxIdx;
    int temp;

    for(i = 0; i < n-1; i++)
    {
        maxIdx = i;

        for(j = i + 1; j < n; j++)
        {
            if(arr[j] > arr[maxIdx])
            {
                maxIdx = j;
            }
        }

        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp;
    }
}

안쪽 for문

안쪽 for문에서는 정렬의 우선순위가 가장 높은 인덱스를 돌면서 찾는다.

바깥 for문

안쪽 for문에서 찾은 최대 인덱스를 참조해서 맨 앞으로 보내는 스왑 연산을 진행한다.

선택 정렬의 성능 평가

선택 정렬은 빅-오 O(N^2)이다... 바람직한 성능은 아니다.

버블 정렬은 아주 쉬운 알고리즘이여서 쉽게 이해하기도 좋고 구현하기도 좋다. 단점으로는 성능이 좋지 못하다는 점이다.

버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 한 번 루프를 돌 때 가장 큰 값을 맨 뒤로 보내고 자리를 확정짓는다. 그리고 이를 반복한다.

두 데이터를 비교해서, 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꾼다.

왜 이름이 버블 정렬일까? 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어졌다.

버블 정렬의 구현

void BubbleSort(int arr[], int n)
{
    int i, j;
    int temp;

    for(i = 0; i < n - 1; i++)
    {
        for(j = 0; j < (n - i) - 1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

여기서 헷갈릴 수 있는 부분에 대해 부연 설명하겠다.

바깥 for문의 범위

바깥 for문을 봤을 때 범위가 n-1인데, 왜냐하면 예를 들어 4개의 데이터를 정렬해야 하는 경우에 3번만 돌아도 마지막 하나는 구지 연산할 필요없이 남은 자리에 들어가기 때문에 마지막 하나의 경우를 빼주므로 n - 1의 범위를 갖는 것이다.

안쪽 for문의 범위

안쪽 for문의 범위는 더 헷갈릴 수 있는데 잘 생각해 보면 간단하다. 버블 정렬의 핵심 논리는 가장 큰 값을 맨 뒤로 보내줘서 바깥 for문을 한 번 돌 때마다 맨 뒤에 자리가 확정이 나는 것이다. 따라서 i를 빼주는 것이다. 이미 확정이 난 자리를 반복해서 연산할 필요가 없으니까. 1을 빼주는 이유는 바깥 for문의 범위처럼 마지막 하나의 경우는 구지 연산할 필요가 없기 때문이다.

버블정렬의 성능

알고리즘의 성능을 따질 때는 시간 복잡도와 공간 복잡도를 고려한다.

하지만 알고리즘의 성능에는 시간 복잡도가 공간 복잡도에 비해 더 큰 영향을 미치므로 주로 시간 복잡도만 고려한다.

그럼 시간 복잡도는 어떻게 알 수 있을까 빅오 표기법으로 파악할 수 있다. 데이터의 수에 따른 연산의 횟수를 파악해야 한다.

정렬 알고리즘에서 핵심 연산은 두 가지이다.

1. 비교 연산
2. 이동 연산

두개의 연산 중 중요한 것은 어떤 것일까? 당연히 비교 연산이다. 비교연산은 무조건 하지만 이동 연산은 비교 연산의 결과에 따라 할 수도 있고 안 할 수도 있기 때문이다. 즉 이동 연산은 비교 연산에 종속적이다.

그러므로 비교 연산의 횟수로 시간 복잡도를 파악할 수 있을 것이다. 버블 정렬의 경우 4개의 데이터가 있을 때 3번 -2번 - 1번 이런 식으로 등차 수열 적으로 연산이 진행된다. 그러므로 등차수열의 합 공식으로 연산의 횟수를 알 수 있다.

(n^2 - n) / 2이므로

Big-O 표기법으로 보면 O(N^2)이 된다.

따라서 버블 정렬은 굉장히 성능이 좋지 못한 알고리즘임을 알 수 있다.

하지만 활용과 구현의 용이함이 있기 때문에 의미가 없다고 할 수는 없는 알고리즘이다.

우선순위 큐는 이름에서 알 수 있듯이 큐와 관련이 있는 자료구조이다. 당연하겠지만 큐와 큰 차이가 있다.

'큐'의 핵심은 다음과 같다.

선입선출(FIFO) 들어온 순서대로 나간다.

• enqueue: 큐에 데이터를 삽입한다.
• dequeue: 큐에 데이터를 꺼낸다.

우선순위 큐의 핵심은 다음과 같다.

들어온 순서에 상관없이 우선순위가 높은 데이터가 먼저 나간다.

• enqueue: 우선순위 큐에 데이터를 삽입한다.
• dequeue: 우선순위가 높은 데이터를 꺼낸다.

우선순위 큐의 우선순위는 프로그래머가 결정할 일이다.

숫자가 큰 것이 우선순위가 높을 수도 있고 작은 것이 높을 수도 있고 특정한 조건에 의해서 우선순위가 결정될 수도 있는 일이다.

참고로 우선순위가 같은 데이터도 존재할 수 있다.

우선순위 큐의 구현 방법

우선 순위 큐를 구현하는 방법은 다음 세 가지로 구분할 수 있다.

1. 배열 기반 구현
2. 연결 리스트 기반 구현
3. 힙을 이용한 구현

배열이나 연결 리스트를 이용하면 우선순위 큐를 아주 간단하게 구현할 수 있다.

배열로 구현하는 경우

우선순위 큐를 배열로 구현하는 경우는 두 가지 단점이 존재한다.

데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반한다.

이는 배열의 대표적인 단점이라 할 수 있다. 하지만 더 큰 문제는 다음과 같다.

삽입 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

이는 우선순위가 가장 낮은 데이터를 저장하는 경우 최악이다.

연결 리스트로 구현하는 경우

연결리스트로 구현하는 경우는 배열의 첫 번째 단점은 없지만, 두 번째 단점이 남아있다...

결론

우선순위 큐는 배열도 연결 리스트도 아닌 '힙'이라는 자료구조를 이용해 구현하는 것이 일반적이다.

힙(Heap)의 소개

힙은 '이진 트리'이되 '완전 이진 트리'이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값이 가장 커야한다.

힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이므로 이를 활용하면 쉽게 우선순위 큐를 구현할 수 있을 것이다. 참고로 힙은 무엇인가를 쌓아 놓은 더미와 흡사하여 지어진 이름이다. 영단어 heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 지닌다.

힙의 구현과 우선순위 큐의 완성

힙의 구현은 곧 우선순위 큐의 완성으로 이어진다. 하지만 둘은 같은 개념은 아니다. 힙은 우선순위 큐의 구현에 딱 어울리는, 완전 이진 트리의 일종이다.

힙에서의 데이터 저장 과정

새로운 데이터는 우선순위가 제일 낮다는 가정하에서 '마지막 위치'에 저장한다. 그리고 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔준다. 바뀐 다음에도 계속해서 부모 노드와 비교한다. 제대로 된 위치를 찾을 때까지.

힙에서의 데이터 삭제 과정

힙에서 데이터의 삭제는 우선순위가 가장 높은 요소를 꺼내는 행위이다. 즉 루트 노드를 삭제하는 것이다. 루트 노드를 삭제하는 것은 어렵지 않다. 문제는 삭제 후에도 힙의 구조를 유지해야 한다는데 있다.

마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다.

힙의 구현은 연결리스트? 배열?

힙을 구현하는데는 일반적으로 배열을 사용한다. 왜냐하면 연결리스트를 기반으로 힙을 구현하면 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않기 때문이다. 하지만 배열은 간단히 추가할 수 있기 때문에 힙은 배열로 주로 구현한다.

배열을 기반으로 힙을 구현하는데 알아야 할 것

노드에 고유의 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다.

참고로 구현의 편의를 위해서 인덱스 0의 위치는 사용하지 않는다.

왼쪽과 오른쪽 자식과 부모 노드의 인덱스 값을 얻는 방법을 알아보자.

• 왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 * 2
• 오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값* 2 + 1
• 부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2 (정수형 나눗셈)

이후 힙 자료구조를 구현해 보았다.