반응형 trie3 [Algorithm] 트라이(Trie) 트라이(Trie)" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스Trie는 탐색트리의 일종으로 특정 문자열이 포함되어있는지 등을 찾는데 효과적인 자료구조다. 예를 들어 영어로 된 여러 단어가 N개 주어지고, 여러개의 접두어가 M개 주어진다.이때, M개의 접두어로 시작하는 단어가 몇 개 있는지 구하는 경우를 생각해보자. 단순하게 반복문으로 구하게 되면 (M개의 접두어)*(N개의 단어)*(접두어와 단어를 비교) 의 반복을 하게 된다.M, N, 접두어 단어의 길이가 작으면 상관없지만 조금이라도 커지면 시간복잡도가 크게 늘어나게 된다. 이러한 반복을 줄이는데 효과적인 자료구조가 Trie다. 이제 [HILL, HIGH, HELL, HELLO, HELLT] 라는 단어를 Trie 구조로 .. 2024. 5. 24. [프로그래머스/C++] 가사 검색 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음 이 문제를 봤을 때 trie 알고리즘을 사용하면 빨리 문제를 해결할 수 있겠다는 생각이 들었다. 왜냐하면 특정 문자가 같은지 비교하고 수를 세는 과정에서 trie 알고리즘을 사용하면 빠르게 해결 될 것 같았기 때문이다. 문제는 조건을 제대로 안읽어서 ab?cd와 같이 중간에 ?가 들어갈 수 있는 줄 알고 코드를 구현했다. 하지만 알고보니 양 끝에만 ?가 연속적으로 들어갈 수 있었다... [문제 풀이] trie 알고리즘으로 문제를 푼 방법은 다음과 같다. 예를 들어 trie라는 문자가 들어온다고 가정하자. 이 경우 위 그림과 같이 t 뒤에는 물음표가 3개 오는 경우가 올 수 있다. 이를 map를 이용해 [문자열의 길이: 개.. 2024. 3. 27. [프로그래머스/C++] 자동완성 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 자동완성 기능을 넣기 위해서 한번이라도 입력된 단어는 자동으로 출력되도록 기능을 구현하기로 했다. 이 때, 앞부분이 같은 단어라면 구분을 위해서 구분이 될 때 까지 단어를 입력해야한다. 만약 goat와 gone이 있다면 구분을 위해 goa와 gon을 입력해 주어야 한다. 그래서 입력해야 할 문자의 수는 6이다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에 보고 trie 알고리즘을 활용하면 쉽게 풀 수 있을 것 같아서 trie 알고리즘을 활용해 풀었다. 그런데 풀고나서 다른 사람들의 풀이를 보니 정렬을 활용해 푼 사람들이 많았다. 게다가 테스트 케이스에서는 더 빨랐다... ㅠㅠ 정렬을 활용한 풀이는 앞이나 뒤에 오는 단어와 비교해서 몇.. 2024. 1. 7. 이전 1 다음 반응형
