greentea31's Note

트라이란?

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조.

최대 20개의 알파벳을 갖는 10000개의 문자열이 있다고 가정할때 일반 배열에 문자열을 저장할 시, 특정 문자열의 존재여부 판단은 10000번의 연산이 필요하다. 하지만 Trie에 저장할 시 20번 안팎의 연산으로 문자열의 존재여부 판단이 가능하다. 트라이의 예시는 아래의 그림과 같다.

["A", "to", "tea", "ted", "ten", "i", "in", "inn"] 을 키로 둔 트라이의 예시이다. 동일한 키를 배열에 담고 "tea"의 존재 여부를 판단하려 했다면 최악의 경우 8번의 연산이 필요하지만 트라이에서는 문자열의 길이만큼의 연산으로 존재 여부가 판단이 가능하다.

트라이 예시 문제

https://leetcode.com/problems/implement-trie-prefix-tree/

트라이를 구현해보는 문제가 리트코드에 있으니 풀어보면서 익히면 좋다.

정답 코드는 아래와 같다.

class TrieNode:
    def __init__(self):
        self.word = False
        self.children = collections.defaultdict(TrieNode)
        

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children[char]
        node.word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

class BinaryHeap(object):
    def __init__(self):
        self.items = [None]

    def __len__(self):
        return len(self.items) - 1  # 배열의 마지막 인덱스를 가리키게끔 함

    def _percolate_up(self):  # insert에서 쓰일 내부 함수이므로 앞에 _를 붙임
        idx = len(self)
        parent = idx // 2
        while parent > 0:
            if self.items[idx] < self.items[parent]:
                self.items[parent], self.items[idx] = self.items[idx], self.items[parent]
            idx = parent
            parent = idx // 2

    def insert(self, k):
        self.items.append(k)  # 일단 맨 뒤에 붙인 후
        self._percolate_up()  # 최소 힙을 만족할 때 까지 자식, 부모 값 계속 변경

    def _percolate_down(self, idx):
        left = idx * 2
        right = idx * 2 + 1
        smallest = idx

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left

        if right <= len(self) and self.items[left] < self.items[smallest]:
            smallest = right

        if smallest != idx:
            self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
            self._percolate_down(smallest)

    def extract(self):
        extracted = self.items[1]
        self.items[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted

출처

https://search.shopping.naver.com/book/catalog/32456486633?cat_id=50010920&frm=PBOKMOD&query=%ED%8C%8C%EC%9D%B4%EC%8D%AC+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+%EC%9D%B8%ED%84%B0%EB%B7%B0&NaPm=ct%3Dl7x0gr9c%7Cci%3D37450ff6270b8d3a48291e8dd82bcdc4e2f38eba%7Ctr%3Dboknx%7Csn%3D95694%7Chk%3Dd52b61344c06ba5a9592667b4cfc72998c53613e 

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

const int INF = 987654321;
int d[20005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int V, E, u, v, w;
    cin >> V >> E;

    for (int i = 1; i < V+1; i++) { // 전체 정점 거리 무한대 초기화
        d[i] = INF;
    }

    int start;
    cin >> start;

    vector<pair<int, int>> adj[20005];

    for (int i = 0; i < E; i++) { // 인접 리스트
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최소 힙
    // (정점까지의 거리, 정점 번호)를 저장하는 최소 힙을 선언한다.
    d[start] = 0; // 시작 정점까지의 거리는 0이다.
    pq.push(make_pair(d[start], start)); // 시작 거리 0 최소화후 최소힙 삽입


    while(!pq.empty()) {
        pair<int, int> cur = pq.top(); pq.pop();
        if (d[cur.second] != cur.first) continue;
        for (int i = 0; i < adj[cur.second].size(); i++) {
            pair<int, int> next = adj[cur.second][i];
            if (d[next.second] <= d[cur.second] + next.first) continue;
            d[next.second] = d[cur.second] + next.first;
            pq.push(make_pair(d[next.second], next.second));
        }
    }

    for (int i = 1; i < V+1; i++) {
        if (d[i] == INF) cout << "INF\n";
        else cout << d[i] << '\n';
    }

    return 0;
}

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

이 문제의 정답이기도 하다.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        Q = [(0, k)]  # 시작점과 시작 거리
        dist = collections.defaultdict(int)
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:  # 거리 저장이 안되어있으면
                dist[node] = time  # 거리 저장
                for v, w in graph[node]:
                    temp = time + w
                    heapq.heappush(Q, (temp, v))
        
        if len(dist) == n:
            return max(dist.values())
        return -1

https://leetcode.com/problems/network-delay-time/

이 문제의 정답이기도 하다.

출처

https://blog.encrypted.gg/941?category=773649 

https://search.shopping.naver.com/book/catalog/32456486633?cat_id=50010920&frm=PBOKMOD&query=%ED%8C%8C%EC%9D%B4%EC%8D%AC+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+%EC%9D%B8%ED%84%B0%EB%B7%B0&NaPm=ct%3Dl78vgtt4%7Cci%3Df701ad06257574c041af4ed5be5c108b6047f8ac%7Ctr%3Dboknx%7Csn%3D95694%7Chk%3Da3fb28618a3308e23e626cf38260466b81380bd4 

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

//struct NODE {
//    struct NODE *prev, *next;
//    int data;
//};

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

void traverse() {
    int cur = nxt[0];
    while(cur != -1) {
        cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
    cout << '\n';
}

void insert(int addr, int num) {
    dat[unused] = num;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    if (nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}

void erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    fill(dat, dat+MX, -1);
    fill(pre, pre+MX, -1);
    fill(nxt, nxt+MX, -1);


    return 0;
}

출처

https://blog.encrypted.gg/932?category=773649 

큐를 활용해 너비 우선 탐색을 시행하는 예시 코드이다.

C++ - Flood Fill BFS

// BFS 예시 코드

#include <bits/stdc++.h>
using namespace std;

int board[502][502];
bool vis[502][502];
int n = 7, m = 10; // n은 가로 길이, m은 세로 길이
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<pair<int, int>> Q;
    vis[0][0] = true;
    Q.push(make_pair(0, 0));

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        cout << '(' << cur.second << ", " << cur.first << ") -> ";
        for (int dir = 0; dir < 4; dir++) {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[ny][nx] || board[ny][nx] != 1) continue;
            vis[ny][nx] = true;
            Q.push(make_pair(ny, nx));
        }
        
    }
    
    return 0;
}

Python - 인접 리스트로 주어진 그래프에 대한 BFS

import collections

graph =[[], [1], [1, 3]] # 인접 리스트로 주어진 그래프


def bfs(start_v):
    discovered = [start_v]
    queue = collections.deque([start_v])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

연결되어 있고 방문하지 않은 정점들을 전부다 큐에 넣고 방문 처리한다.

큐가 빌 때 까지 큐의 맨 앞의 정점에 대해 이를 반복한다.

출처

C++ 코드

https://blog.encrypted.gg/941?category=773649 

Python 코드

https://book.naver.com/bookdb/book_detail.nhn?bid=16406247 

#include <bits/stdc++.h>
using namespace std;

int output[10];

void go(int index, int selected, int max_number, int length) {
    if (selected == length) {
        for (int i = 0; i < length; i++) {
            cout << output[i] << ' ';
        }

        cout << '\n';
        return;
    }

    if (index > max_number) return;
    output[selected] = index;
    go(index+1, selected+1, max_number, length);
    go(index+1, selected, max_number, length);
}

int main() {
    int N, M;
    cin >> N >> M;
    go(1, 0, N, M);
}

위의 코드와 같이 재귀로 조합을 구현할 수 있다.

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

위의 문제의 정답 코드이기도 하다.

#include <bits/stdc++.h>
using namespace std;

int discovered[10];
int output[10];

void go(int index, int max_number, int length) {
    if (index == length) {
        for (int i = 0; i < length; i++) {
            cout << output[i] << ' ';
        }

        cout << '\n';
        return;
    }

    for (int i = 1; i <= max_number; i++) {
        if (discovered[i]) continue;
        discovered[i] = 1;
        output[index] = i;
        go(index+1, max_number, length);
        discovered[i] = 0;
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    go(0, N, M);
}

중복을 허용하지 않는 순열을 재귀를 이용해 작성한 코드이다.

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

위의 문제의 정답 코드이기도 하다.