# Trie

20개의 포스트

[Leetcode] 208. Implement Trie (Prefix Tree)

문제 바로가기In computer science, a trie, also called digital tree or prefix tree, is a type of search tree, a tree data structure used for locating specifi

2021년 4월 22일
·
0개의 댓글
post-thumbnail

트라이(Trie) 구현

이 글은 gogaegaebal, 코딩하는 지미님 블로그를 참고해 작성되었습니다. 사진을 누르면 각 사진의 출처로 이동합니다.문자열을 트리 형식으로 만들어 진행되며 이진탐색 트리와 비슷한 원리로 진행되기 때문에 빠르게 문자열 검색이 가능한 자료구조이다.문자 하나씩을 기준

2021년 3월 24일
·
0개의 댓글
post-thumbnail

[자료구조] TREE

TREE는 아래와 같은 요소로 구성된다.Node, Edge (간선), Root Node, Leaf Node (단말 노드), Internal Node (루트 노드와 단말 노드가 아닌 노드)Tree의 특징으로는 다음 3가지가 있다.서로 다른 임의의 두 노드를 연결하는 간선

2021년 3월 22일
·
0개의 댓글
post-thumbnail

Trie 자료구조

트리 형태로 링크드리스트 형태로 '글자수'만큼(O(n))시간소요글자 하나당 노드하나를 만들어주고 노드안에 26개(알파벳 대문자) 포인터가 쓰인다.삼성,카카오에서 가끔 한두문제 나옴MST,TRIE,Union-Find 3가지는 기본을 다 쌓은후 공부해보자참고 이미지 블로그

2021년 3월 7일
·
0개의 댓글
post-thumbnail

[leetcode] Short Encoding of Words

Time: O(N^2\*M), N is the length of the words, M is the length of wordsiSpace: O(1)

2021년 3월 6일
·
0개의 댓글
post-thumbnail

2018 KAKAO BLIND_[3차] 자동완성

코딩테스트 연습 - \[3차] 자동완성입력된 문자열 중 어떤 단어가 다른 단어의 접두어 가 되는 경우를 찾는 문제였다.접두어라면 반사적으로 prefix tree, 즉, Trie가 생각나 Trie로 구현하였다.for k in key:k가 현재 노드의 자식에 없을 때 (즉

2021년 2월 27일
·
0개의 댓글
post-thumbnail

[Trie] 프로그래머스_전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577이전에 같은 문제를 Hash를 이용해서 풀었던 적이 있는데 Trie로도 풀 수 있다고 해서 다시 풀어보았다. \[hash]프로그래머스\_전화번호 목록이전 풀이의

2021년 2월 26일
·
0개의 댓글
post-thumbnail

[백준] 5052 - 전화번호 목록 (java)

문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전...

2021년 1월 28일
·
0개의 댓글
post-thumbnail

[백준] 14425 - 문자열 집합 (java)

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음...

2021년 1월 28일
·
0개의 댓글
post-thumbnail

Kakao - 가사 검색

본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니

2021년 1월 26일
·
0개의 댓글

210126 개발일지(50일차) - 트라이(Trie) 알고리즘 개념 및 파이썬에서 구현하기(feat. Class)

트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 한다.retrieval(탐색)에서 trie를 따왔다고도 한다.이 자료구조를 활용해 검색어 자동완성, 사전

2021년 1월 26일
·
0개의 댓글
post-thumbnail

Kakao - 자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된

2021년 1월 16일
·
0개의 댓글
post-thumbnail

Python Dict를 이렇게 쓸 수 있다고? : Trie 자료형 구현하기

플젝을 열심히 구현하다 보면잠시 주위를 환기하기 위해 관련된 유사 주제들로 눈을 돌리는 것도 도움이 되는 것 같다.이번에도 사용자가 서비스에 등록한 문서들을 관리하기 위해 문자열 관리를 좀 공부하던 중개발자 테스트에도 단골로 출제된다는 Trie자료형이라는 것을 처음 알

2021년 1월 13일
·
0개의 댓글

[자료구조/C,C++]Trie 자료구조 사용하기

초기화된 Trie구조에 문자열 "abd"삽입 <결과> 문자열 "ab" 탐색문자열 "az" 탐색https://twpower.github.io/187-trie-concept-and-basic-problem

2020년 9월 11일
·
0개의 댓글

프로그래머스-전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577문자열 배열에서 한 문자열이 다른 문자열의 prefix인 경우가 있는지 확인하는 문제이다.정렬하면 123은 1234 바로 전에 있을 것이므로 인접한 문자열끼리만

2020년 7월 18일
·
0개의 댓글
post-thumbnail

[코딩테스트]프로그래머스 - 가사 게임

본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니

2020년 7월 10일
·
0개의 댓글

Trie 자료구조 JavaScript

Trie 자료구조 라는게 있다. 문자열 검색을 빠르게 해주는 자료구조이다. 요즘 문자열에 관한 코딩 문제들이 정말 자주 나오는데, 그 때마다 오픈채팅방 사람들이 Trie로 풀었다, KMP로 풀었다. 말이 많길래 이번 기회에 알아보았다.Trie에 대한 내용은 검색을 하면

2020년 7월 6일
·
0개의 댓글

프로그래머스 - 전화 번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577 > 접근 전화번호가 최대 100만개가 들어올 수 있으므로 절대로 일일이 비교하면 안됩니다. 카테고리가 해쉬여서 해쉬를 이용해야 되나 했는데, 결론적으론 Tire구

2020년 5월 6일
·
0개의 댓글
post-thumbnail

2020 KAKAO BLIND RECRUITMENT - 가사 검색

2020 KAKAO BLIND RECRUITMENT 가사 검색

2020년 5월 2일
·
0개의 댓글

[2020카카오공채] 가사 검색

문제출처: https://programmers.co.kr/learn/courses/30/lessons/60060 문제 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 ...

2019년 11월 27일
·
0개의 댓글