트리

트라이란?트라이(Trie)란 주로 문자열을 효율적으로 저장, 탐색하기 위한 트리 형태의 자료 구조를 의미한다.트라이는 문자열의 맨 앞 문자부터 계층적으로 저장하고 있다.위 그림에서 'tea'를 찾으려면 순서대로 't', 'te', 'tea'로 찾아 내려오면 된다.이처럼 트라이에서 찾으려는 문자열의 길이가 $m$일 때, $O(m)$의 시간 만에 원하는 문자열을 찾을 수 있다. 구현해보기삽입'tax'라는 문자열을 삽입해보자.root의 자식 중 't'가 있으므로 해당 노드로 이동한다.'t'의 자식 중 'a'('ta')가 없으므로 해당 노드를 생성 후 이동한다.'a'의 자식 중 'x'('tax')가 없으므로 해당 노드를 생성 후 이동한다.해당 구조를 코드로 작성하면 아래와 같다.class Node: def..

최소 신장 트리란?신장 트리(스패닝 트리)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다.트리이므로 간선의 수는 (정점의 수 - 1)이며, 사이클은 존재하지 않는다. 신장 트리 중 가중치의 합이 최소인 트리를 최소 신장 트리라고 한다. 최소 신장 트리 구하기크루스칼 알고리즘(Kruskal's Algorithm)크루스칼 알고리즘은 가중치가 가장 작은 간선부터 확인하며 사이클이 생기지 않는 경우 MST에 포함하는 그리디(Greedy)적인 방법이다. 먼저 그래프 내의 모든 간선을 가중치에 대한 오름차순으로 정렬한다.이후 반복문을 돌며 가중치가 작은 가중치부터 MST에 포함 가능한지 여부를 판별하는데, 서로소 집합을 이용하는 방법이 가장 대중적이다.($A$와 $B$가 이미 같은 집합에 있다면, 이미 해당 ..