문자열13 [자료구조] Trie 트라이 트라이 (Trie) retrieval Tree에서 온 단어 문자열들을 트리 구조로 저장하여 O(log n) 속도로 빠르게 문자열을 탐색할 수 있게 해준다. 알고리즘 문제에선 주로 문자열의 '접두어', '~로 시작하는', '접미어', '~로 끝나는' 등의 키워드가 나오는 접두어, 접미어 판별 문제에서 사용된다. ※ 참조 문제 코딩테스트 연습 - 가사 검색 programmers.co.kr 자바로 트라이 구현하기 1. 노드 (Node) 클래스 import java.util.HashMap; public class Node { //해당 node 밑의 서브트리 총 node 개수 (옵션 : 즉 필요에 따라 넣는 요소) int count = 0; // isLast = true면 해당 문자열 존재 boolean isLa.. 2020. 8. 26. [알고리즘] 전화번호 목록 (백준 5052번) 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 문자열 처리 문제인데 전화번호들의 일관성을 유지하려면 '한 번호가 다른 번호의 접두어인 경우가 없어야 한다' 라고 되어있다. 즉 911, 9112584 같은 경우엔 일관성이 없는 경우이다. 접두어 판별문제인만큼 Trie를 사용해야한다. Trie 자료구조에 관한 것은 알고리즘 설명 카테고리에 올라와 있을 것이다. Trie 클래스와 Node 클래스를 만들고 Trie 클래스에 String을 삽입하는 insertString() 메서드와 일관성 있는지 판별하는 isConsi.. 2020. 8. 26. [알고리즘] 문자열 폭발 (백준 9935번) 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 www.acmicpc.net 폭발 문자열, 즉 특정 패턴을 찾아서 매칭되면 그 패턴에 해당하는 문자열을 삭제하고, 새로 만들어진 문자열에서 또 패턴을 찾아 삭제하라는 문제이다. 당연하겠지만 String.replaceAll로 반복문을 돌리는 것은 메모리 초과, 혹은 시간 초과로 불가능하다. O(N) 만큼의 시간복잡도로 패턴을 찾아 파괴하는 것이 포인트이다. 1. failureFunction 만들기 KMP를 응용하여 failureFunction을 만들어서 비교 문자가 같지 않은 경우 pattern 인.. 2020. 8. 26. [알고리즘] 팰린드롬? (백준 10942번) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 팰린드롬을 판별하는 동적 프로그래밍 + 문자열 처리 문제이다. 우선 팰린드롬이란 문자열 중앙을 기준으로 좌측, 우측이 마치 데칼코마니처럼 일치하는 경우를 말한다. EX) 121, 5, 2345432 문제에선 S 인덱스부터 E 인덱스까지의 문자열이 팰린드롬인지를 판별하라고 했는데 동적 프로그래밍을 사용하지 않고 일일이 계산한다면 O(N ^ 3) 혹은 O (N * M) 의 시간이 걸리는데 최악의 경우 무려 80억번의 계산이 필요하다. 하지만 동적 프로그래밍을 사용해서 구하게 된다면 O (N ^ 2) 의 시.. 2020. 8. 25. 이전 1 2 3 4 다음
