문자열을 빨리 찾을 순 없을까? 개념 문자열은 문자들을 이어붙여 만든 개념으로 이를 빠르게 탐색하고 싶을 때 문자열들을 문자 하나를 기준으로 앞에는 어떤 문자가 오는지, 뒤에는 어떤 문자가 오는지를 체크 해놓으면 여러 문자열을 저장할 때 더 적은 비용을 들여 탐색할 수 있다. 말은 쉽지.. 트라이(Trie) 알고리즘 문자열 집합을 표현하는 트리 자료구조 문자열을 탐색하는데 있어 시간을 줄이기 위한 알고리즘(문자열 탐색 알고리즘) 장점 빠른 탐색 시간( O(M *L) → O(M) ※M: 문자열의 수, L: 가장 긴 문자열 길이) 단점 정렬이 되어 있어야 함 비효율적인 메모리 기존 : 문자열 길이(개행포함) * 문자열의 총 개수 트라이 형식 : 문자열 * (다음 노드의 수 + 끝인 경우의 문자열) * 문자열..

https://www.acmicpc.net/problem/9935 이해 문자열을 완전 탐색을 통해 더했다가 뺐다가 할 수 있지만, 최대 길이가 1,000,000 이므로 뺄때, 붙일 때 길이만큼 탐색하고, 제거/더해줌 반복되므로 시간 초과가 날 수 있음 Stack 구조의 append/pop 연산을 통해 중복되는 반복을 제거하고, 최대 폭발 문자열의 길이만큼만 반복하게 하여 시간을 줄일 수 있음 구현 Stack으로 이용할 리스트 생성 Stack에 문자열 하나씩 저장하며, 길이가 폭발 문자열 길이 보다 길어졌을 때부터 폭발 문자열이 stack 내부에 있는지 확인 → 마지막 길이만큼만 확인하면 모두를 확인할 수 있음 만약 폭발 문자열이 있다면 pop 연산을 통해 제거 없다면 계속해서 append 연산을 통해 S..

https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 이해 문자열 탐색을 통한 완전탐색 구현 문제 해당 단어를 탐색하여 개수를 센 후, 이를 비교해도 시간이 충분하다.(O(1,000,000)) 구현 각 단어별 구성하고 있는 단어와 그 개수를 저장할 dictionary 생성(편의를 위한 defaultdict 사용) 단어별 구성 단어와 개수를 저장 단어별 구성 단어 개수에서 기준 단어 구성 단어의 개수를 빼서 개수를 재구성(아래와 같이 표현) 해당 단..