# Trie
14425번 문자열 집합
https://www.acmicpc.net/problem/14425처음 n개의 문자열을 trie에 적재한 뒤, 주어진 m개의 target 문자열들에 대해 일치하는 문자열들의 개수를 구했다.이때, 일치하는 문자열을 구하기 위해 target의 문자 하나씩 타고 끝
Trie (in Python)
검색어 추천할 때 target 문자열에 해당하는 다른 모든 하위 문자열들을 빠르게 탐색할 수 있다는 장점이 있다.실제 코테에서 많이 나오는 거 같진 않지만, 잊고 있다가 가끔 한번씩 등장함딕셔너리를 활용하면 depth를 추가해가며 한 글자씩 저장하기 용이하다.테스트케이
가사 검색
본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았
Trie에 대해 알아보자
접두사 트리라고도 하는 Trie는 문자열을 효율적으로 검색하는 데 사용되는 트리 기반 데이터 구조입니다. Trie라는 이름은 영어로 "tree"로 발음되는 retrieval이라는 단어에서 유래되었습니다.Trie 데이터 구조에서 각 노드는 접두사 또는 완전한 단어를 나타
Trie
시간복잡도(N : 문자열의 길이) : O(N)개요문자 단위로 Tree의 하위로 내려가며 추가한다.문자열의 마지막에 도달하면 해당 글자가 문자열의 끝이라는 표시를 한다
React 자동완성 정리, 실활용 사례
최근 코테준비를 위한 자구,알고리즘을 공부하며 Trie라는 새로운 자료구조를 배우고 구현해봤음. Trie는 검색창 자동완성 등, 문자열을 키로 하는 탐색 트리의 일종으로 자동완성에 주로 사용되는 자료구조다. 자동완성은 실제로 많은 곳에 활용되고, 평소에 그 자세한 원리
Leetcode 211. Design Add and Search Words Data Structure with Python
Trie의 색다른 활용법~
BOJ 19585 전설
먼저 후기부터 적으면 되게 고생한 문제...트라이를 처음 접한 것과 달리 트라이를 구현하는 건 어렵지 않았다.하지만 map을 사용할 때 초기화를 제대로 안해줘서 문제가 생겼는데 문제점을 못찾아 고생했다.맞왜틀직관적으로 접근하면 당연하지만 문자열 비교의 횟수가 어마무시하
Graph Algorithms #3
node, edge로 이루어진 자료 구조부모-자식 관계로 구성되어 있음사이클이 존재할 수 없고, 모든 노드는 자료형으로 표현이 가능node 수가 n개면 edge 수는 n-1, 루트에서 노드로 이동하는 경로는 유일하다.전위 순회(pre-order) : 각 루트를 순차적
Data Structure
여러 원소를 하나의 묶음으로 관리하고 각 원소 간에 순서가 존재해 인덱스를 통해 접근하는 리스트파이썬에 내장된 리스트 관련 함수들을 구현해보면 다음과 같다.기존 array는 인덱스를 통해 빠른 접근이 가능하지만, 크기를 지정해야 해 데이터 추가, 삭제가 힘들기에 이러한
[BOJ 9202] Boggle
https://www.acmicpc.net/problem/9202레벨 : P5알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이DFS를 통해 보드에서 가능한 단어들을 찾고 해당 단어가 사전
프로그래머스 가사 검색
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '
Leetcode - 208. Implement Trie (Prefix Tree) 풀이
아래와 같은 동작을 구현하라. 기본적으로 trie를 구현하는 방법에 대한 문제이지만, 그 전에 hashtable만 사용하여 아주 간단한게 풀어보았다. hashtable 방법insert() 함수에서 모든 prefix를 해시테이블에 값 1로 저장한다. 그리고 전체 word
[백준 C++] 13504 XOR 합
문제 N개의 수로 이루어진 수열 A가 주어진다. 수열 A에서 연속된 부분 수열을 고르려고 한다. 부분 수열의 XOR 합이란, 부분 수열에 들어있는 모든 원소를 XOR한 값을 의미한다. 수열 A가 주어졌을 때, XOR 합이 가장 큰 부분 수열을 찾는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10) 각...