Computer Science & Engineering

//Trie

struct trie {
    struct node {
        bool terminal;
        map<char, node*> child;
        node() : terminal(false) {}
    };

    node* head = new node();

    void store(string str) {
        store_dfs(str, 0, head);
    }

    bool find(string str) {
        return find_dfs(str, 0, head);
    }

private:
    void store_dfs(string str, int n, node* now) {
        if(n == str.size()) {
            now->terminal = true;
            return;
        }

        if(now->child.find(str[n]) == now->child.end()) 
            now->child[str[n]] = new node();

        store_dfs(str, n + 1, now->child[str[n]]);
        now->terminal = false;
    }

    bool find_dfs(string str, int n, node* now) {
        if(str.size() == n) return true;
        if(now->terminal) return false;

        bool ret = false;
        for(auto nxt : now->child) {
            if(str[n] == nxt.first)
                ret |= find_dfs(str, n + 1, nxt.second);
        }

        return ret;
    }
};




//Aho-Corasic
struct Aho_Corasic {

    struct node {
        char now_char;
        map<char, node*> child;
        node* fail;
        bool terminal;

        node(char c) {
            now_char = c;
            terminal = false;
        }
        
        ~node() {
        	for(auto it = child.begin(); it != child.end(); it++) delete it->second;
        }
    };

    node* root;
    
    Aho_Corasic() {
        root = new node(' ');
        root->fail = root;
    }

    ~Aho_Corasic() {
        delete root;
    }

    void insert(string str) {
        node* now = root;
        for(char c : str) {
            if(now->child.find(c) == now->child.end()) now->child[c] = new node(c);
            now = now->child[c];
        }
        now->terminal = true;
    }

    void failure() {
        queue<node*> q;
        root->fail = root;
        q.push(root);

        while(!q.empty()) {
            node* now = q.front(); q.pop();
            for(auto it = now->child.begin(); it != now->child.end(); it++) {
                node* next = it->second;
                char next_char = next->now_char;
                if(now == root) {
                    next->fail = root;
                }
                else {
                    node* failnode = now->fail;

                    while(failnode != root && failnode->child.find(next_char) == failnode->child.end()) {
                        failnode = failnode->fail;
                    }
                    if(failnode->child.find(next_char) != failnode->child.end()) {
                        failnode = failnode->child[next_char];
                    }

                    next->fail = failnode;
                }
                if(next->fail->terminal) next->terminal = true;
                q.push(next);
            }
        }
    }

    bool query(string str) {
        node* now = root;

        for(char c : str) {
            while(now != root && now->child.find(c) == now->child.end())
                now = now->fail;
            if(now->child.find(c) != now->child.end()) now = now->child[c];
            if(now->terminal) return true;
        }

        return false;
    }
};



//최소 공통 조상(LCA);
const int MN = 100001;
vector<int> g[MN];

int h[MN];
int dp[20][MN];

void dfs(int n, int prev) {
    for(int nxt : g[n]) {
        if(nxt == prev) continue;
        h[nxt] = h[n] + 1;
        dp[0][nxt] = n;
        dfs(nxt, n);
    }
}

int LCA(int a, int b) {
    if(h[a] < h[b]) swap(a, b);

    int gap = h[a] - h[b];

    for(int i = 0; i < 20; i++)
        if(gap & (1 << i))
            a = dp[i][a];

    if(a == b) return a;

    for(int i = 19; i >= 0; i--)
        if(dp[i][a] != dp[i][b])
            a = dp[i][a], b = dp[i][b];

    return dp[0][a];
}

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

    int N; cin >> N;
    for(int i = 0; i < N-1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    for(int i = 1; i < 20; i++)
        for(int j = 1; j <= N; j++)
            dp[i][j] = dp[i-1][dp[i-1][j]];

    int M; cin >> M;
    while(M--) {
        int a, b; cin >> a >> b;
        cout << LCA(a, b) << '\n';
    }
}

STL priority_queue

    이번 글에는 STL의 <queue> 헤더파일에 존재하는 내부 함수 우선순위 큐를 직접 구현해보았다. priority_queue를 C++ STL 홈페이지(https://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue)에서 찾아볼 경우 다음과 같이 나온다.

초록색 글씨를 보면 선언할 때 변수의 type(class도 가능)을 받고 두 번째 인자로 우선순위 큐를 구성하는 컨테이너, 즉 배열을 선언할 수 있다. 기본값으론 vector를 사용한다. 마지막 인자로 힙을 구성하는 비교 함수 연산자가 있는 class를 포함한다. 기본값인 less는 최대힙을 만들 때 사용한다. 최소힙으로 사용하고 싶을 경우 greater를 사용한다. 다음과 같이 최대힙, 최소힙을 선언할 수 있다.

#include <queue>

priority_queue<int, vector<int>, less<int>> pq; //최대힙
priority_queue<int, vector<int>, greater<int>> pq; //최소힙

우선순위 큐 동작 방식

 우선순위 큐는 힙을 이용한다. FIRST IN FIRST OUT인 queue와 다르게 우선순위가 높은 인자가 우선적으로 나온다. 힙의 push와 pop은 다음과 같이 동작한다. 예시는 5, 6, 3, 7, 10, 4가 순서대로 push될 경우 최대힙이 만들어지는 과정이다.

힙은 언제나 완전 이진트리이다. 동작방식은 다음과 같다.

삽입

• 삽입하려는 값을 트리의 맨 마지막에 넣는다.
• 부모노드와 비교하며 삽입하려는 값이 더 큰 경우 부모노드와 값을 바꾼다.
• 삽입하려는 값보다 큰 값이 나오지 않을 때까지 반복한다.
• 만약 root노드보다 삽입하려는 값이 큰 경우 root노드에 저장한다.

삭제

• 트리의 맨 아래의 맨 오른쪽에 있는 원소인 pivot을 root노드로 위치시킨다.
• 왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 값과 비교한다.
• 자식 노드가 더 큰 경우 자식노드와 값을 바꾼다.
• pivot 값보다 작은 값을 만날 때까지 반복한다.
• 만약 leaf노드까지 도달한 경우 pivot 값을 leaf노드에 저장한다.

우선순위 큐는 위의 과정으로 동작한다. 여기서 비교하는 함수는 선언의 마지막 인자에 있는 class를 이용하여 비교연산을 한다. 

priority_queue 코드 설명

class의 구조와 멤버 변수는 다음과 같다.

template <class T, class CONT = std::vector<T>, class CMP = less<typename CONT::value_type>>
class mypriority_queue {
private:
    CONT container;
    int num;
    CMP compare;
}

    맨 첫 번째 줄을 보면 글 맨 위에 있는 사진에서 확인할 수 있듯이 template를 동일하게 선언하였다. 타입, 컨테이터, 비교클래스.

    멤버변수는 template로 선언한 container가 컨테이너, num은  원소의 수를 나타내고 compare는 비교를 실행할 인스턴스이다. 비교 클래스를 받기 때문에 클래스 안에 있는 비교함수나 연산자를 이용하기 위해선 그 class를 타입으로 가지는 인스턴스가 존재해야하기 때문에 선언하였다. 예를 들어 CMP안에 ()연산자가 정의된 경우 compare(a, b)와 같이 사용하여 비교연산을 수행할 수 있다.

사이트에 나와있는 멤버 함수는 다음과 같다.

이 중에 구현한 함수는 생성자를 포함해 empty, size, top, push, pop을 구현하였다. 다른 함수들은 많이 사용되지 않기 때문에 생략하였다.

소스 코드

아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/mypriority_queue.cpp

이번에는 C++에서 제공하는 Standart Template Library의 <list>를 구현해보았다. list는 linked list(연결리스트)를 구현한 것이며 특징으로는 iterator를 제공하고 양방향 연결리스트라는 것이다. cplusplus.com에 검색하면 나오는 list의 모든 메소드들을 구현하지는 못하였고 많이 쓰이는 메소드 몇 가지만 구현하였다. 소스코드는 아래의 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/mylist.cpp

연결리스트는 컴퓨터 전공생이면 1학년부터 C언어에서 포인터를 배우며 누구나 구현해보았을 것이다. 양방향 연결리스트도 이전노드와 연결해주는 것만 포함하면 전혀 다를 것이 없이 쉽게 구현할 수 있다. 따라서 이 구현에서 새로웠던 점은 iterator구현이다. list의 iterator 구현을 위한 특징이 하나 있다. 아래는 mylist의 멤버 변수이다.

멤버변수

public:
    node* head; //시작 노드
    node* tail; //마지막 노드
    node* fin; //end 노드
    int num; //노드 수

head와 tail은 첫 번째 노드와 마지막 노드를 가리킨다. iterator에서는 end가 존재한다. end는 연결리스트의 노드가 아니며 마지막만을 나타내는 기능을 제공한다. 즉 데이터가 들어있지 않다. 따라서 list에 아무것도 들어있지 않았어도 end를 가리키는 fin노드는 존재하여 유지시켰다.

iterator

class myiterator {
        node* current;
    public:
        myiterator(node* node = 0) : current(node) {};

        myiterator& operator++() {
            current = current->next;
            return *this;
        }
        
        myiterator& operator--() {
            current = current->prev;
            return *this;
        }

        node* operator&() {
            return current;
        }

        T& operator*() {
            return current->data;
        }

        bool operator !=(const myiterator& cmp) {
            return (current != cmp.current);
        }

        bool operator ==(const myiterator& cmp) {
            return (current == cmp.current);
        }
    };

iterator는 vector를 구현했을 때와 비슷하다. 연산자는 ++, --, *, !=, ==를 구현하였고 &연산자는 iterator로부터 포인터 값을 얻기 위해 내가 따로 만들었다. 물론 사용자도 사용할 수 있다. ++와 --는 각각 다음 노드, 이전 노드로 이동하는 연산자이다. iterator를 이용한 연결리스트를 순회할 때 굉장히 유용하게 사용할 수 있다. * 연산자는 현재 노드의 데이터 값을 얻어오는 연산자이다. ==와 !=는 각각 두 iterator변수가 같은 노드를 가리키는지 다른 노드를 가리키는지를 판단하는 연산자이다.

methods

구현한 메소드를 나열해보면

size, empty, front, back, push_back, pop_back, push_front, pop_front, insert, erase, begin, end로 총 12가지이다. 메소드는 모두 cplusplus.com에서 list를 검색했을 때 나오는 메소드와 똑같이 동작한다. 아래에서 실제 실행 결과로 보여주겠다. 코드가 길어 소스코드는 위의 링크에서 확인할 수 있다.

실행결과

이 코드는 아래와 같이 동작한다.

    1. 1부터 10까지 push_back을 한 다음 출력

    2. 3번 pop_back()을 한 다음 출력

    3. 100부터 3번 push_front한 다음 출력

    4. 6번 pop_front한 다음 출력

실행 결과는 다음과 같이 올바르게 나오는 것을 알 수 있다. iterator를 이용하여 모든 노드의 데이터를 출력하는 것도 올바르게 동작하는 것을 확인할 수 있다.

이번에는 insert와 erase를 사용해보겠다.

이 코드는 다음과 같이 동작한다.

    1. 1부터 10까지 push_back하고 출력

    2. begin부터 2번 다음 노드로 이동 후 100 insert 하고 출력

    3. 그 다음 3번 다음 노드로 이동 후 erase하고 출력

결과는 다음과 같다.

실행 결과 begin부터 2번 이동한 3번 위치에서 insert를 수행할 경우 3번 위치에 100을 삽입하고 3부터는 뒤로 밀리는 것을 알 수 있다. 그 다음 3번 위치부터 3번 이동한 6번 노드에서 erase연산을 수행하여 6번 노드가 사라진 최종 결과가 정확히 나왔음을 확인할 수 있다.

이렇게 C++ STL의 list의 일부를 직접 구현해보았다. 연결리스트를 직접 구현할 경우 예상치 못한 널포인터로 segmentation fault가 발생하는 것을 자주 접할 수 있다. 글쓴이 역시 list를 구현하며 몇 번의 segmentation fault를 보았다. 하지만 포인터 관리만 잘해주면 오류를 쉽게 찾고 고칠 수 있기 때문에 이렇게 직접 구현해보며 실수를 깨달을 수 있었다.