# 트라이

41개의 포스트
post-thumbnail

구글 자동완성 기능은 어떻게 만들어질까? - 대규모 시스템 설계 기초 13장

언뜻 보기엔 별거 아닌 것 같지만 빠른 속도를 보장하기 위해 제대로 된 설계가 필요하다.

2022년 11월 13일
·
1개의 댓글
·

자료구조&알고리즘_트라이

트리를 이용한 자료구조문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조ex) 검색에서 사용하는 자동완성 기능을 만들 때 사용하는 알고리즘검색어 자동완성, 사전 찾기 등에 사용한다.L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.각 정점이 자식에

2022년 10월 23일
·
0개의 댓글
·
post-thumbnail

[자료구조&알고리즘] 트라이(Trie)

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.각 간선은 새롭게 추가되는 정보를 가지고 있고 정점은 이전 정점으로부터 더해진 문자열 정보를 갖습니다.검색어 자동완성, 사전 찾기 등에 응용된다.L이 문자열의 길이일 때 탐색, 삽입은 O(L

2022년 10월 21일
·
0개의 댓글
·

[C++] 백준 16934번: 게임 닉네임

16934번: 게임 닉네임어떤 게임에서 유저의 닉네임을 기반으로 내부적으로 저장할 별칭을 만든다. 별칭을 생성하는 규칙은 다음과 같다.1\. 유저 닉네임의 접두사 중 가장 짧은 것을 사용하되, 이 접두사는 이전에 가입한 다른 닉네임의 접두사가 되면 안된다.2\. 만약

2022년 10월 17일
·
0개의 댓글
·

트라이(Trie)

(초창기에는 '트리'로 발음했으나, 기존의 트리(Tree)와 구분하기 위해 '트라이'로 불린다.)키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있는 자료구조 연상 배열, 결합형 배열, 맵(map), 사전(dictionary)으로 부르기도 한다

2022년 9월 17일
·
0개의 댓글
·

알고리듬 #14 | 트라이 (Trie)

문자열을 저장하고 효율적으로 탐색하는 자료구조 입니다.간선에 이전 정점으로부터 새롭게 추가되는 문자정보를 가지고 있습니다.트리 형태를 가지고 있습니다.검색어 자동완성, 사전 찾기 등에 응용될 수 있습니다.문자열 탐색시, 단순한 비교 방법보다 효율적입니다.단순한 비교 방

2022년 9월 3일
·
0개의 댓글
·
post-thumbnail

[ 자료 구조 ] Trie ( 트라이 )

문자열을 효율적으로 탐색할 수 있게 저장하는 자료구조.

2022년 8월 29일
·
0개의 댓글
·

[리트 코드] 208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/submissions/트라이를 직접 구현했다. 트라이는 다진 트리의 향태를 가진다.defaultdict() 는 ( ) 안에 기본값을 넣어주면 key 값을 선언

2022년 8월 13일
·
0개의 댓글
·
post-thumbnail

𝙏𝙧𝙞𝙚

트라이의 정의 및 접미어 트라이 적용 사례

2022년 8월 4일
·
0개의 댓글
·

카카오 2018 자동완성

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

2022년 7월 24일
·
0개의 댓글
·

하루일지 - 22.07.14

조인 : 두 개 이상의 테이블이나 데이터베이스를 연결하여 데이터를 검색하는 방법테이블을 연결하려면, 적어도 하나의 칼럼을 서로 공유하고 있어야 하므로 이를 이용하여 데이터 검색에 활용한다.종류1\. INNER JOIN : 교집합에 속하는 원소들을 보여줌2\. LEFT

2022년 7월 14일
·
0개의 댓글
·

백준 5052 전화 번호 목록

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

2022년 7월 13일
·
0개의 댓글
·
post-thumbnail

CS50_자료구조_(2)[연결리스트_트리,해시 테이블, 트라이, 스택,큐,딕셔너리, 퀴즈-!]

1. 연결리스트 먼저 배열은 임의접근을 할 수있어서 이진탐색을 쓸수있습니다. 그러나 연결리스트는 역동성을 가지며 임의접근이 불가합니다. 즉, 이진탐색이 불가합니다. 기존의 연결리스트는 하나의 포인터를 갖고있던 반면 두개의 포인터를 가지게 하여 이진탐색을 할 수 있도록 만들 수 있습니다. 이것을 트리라고 하며 이진탐색 트리입니다. 모든 노드의 왼쪽 자식...

2022년 6월 25일
·
0개의 댓글
·
post-thumbnail

[CS50] 트라이

트라이란 '각각의 노드가 배열로 이루어진 트리'다.이렇게 '트리'형태의 자료 구조로 찾으면 걸리는 시간이 '문자열의 길이'에 의해 한정된다.일반적인 영어 이름의 길이를 n이라고 했을때, 검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값이므로 O(1

2022년 6월 18일
·
0개의 댓글
·
post-thumbnail

[알고리즘] 트라이 개념 및 구현하기

TIL 트라이 구현하기

2022년 4월 3일
·
0개의 댓글
·

[C++] 백준 16903번: 수열과 쿼리 20

16903번: 수열과 쿼리 200이 하나 포함된 배열 A에 대해서 다음의 쿼리들을 구현해야 한다.1 x: A에 x를 추가한다.2 x: A에서 x를 제거한다. A에 x가 두 개 이상 있는 경우에는 하나만 삭제한다. 항상 A에 x가 있는 쿼리만 주어진다.3 x: A에 포함

2022년 3월 18일
·
0개의 댓글
·

[C++] 백준 14426번: 접두사 찾기

5052번: 전화번호 목록N개의 문자열이 주어지고 M개의 문자열이 주어진다. M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수를 구해야 한다.쉬운 풀이가 있지만, 트라이 연습삼아서 트라이로 접근해봤습니다. N개의 문자열을 모두

2022년 3월 18일
·
0개의 댓글
·

[C++] 백준 5052번: 전화번호 목록

5052번: 전화번호 목록주어진 전화 번호 중에 어떠한 전화번호가 다른 전화번호의 접두어가 되는 경우가 있는지 판별해야 한다.트라이를 이용해서 풀었습니다. 먼저 입력으로 주어진 전화번호들을 모두 트라이에 집어 넣습니다. 그 다음에 각 전화번호로 순서대로 트라이에서 탐색

2022년 3월 17일
·
0개의 댓글
·