Loading [MathJax]/jax/output/HTML-CSS/jax.js
본문 바로가기

Golang/Golang 자료구조

 (1)
[Golang 자료구조] 트라이(Trie) 구현하기 Golang은 내장 자료구조가 별로 없다. 하다못해 스택도 없다. 그래서 golang으로 몇몇 자료구조를 직접 구현하여 사용해보는 시리즈를 진행하고자 한다. 그 첫 번째는 간단하게 구현 및 테스트를 할 수 있는 트라이(Trie)이다.Trie  트라이를 간략하게 설명하면 여러 단어들의 집합을 하나의 트리로 관리하여 어떤 단어 S의 존재 여부를 O(|S|)의 시간 복잡도로 찾을 수 있는 자료구조이다. 비교적 간단하게 구현할 수 있고 트라이를 이용한 다양한 알고리즘 테크닉을 쓸 수가 있어 PS에서 인기가 많은 편이다. 이 포스트에서는 PS 수준에서 활용할 수 있는 간단한 트라이를 구현할 것이다.Node 구조체트라이에 필요한 노드 구조체를 정의해보자. type trieNode struct { child..

티스토리툴바