Algorithm76 [알고리즘] 찾기 KMP (백준 1786번) 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 정확하게 KMP를 구현하는 문제다. 패턴 매칭 실패 시 패턴 인덱스 j 가 돌아갈 곳을 지정하는 failureFunction을 구하는 메서드와 그걸 이용해서 패턴 매칭을 하는 KMP 메서드로 이루어져있다. 주로 겹쳐져있는 패턴도 찾아낼 때에 사용한다. EX) 텍스트 : ababa, 패턴 : aba → 패턴 개수 : 2개 String.replace로는 찾아낼 수 없는 경우임 import java.io.BufferedReader; import java.io.. 2020. 8. 27. [알고리즘] 전화번호 목록 (백준 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 ··· 14 15 16 17 18 19 다음
