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

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이해 완전 탐색을 통해 구현할 수 있지만, 이동에 있어 비용이 다르기 때문에 우선순위 큐를 활용한 다익스트라가 더 유리 비교를 위해 두 방식 모두 풀이했습니다. 구현 BFS 방문했을 때 최소값을 알기 위한 visited 배열 선언(초기화 값은 최댓값인 100,001) N부터 너비우선 탐색을 통해 탐색 방문 시 이전 방식보다 가중치가 작다면 최솟값을 변경하면서 ..

https://www.acmicpc.net/problem/12851 이해 N에서 K까지 가는 길을 완전탐색을 통해 해결 완전 탐색을 하면서 최소가 되는 시점에만 값을 변경, 이후 같은 값이 나오면 카운트 ++ 구현 방문 확인용 배열 및 후보 과정을 담을 배열 생성 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가 코드 # 46944KB380ms # 12851 숨바꼭질 2 import sys from collections import deque input = sys.stdin.readline def solution(): N, K = map(int, input().split()) que = deque([(0, ..

https://www.acmicpc.net/problem/1697 이해 N에서 K까지 가는 길을 완전탐색을 통해 해결 다익스트라를 통해 해결도 가능할 것 같아 풀어봄 방문 확인용 배열에 최솟값을 저장해 가지치기를 할 수 있음 N == K 인 경우, 조건문을 통해 배열에 넣고, 빼는 시간을 줄임 구현 방문 확인용 배열 및 후보 과정을 담을 배열 생성 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가 코드 너비우선탐색 # 35388KB140ms import sys from collections import deque N, K = map(int, sys.stdin.readline().strip().split())..

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 사용) 단어별 구성 단어와 개수를 저장 단어별 구성 단어 개수에서 기준 단어 구성 단어의 개수를 빼서 개수를 재구성(아래와 같이 표현) 해당 단..