# Trie

54개의 포스트

[자료구조] Trie

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조"ant"를 추가하기 위하여 root의 자식노드 'a'가 존재하지 않으면 추가하고 동일한 방법으로 'n', 't' 추가"ant"를 탐색하기 위하여 root -> 'a' -> 'n' -> 't' 3번의 이동

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

백준 13504번: XOR 합

백준 13504번: XOR 합입력받은 수열의 누적 XOR을 계산해놓는다. 이 값을 전부 트라이에 삽입하고, 각각의 값과 XOR했을 때 최댓값이 부분수열 XOR의 최댓값이다. trie를 이런식으로 만드는게 훨씬 간편한듯. 노드 번호를 전역 변수로 관리한다. 새로운 노드를

2022년 4월 30일
·
0개의 댓글
post-thumbnail

백준 16903번: 수열과 쿼리 20

백준 16903번: 수열과 쿼리 200이랑 1만 있는 트라이를 만든다. 입력받는 정수의 맨 앞쪽 비트 (2^29)부터 쭉 훑으면서 둘 다 있으면 XOR값을 최대로 할 수 있도록 선택, 둘 중 하나만 있으면 그거 선택. 다 더하면 정답!삭제 연산은 cnt를 감소시킨다.

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

백준 5467번: Type Printer

백준 5467번: Type PrinterTrie를 구성하고 재귀적으로 깊이가 얕은 글자부터 출력한다.마지막에 최대한 긴 단어를 치고 지우지 않고 끝내야 한다.

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

백준 3080번: 아름다운 이름

백준 3080번: 아름다운 이름노드 자식 개수만큼 permutation 구하면서 올라가면 된다. 로직 짜는건 쉬운데 그냥 Trie child26 해도 MLE, map<char, Trie> child해도 MLE.. 그나마 메모리 제일 적게 사용하는 vector 만들

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

백준 5446번: 용량 부족

백준 5446번: 용량 부족지워야 하는 파일, 지우면 안 되는 파일 둘 다 트라이에 insert. 이 때 지워야 하는 파일은 노드 마지막에 종료 표시, 지우면 안 되는 파일은 모든 노드에 지울 수 없다고 표시. 노드 하나가 removable 하면 그 모든 자식들도 re

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

백준 19585번: 전설

백준 19585번: 전설색상은 trie에 insert, 닉네임은 unordered_set에 insert.그리고 쿼리 앞부분부터 트라이에서 찾는다. 트라이에 알파벳이 존재하지 않으면 return false, 트라이에 해당 색상이 존재하고, 뒷쪽 substring이 uno

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

백준 16934번: 게임 닉네임

백준 16934번: 게임 닉네임단어를 루트에 삽입하면서 하나씩 출력한다. 그러다가 다음 알파벳이 자식 노드로 존재하지 않으면, print를 false로 변경하고 재귀호출한다. print가 true인 경우에만 알파벳을 출력한다.같은 닉네임으로 가입한 유저를 숫자로 구분하

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

백준 5670번: 휴대폰 자판

백준 5670번: 휴대폰 자판자동완성이 안되는 경우는 단어가 완성되는 경우, 혹은 자식이 2개 이상인 경우이다.모든 단어가 같은 알파벳으로 시작하더라도 처음에는 버튼을 한 번 눌러줘야 한다.다들 C-style 문자열(const char\*)로 trie를 구현하고, 그걸

2022년 4월 20일
·
0개의 댓글
post-thumbnail

[BOJ]5052(python)

백준 5052(전화번호 목록) python 풀이입니다

2022년 4월 19일
·
0개의 댓글
post-thumbnail

[Python] 백준 20166 - 문자열 지옥에 빠진 호석 문제 풀이

분류: Trie (트라이)

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

[Python] 백준 4358 - 생태학 문제 풀이

분류: Trie (트라이)

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

[BOJ] 5052 - 전화번호 목록

접두어 확인 Trie 자료구조

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

[Python] 백준 5052 - 전화번호 목록 문제 풀이

분류: Trie (트라이), String (문자열)

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

[NodeJS] 대용량 데이터 C++ 로 필터링 하기

개요 대기업 커머스로 부터 매체별 광고등록 프로세스에 사용하기 위한 상품 EP 데이터를 제공받고 자체 필터링하여 매체별로 피드를 생성하는 프로세스가 기존에 있었다. 대략 1~2억 개의 대용량 상품 ep데이터이다. 기존에는 필터링 해야할 카테고리, 상품이름에 포함된 단

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

[ Python_Algorithm ] 트라이 (Trie)

트라이는 검색 트리의 일종으로 일반적으로 키가 문자열인 동적 배열 또는 연고나 배열을 저장하는데 사용되는 정렬된 트리 자료구조이다.트라이는 실무에 매우 유용하게 쓰이는 자료구조로, 특히 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 트라이는

2022년 2월 25일
·
0개의 댓글

220208 화 Algorithms TIL

KMP 알고리즘 자료구조 공부 소스https://velog.io/@bongf/220207-Algorithms-TILhttps://m.blog.naver.com/kks227/220917078260주의. FailTable을 만들 때는 0번부터 시작하면 항

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

[프로그래머스] 가사검색 (파이썬)

https://programmers.co.kr/learn/courses/30/lessons/60060본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가

2022년 1월 28일
·
0개의 댓글

TRIE 구조

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.Trie 는 빠른 시간복잡도를 가지고 있기때문에 검색엔진 사이트에서 제공하는 자동 완성 및 검색어 추천 기능 등 문자열을 탐색하는 곳에서 Trie 알고리즘을 사용합니다.\["fro

2022년 1월 27일
·
0개의 댓글

Suffix Trie Construction

Suffix Trie Construction

2021년 12월 7일
·
0개의 댓글