Trie 자료구조

최성현·2021년 3월 7일
0

👏 접두사 기준 짧은 문자열을 찾을 때 최적화된 자료구조이다.

트리 형태로 링크드리스트 형태로 '글자수'만큼(O(n))시간소요

😊 빠르긴하지만 메모리가 너무 많이 쓰인다

글자 하나당 노드하나를 만들어주고 노드안에 26개(알파벳 대문자) 포인터가 쓰인다.

삼성,카카오에서 가끔 한두문제 나옴

MST,TRIE,Union-Find 3가지는 기본을 다 쌓은후 공부해보자

✌기본 소스 코드

#include<iostream>
#include<string>
using namespace std;
struct Node {
	char ch;
	Node* next[26]; //대문자 26개
	//int cnt 까지 추가 하여 활용가능

};
Node* head;
void init() { 

	head = new Node();
	head->ch = '#'; //처음 노드(스타트값)
}
void insert(string str) {
	Node* now = head; //head가리키고 시작
	for (int i = 0; i < str.size(); i++) { //한글자씩 탐색
		int index = str[i] - 'A'; //0번 index
		if (now->next[index] == NULL) {
			now->next[index] = new Node();
			now->next[index]->ch = str[i];
		}
		now = now->next[index];

	}
}

int main() {
	init();
	insert("ABC");
	insert("ABS");
	insert("ABCD");




	return 0;
}

참고 이미지 블로그

profile
후회없이

0개의 댓글